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

### MINIMUM TWO-PROCESSOR FLOW-SHOP SCHEDULING WITH BATCH SET-UP TIMES

- INSTANCE: Set C of compilers, set J of jobs, for each , which consists of two operations oi,j, i=1,2, a compiler , for each operation oi,j a length and for each a pair of set-up times (s1(c), s2(c)), where .

- SOLUTION: A two-processor flow-shop schedule for J (see MINIMUM FLOW-SHOP SCHEDULING) such that, whenever two operations oi,j and oi,j' with fi(j) < fi(j') are scheduled consecutively (i.e., no other operation oi,j'' has fi(j) < fi(j'') < fi(j')) and have different compilers (i.e., ), then .

- MEASURE: The completion time of the schedule, i.e., .

- Good News: Approximable within 4/3 [97].