MINIMUM PRECEDENCE CONSTRAINED SCHEDULING

• INSTANCE: Set T of tasks, each having length l(t)=1, number m of processors, and a partial order < on T.

• SOLUTION: An m-processor schedule for T that obeys the precedence constraints, i.e., a function $f : T \rightarrow N$ such that, for all $u \ge 0$, $\vert f^{-1}(u)\vert \leq m$ and such that t < t' implies f(t') > f(t).

• MEASURE: The finish time for the schedule, i.e., $\max\limits_{t\in T} f(t)$.

  
  

• Good News: Approximable within $2-2/\vert T\vert$ [344].

• Bad News: Not approximable within 4/3$-\varepsilon$ for any $\varepsilon >0$ [346].

• Comment: A variation with an enlarged class of allowable constraints is approximable within $3-4/(\vert T\vert +1)$ while a variation in which the partial order < is substituted with a weak partial order $\leq$ is approximable within $2-2/(\vert T\vert +1)$ [71]. Variation in which there is a communication delay of 1, i.e., if two tasks t<t' are scheduled on different machines, then f(t')>f(t)+1, is approximable within 3 [422], and not approximable within 5/4$-\varepsilon$ [260]. The same problem without limit on the number of processors, i.e. with $m=\infty$, is not approximable within 7/6$-\varepsilon$ [260]. The variation of this problem in which the average weighted completion time has to be minimized is approximable within 10/3 (respectively, 6.143 if the tasks have arbitrary length) [379]. Generalization where the tasks have lengths l(t) and the processors have speed factors s(i) is approximable within $O(\log m)$ [115].

• Garey and Johnson: SS9