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

• INSTANCE: Set C of compilers, set J of jobs, for each $j\in J$, which consists of two operations $o_{i,j}$, i=1,2, a compiler $k(j) \in C$, for each operation $o_{i,j}$ a length $l_{i,j}\in N$ and for each $c\in C$ a pair of set-up times $(s_1(c), s_2(c))$, where $s_i(c)\in Z^+$.

• SOLUTION: A two-processor flow-shop schedule for J (see MINIMUM FLOW-SHOP SCHEDULING) such that, whenever two operations $o_{i,j}$ and $o_{i,j'}$ with $f_i(j) < f_i(j')$ are scheduled consecutively (i.e., no other operation $o_{i,j''}$ has $f_i(j) < f_i(j'') < f_i(j')$) and have different compilers (i.e., $k(j)\neq k(j')$), then $f_i(j') \ge f_i(j) + l_{i,j} + s_i(k(j'))$.

• MEASURE: The completion time of the schedule, i.e., $\max\limits_{j\in J} f_2(j)+l_{2,j}$.

  
  

• Good News: Approximable within 4/3 [105].