Open-shop scheduling for unit jobs under precedence constraints (Q5919300)

The authors present approximation algorithms for the open-shop scheduling problem \(O | p_{ij} = 1, \prec | C_{\max} \) with unit processing times and arbitrary precedence constraints minimizing the makespan. At first, for the problem \(O3 | p_{ij} = 1, \prec | C_{\max} \) with three machines, a polynomial-time 5/3-approximation algorithm is proposed which is then improved to have approximation ratio 4/3. Finally, the idea is generalized to the \(m\)-machine case leading to the approximation ratio of \(2-\frac{2}{m}\).