Next: MINIMUM PREEMPTIVE SCHEDULING WITH Up: Multiprocessor Scheduling Previous: MINIMUM PRECEDENCE CONSTRAINED SCHEDULING Index

### MINIMUM RESOURCE CONSTRAINED SCHEDULING

- INSTANCE: Set T of tasks each having length l(t), number m of processors, number r of resources, resource bounds bi, , and resource requirement ri(t), , 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 [169].

- 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 [431]. 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 [344]. 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 [425].

- Garey and Johnson: SS10

Next: MINIMUM PREEMPTIVE SCHEDULING WITH Up: Multiprocessor Scheduling Previous: MINIMUM PRECEDENCE CONSTRAINED SCHEDULING Index