Next: MINIMUM JOB SHOP SCHEDULING
Up: Shop Scheduling
Previous: MINIMUM FLOW-SHOP SCHEDULING
  Index
- INSTANCE:
Set C of compilers, set J of jobs, for each
,
which consists of two operations oi,j, i=1,2, a compiler
,
for each operation oi,j a length
and for each
a pair of set-up times
(s1(c), s2(c)), where
.
- SOLUTION:
A two-processor flow-shop schedule for J (see MINIMUM FLOW-SHOP SCHEDULING)
such that, whenever two operations oi,j and oi,j' with
fi(j) < fi(j') are scheduled consecutively (i.e., no other operation
oi,j'' has
fi(j) < fi(j'') < fi(j')) and have different compilers
(i.e.,
), then
.
- MEASURE:
The completion time of the schedule, i.e.,
.
- Good News:
Approximable within 4/3 [97].
Viggo Kann
1999-04-22