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 f(t)2=i, then |S(u,i)| = 1 and for each task
t,
.
- MEASURE:
The total flow time for the schedule, i.e.,
.
- Good News:
Approximable within
where n=|T|
[333].
- Bad News:
Not approximable within
for any
[333].
- Comment:
In the case m=1, it is approximable within
and it is not
approximable within
for any
[285]. 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
[333].
Variation in which all speed factors are 1 and the load is measured using the
Lp 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
1999-04-22