Next: MINIMUM WEIGHTED COMPLETION TIME
Up: Multiprocessor Scheduling
Previous: MINIMUM MULTIPROCESSOR SCHEDULING WITH
  Index
- INSTANCE:
Set T of tasks, number m of identical processors, for each task
a release time
and a length .
- 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 total flow time for the schedule, i.e.,
.
- Good News:
Approximable within
where
[349].
- Bad News:
Not approximable within
for any
[349].
- Comment:
In the case m=1, it is approximable within
and it is not
approximable within
for any
[300]. In the preemptive case, that is, in the case a job
that is running can be preempted and continue later on any machine,
the problem is approximable within
and it is not
approximable within
where
[349].
Variation in which all speed factors are 1 and the load is measured using the
norm, i.e.
,
admits a PTAS for any
[10].
Next: MINIMUM WEIGHTED COMPLETION TIME
Up: Multiprocessor Scheduling
Previous: MINIMUM MULTIPROCESSOR SCHEDULING WITH
  Index
Viggo Kann
2000-03-20