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
and
with
,
either
or
.
- MEASURE:
The makespan of the schedule, i.e.,
.
- Good News:
Admits a PTAS [18].
- Comment:
Admits a PTAS even for any fixed number of processors.
Viggo Kann
2000-03-20