MINIMUM OPEN-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, i.e., a collection of one-processor schedules $f_i: J\rightarrow N$, $1\le i\le m$, such that $f_i(j)>f_i(j')$ implies $f_i(j) \geq f_i(j')+l_{i,j'}$, such that for each $j\in J$ the intervals $[f_i(j),f_i(j)+l_{i,j})$ are all disjoint.

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

  
  

• Good News: Approximable within 2 [347].

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

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

• Garey and Johnson: SS14