Next:
SS17 MINIMUM JOB
Up:
Shop Scheduling
Previous:
SS15 MINIMUM FLOW-SHOP
-
I
NSTANCE
:
Set
C
of compilers, set
J
of jobs, for each
,
which consists of two operations
,
i=1,2
, a compiler
,
for each operation
a length
and for each
a pair of set-up times
, where
.
-
S
OLUTION
:
A two-processor flow-shop schedule for
J
(see M
INIMUM
F
LOW
-S
HOP
S
CHEDULING
)
such that, whenever two operations
and
with
are scheduled consecutively (i.e., no other operation
has
) and have different compilers
(i.e.,
), then
.
-
M
EASURE
:
The completion time of the schedule, i.e.,
.
-
Good News:
Approximable within 4/3 [
69
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997