Next:
SS7 MINIMUM PRECEDENCE
Up:
Multiprocessor Scheduling
Previous:
Multiprocessor Scheduling
-
I
NSTANCE
:
Set
T
of tasks, number
m
of processors, length
for each
task
and processor
.
-
S
OLUTION
:
An
m
-processor schedule for
T
, i.e., a function
.
-
M
EASURE
:
The finish time for the schedule, i.e.,
.
-
Good News:
Approximable within 2 [
251
].
-
Bad News:
Not approximable within 3/2
for any
[
251
].
-
Comment:
Admits an FPTAS for the variation in which the number of processors
m
is
constant [
178
].
Admits a PTAS for the uniform variation, in which
l(t,i)
is independent
of the processor
i
[
173
].
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 [
321
].
-
Garey and Johnson:
SS8
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997