Next: MINIMUM TWO-PROCESSOR FLOW-SHOP SCHEDULING
Up: Shop Scheduling
Previous: MINIMUM OPEN-SHOP SCHEDULING
  Index
- INSTANCE:
Number
of processors, set J of jobs, each
consisting
of m operations oi,j with
(with oi,j to be
executed by processor i), and for each operation a length
.
- SOLUTION:
An open-shop schedule for J (see MINIMUM OPEN-SHOP SCHEDULING) such that,
for each
and
,
.
- MEASURE:
The completion time of the schedule, i.e.,
.
- Good News:
Approximable within m/2 if m is even and within m/2 + 1/6 if
m is odd [96].
- Bad News:
Not approximable within 5/4
for any
[443].
- Comment:
Approximable within 5/3 if m=3 [96].
Variation in which m=2, but the two processors are replaced by
respectively m1 and m2 identical parallel processors, is
approximable within
[95].
- Garey and Johnson: SS15
Viggo Kann
1999-04-22