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
,
i=1,2, a compiler
,
for each operation
a length
and for each
a pair of set-up times
,
where
.
- SOLUTION:
A two-processor flow-shop schedule for J (see MINIMUM FLOW-SHOP SCHEDULING)
such that, whenever two operations
and
with
are scheduled consecutively (i.e., no other operation
has
)
and have different compilers
(i.e.,
), then
.
- MEASURE:
The completion time of the schedule, i.e.,
.
- Good News:
Approximable within 4/3 [105].
Viggo Kann
2000-03-20