Two machine open shop scheduling problems with bi-criteria (Q1331894)

A bi-criteria two machine open shop scheduling problem is considered. The processing of any operation can be interrupted. The two criteria to be minimized are maximum completion time \(C_{\max}\) and maximum lateness \(L_{\max}\). Two basic single criterion problems have already been investigated. For the \(C_{\max}\) criterion the problem was solved by \textit{T. Gonzalez} and \textit{S. Sahni} [J. Assoc. Comput. Machin. 23, 665- 679 (1976; Zbl 0343.68031)], while the \(L_{\max}\) criterion was considered by \textit{E. L. Lawler}, \textit{J. K. Lenstra} and \textit{A. H. G. Rinnooy Kan} [Math. Oper. Res. 6, 153-158 (1981; Zbl 0496.90047)]. These well-known results are used in the paper. It is shown that two cases may occur. In the first case, there exists a unique optimal solution, both criteria being simultaneously optimized. In the second case, nondominated solutions \((C_{\max}, L_{\max})\) lie on the line segment \(L_{\max}= F- C_{\max}\), where \(F\) is computed in \(O(n^2)\) time. In both cases a corresponding schedule can be constructed in \(O(n)\) time.