Next: MINIMUM FLOW-SHOP SCHEDULING
Up: Shop Scheduling
Previous: Shop Scheduling
  Index
- INSTANCE:
Number
of processors, set J of jobs, each
consisting
of m operations
with
(with
to be
executed by processor i), and for each operation a length
.
- SOLUTION:
An open-shop schedule for J, i.e., a collection of one-processor schedules
,
,
such that
implies
,
such that for each
the
intervals
are all disjoint.
- MEASURE:
The completion time of the schedule, i.e.,
.
- Good News:
Approximable within 2 [347].
- Bad News:
Not approximable within 5/4
for any
[466].
- Comment:
Approximable within 3/2 if m=3 [106].
Variation in which m=2, but the two processors are replaced by
respectively
and
identical parallel processors, is
approximable within 3/2 if
,
5/3 if
and
otherwise [107].
- Garey and Johnson: SS14
Viggo Kann
2000-03-20