MINIMUM FLOW-SHOP SCHEDULING

• INSTANCE: Number $m\in Z^+$ of processors, set J of jobs, each $j\in J$ consisting of m operations $o_{i,j}$ with $1 \leq i \leq m$ (with $o_{i,j}$ to be executed by processor i), and for each operation a length $l_{i,j}\in N$.

• SOLUTION: An open-shop schedule for J (see MINIMUM OPEN-SHOP SCHEDULING) such that, for each $j\in J$ and $1\le i<m$, $f_{i+1}(j)\ge f_i(j)+l_{i,j}$.

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

  
  

• Good News: Approximable within m/2 if m is even and within m/2 + 1/6 if m is odd [104].

• Bad News: Not approximable within 5/4$-\varepsilon$ for any $\varepsilon >0$ [466].

• Comment: Approximable within 5/3 if m=3 [104]. Variation in which m=2, but the two processors are replaced by respectively $m_1$ and $m_2$ identical parallel processors, is approximable within $2-1/{\max(m_1+m_2)}$ [103].

• Garey and Johnson: SS15