Next: MINIMUM FLOW-SHOP SCHEDULING
Up: Shop Scheduling
Previous: Shop Scheduling
of processors, set J of jobs, each
of m operations
executed by processor i), and for each operation a length .
An open-shop schedule for J, i.e., a collection of one-processor schedules
such that for each
are all disjoint.
The completion time of the schedule, i.e.,
- Good News:
Approximable within 2 .
- Bad News:
Not approximable within 5/4
Approximable within 3/2 if m=3 .
Variation in which m=2, but the two processors are replaced by
identical parallel processors, is
approximable within 3/2 if
- Garey and Johnson: SS14