Next:
Shop Scheduling
Up:
Multiprocessor Scheduling
Previous:
SS12 MINIMUM WEIGHTED
-
I
NSTANCE
:
Set
T
of tasks, set
P
of 3 processors, and, for each task
, a
length
and a required subset of processors
.
-
S
OLUTION
:
A schedule for
T
, i.e., a starting time function
such
that, for any two tasks
and
with
, either
or
.
-
M
EASURE
:
The makespan of the schedule, i.e.,
.
-
Good News:
Approximable within 7/6 [
131
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997