Next: Shop Scheduling
Up: Multiprocessor Scheduling
Previous: MINIMUM WEIGHTED COMPLETION TIME
  Index
- 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.
Viggo Kann
1999-04-22