Next: MINIMUM FLOW-SHOP SCHEDULING Up: Shop Scheduling Previous: Shop Scheduling Index

### MINIMUM OPEN-SHOP SCHEDULING

- 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