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

### MINIMUM MULTIPROCESSOR SCHEDULING

- INSTANCE: Set T of tasks, number m of processors, length for each task and processor .

- SOLUTION: An m-processor schedule for T, i.e., a function .

- MEASURE: The finish time for the schedule, i.e., .

- Good News: Approximable within 2 [332].

- Bad News: Not approximable within 3/2 for any [332].

- Comment: Admits an FPTAS for the variation in which the number of processors m is constant [244]. Admits a PTAS for the uniform variation, in which l(t,i) is independent of the processor i [238]. A variation in which, for each task t and processor i, a cost c(t,i) is given in input and the goal is to minimize a weighted sum of the finish time and the cost is approximable within 2 [418]. Variation in which each task has a nonnegative penalty and the objective is to minimize the finish time for accepted jobs plus the sum of the penalties of rejected jobs, is approximable within 2-1/m and admits an FPTAS for fixed m [60].

- Garey and Johnson: Generalization of SS8

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