Next: Shop Scheduling Up: Multiprocessor Scheduling Previous: MINIMUM WEIGHTED COMPLETION TIME Index

### MINIMUM 3-DEDICATED PROCESSOR SCHEDULING

- INSTANCE: Set T of tasks, set P of 3 processors, and, for each task , a length and a required subset of processors .

- SOLUTION: A schedule for T, i.e., a starting time function such that, for any two tasks t1 and t2 with , either s(t1)+l(t1) < s(t2) or s(t2)+l(t2) < s(t1).

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

- Good News: Admits a PTAS [17].

- Comment: Admits a PTAS even for any fixed number of processors.