- INSTANCE:
Set
*T*of tasks, number*m*of identical processors, for each task a release time , a length , and a weight . - SOLUTION:
An
*m*-processor schedule for*T*that obeys the resource constraints and the release times, i.e., a function such that, for all and for each processor*i*, if*S(u,i)*is the set of tasks*t*for which and , then and for each task*t*, . - MEASURE:
The weighted sum of completion times, i.e.
.

*Good News:*Approximable within 2 [432].*Comment:*The preemptive case is also approximable within 2 [401]. Generalization to unrelated processors (where the length of a task also depends in the processor) is approximable within 2 for any for both nonpreemptive and preemptive scheduling [432]. Restriction (of the nonpreemptive case) where*r(t)=0*for all*t*is approximable within 3/2 [433]. Generalization where there are precedence constraints on*T*that must be obeyed in the solution is approximable within 5.33 [96].*Garey and Johnson:*SS13