Next:
SS13 MINIMUM 3-DEDICATED
Up:
Multiprocessor Scheduling
Previous:
SS11 MINIMUM PARALLEL
-
I
NSTANCE
:
Set
T
of tasks, number
m
of identical processors, for each task
a release time
and a length
.
-
S
OLUTION
:
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
|S(u,i)| = 1
and for each task
t
,
.
-
M
EASURE
:
The weighted sum of completion times, i.e.
.
-
Good News:
Approximable within 2.85 [
65
].
-
Comment:
The preemptive case is approximable within 2 [
291
].
Generalization (of the nonpreemptive case) where there are precedence
constraints on
T
that must be obeyed in the solution is approximable
within 5.33 [
62
].
-
Garey and Johnson:
SS13
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997