Next: MINIMUM PARALLEL PROCESSOR TOTAL
Up: Multiprocessor Scheduling
Previous: MINIMUM PREEMPTIVE SCHEDULING WITH
  Index
- INSTANCE:
Set T of tasks, number m of processors, for each task
a length
,
and for each processor
a speed factor
such that s(1)=1 and
for every i.
- SOLUTION:
An m-processor schedule for T, i.e., a function
.
- MEASURE:
The finish time for the schedule, i.e.,
.
- Good News:
Admits a PTAS [256].
- Bad News:
Does not admit an FPTAS [256].
- Comment:
Admits an FPTAS for the variation in which the number of processors m is
constant [261].
Viggo Kann
2000-03-20