A polynomially solvable case of the two-stage open shop problem for three machines (Q2729351)

The authors study the two-stage open shop problem for three machines with the test of minimum length scheduling. This problem is a restriction of the classical three-machine open shop problem [see \textit{T.~Gonzalez} and \textit{S.~Sahni}, J. Assoc. Comput. Mach. 23, No. 4, 665-679 (1976; Zbl 0343.68031)] in the case of two operations. The authors prove that the problem under consideration is polynomially solvable in the case when \(L_{\max}\geq 3p_{\max}\). Here \(L_{\max}\) and \(p_{\max}\) denote the maximal machine loading and maximal duration of operation. Moreover, the optimal length scheduling equals \(L_{\max}\).NEWLINENEWLINENEWLINEThe authors note that the question on the complexity for the problem is still open.