Next: MINIMUM PRECEDENCE CONSTRAINED SCHEDULING
Up: Multiprocessor Scheduling
Previous: Multiprocessor Scheduling
  Index
- 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 [348].
- Bad News:
Not approximable within 3/2
for any
[348].
- Comment:
Admits an FPTAS for the variation in which the number of processors m is
constant [261].
Admits a PTAS for the uniform variation, in which l(t,i) is independent
of the processor i [255].
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 [441].
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 [64].
- Garey and Johnson: Generalization of SS8
Next: MINIMUM PRECEDENCE CONSTRAINED SCHEDULING
Up: Multiprocessor Scheduling
Previous: Multiprocessor Scheduling
  Index
Viggo Kann
2000-03-20