The mixed shop scheduling problem

In this paper, we consider a two-machine shop scheduling problem consisting of two disjoint job subsets F and O. F is a set of the flow shop type jobs, while O is a set of the open shop type jobs. Our objective is to find the schedule minimizing the maximum completion time. For the case that O is empty, this problem reduces to a two-machine flow shop scheduling problem for which Johnson developed an optimal algorithm. Also for the case that F is empty, the problem reduces to a two-machine open shop scheduling problem for which there is an optimal algorithm developed by Gonzalez and Sahni. While for the case that both F and O are not empty, the situation is complicated in the sense that the preceding two cases are not extensible to our case. We give the optimal algorithm for our nontrivial case