Next: MINIMUM 3-DEDICATED PROCESSOR SCHEDULING
Up: Multiprocessor Scheduling
Previous: MINIMUM PARALLEL PROCESSOR TOTAL
  Index
- INSTANCE:
Set T of tasks, number m of identical processors, for each task
a release time
,
a length
,
and a weight
.
- SOLUTION:
An m-processor schedule for T that obeys the resource constraints
and the release times, i.e., a function
such that, for all
and for each processor i, if
S(u,i) is the set of tasks t for which
and
,
then
and for each task
t,
.
- MEASURE:
The weighted sum of completion times, i.e.
.
- Good News:
Approximable within 2 [432].
- Comment:
The preemptive case is also approximable within 2 [401].
Generalization to unrelated processors (where the length of
a task also depends in the processor) is approximable within
2
for any
for both nonpreemptive
and preemptive scheduling [432].
Restriction (of the nonpreemptive case) where r(t)=0 for all t
is approximable within 3/2 [433].
Generalization where there are precedence
constraints on T that must be obeyed in the solution is approximable
within 5.33 [96].
- Garey and Johnson: SS13
Next: MINIMUM 3-DEDICATED PROCESSOR SCHEDULING
Up: Multiprocessor Scheduling
Previous: MINIMUM PARALLEL PROCESSOR TOTAL
  Index
Viggo Kann
2000-03-20