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

### MINIMUM FLOW-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 (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