SS7 M INIMUM P RECEDENCE C ONSTRAINED S CHEDULING

   
• I NSTANCE : Set T of tasks, each having length l(t)=1 , number m of processors, and a partial order < on T .
• S OLUTION : 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) .
• M EASURE : The finish time for the schedule, i.e., .

• Good News: Approximable within 2-2/|T| [ 247 ].
• Bad News: Not approximable within 4/3 for any [ 249 ].
• 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) [ 43 ]. 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 [ 312 ], and not approximable within 5/4 [ 176 ]. The same problem without limit on the number of processors, i.e. with , is not approximable within 7/6 [ 176 ]. Generalization where the tasks have lengths l(t) and the processors have speed factors s(i) is approximable within [ 76 ].
• Garey and Johnson: SS9