SS8 M INIMUM R ESOURCE C ONSTRAINED S CHEDULING

   
• I NSTANCE : 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 .
• S OLUTION : 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
  
  
• M EASURE : The makespan of the schedule, i.e., .

• Good News: Approximable within 2 [ 120 ].
• 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 [ 334 ]. 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 [ 262 ]. 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 [ 328 ].
• Garey and Johnson: SS10