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 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, i.e., a collection of one-processor schedules
,
,
such that
fi(j)>fi(j')
implies
,
such that for each
the
intervals
[fi(j),fi(j)+li,j) are all disjoint.
- MEASURE:
The completion time of the schedule, i.e.,
.
- Good News:
Approximable within 2 [331].
- Bad News:
Not approximable within 5/4
for any
[443].
- Comment:
Approximable within 3/2 if m=3 [98].
Variation in which m=2, but the two processors are replaced by
respectively m1 and m2 identical parallel processors, is
approximable within 3/2 if
,
5/3 if m1=m2=2 and
otherwise [99].
- Garey and Johnson: SS14
Viggo Kann
1999-04-22