- INSTANCE:
Set
*T*of tasks each having length*l(t)*, number*m*of processors, number*r*of resources, resource bounds , , and resource requirement , , for each task*t*and resource*i*. - SOLUTION:
An
*m*processor schedule for*T*that obeys the resource constraints, i.e., a function such that for all , if*S(u)*is the set of tasks*t*for which , then and for each resource*i*

- MEASURE:
The makespan of the schedule, i.e.,
.

*Good News:*Approximable within 2 [181].*Comment:*Note that the restriction in which there is only one resource, i.e., the available processors, is identical to minimizing the makespan of the schedule of parallel tasks on*m*processors. In this case, minimizing the average response time, i.e., is approximable within 32 [454]. The further variation in which each task can be executed by any number of processors and the length of a task is a function of the number of processors allotted to it is also approximable [363]. Variation in which every task is of length 1 and has an integer ready-time, which means that it cannot be processed before its ready-time, is approximable [448].*Garey and Johnson:*SS10