- INSTANCE:
Set
*T*of tasks, number*m*of identical processors, for each task a release time and a length . - 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 total flow time for the schedule, i.e.,
.

*Good News:*Approximable within where [349].*Bad News:*Not approximable within for any [349].*Comment:*In the case*m=1*, it is approximable within and it is not approximable within for any [300]. In the preemptive case, that is, in the case a job that is running can be preempted and continue later on any machine, the problem is approximable within and it is not approximable within where [349]. Variation in which all speed factors are 1 and the load is measured using the norm, i.e. , admits a PTAS for any [10].