Next:
SS11 MINIMUM PARALLEL
Up:
Multiprocessor Scheduling
Previous:
SS9 MINIMUM PREEMPTIVE
SS10 M
INIMUM
M
ULTIPROCESSOR
S
CHEDULING
WITH
S
PEED
F
ACTORS
I
NSTANCE
: Set
T
of tasks, number
m
of processors, for each task
a length
, and for each processor
a speed factor
such that
s(1)=1
and
for every
i
.
S
OLUTION
: An
m
-processor schedule for
T
, i.e., a function
.
M
EASURE
: The finish time for the schedule, i.e.,
.
Good News:
Admits a PTAS [
174
].
Bad News:
Does not admit an FPTAS [
174
].
Comment:
Admits an FPTAS for the variation in which the number of processors
m
is constant [
178
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
a length
, and for each processor
a speed factor
such that
s(1)=1
and
for every
i
.
.
.