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

      Identifiers