Next: MINIMUM RESOURCE CONSTRAINED SCHEDULING Up: Multiprocessor Scheduling Previous: MINIMUM MULTIPROCESSOR SCHEDULING Index

### 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 such that, for all , and such that t < t' implies f(t') > f(t).

- MEASURE: The finish time for the schedule, i.e., .

- Good News: Approximable within 2-2/|T| [328].

- Bad News: Not approximable within 4/3 for any [330].

- Comment: A variation with an enlarged class of allowable constraints is approximable within 3-4/(|T| +1) while a variation in which the partial order < is substituted with a weak partial order is approximable within 2-2/(|T| +1) [66]. 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 [400], and not approximable within 5/4 [243]. The same problem without limit on the number of processors, i.e. with , is not approximable within 7/6 [243]. 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) [359]. Generalization where the tasks have lengths l(t) and the processors have speed factors s(i) is approximable within [107].

- Garey and Johnson: SS9

Next: MINIMUM RESOURCE CONSTRAINED SCHEDULING Up: Multiprocessor Scheduling Previous: MINIMUM MULTIPROCESSOR SCHEDULING Index