Scheduling Interval-Ordered Tasks (Q3854618)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3655346
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Scheduling Interval-Ordered Tasks |
scientific article; zbMATH DE number 3655346 |
Statements
Scheduling Interval-Ordered Tasks (English)
0 references
1979
0 references
chordal graphs
0 references
interval orders
0 references
polynomial in time algorithms
0 references
scheduling unit length tasks
0 references
incomparability graph
0 references
arbitrary length tasks
0 references
NP-completeness
0 references
The problem, to be considered, is one of scheduling unit length tasks on \(m\) processors to minimize schedule length. The authors consider the special case of a partial order \(P=(V, A)\) among the tasks, i.e. one whose incomparability graph is chordal, where the Incomparability graph \(G(V, E)\) includes \([v, u]\) if and only if \((v, u), (u, v) \notin A\). This partial order is proved to be equivalent to an interval one, i. e. one whose nodes are closed intervals in the real line, and \((u, v) \in A\) if and only if \(x \in u, y \in v \Rightarrow x<y \). In the paper, an \(O\left(n^2\right)\) algorithm for solving the above problem, is proposed. In addition, the problem of scheduling arbitrary length tasks, subject to an interval partial order, is proved to be NP-complete in the strong sense.
0 references