A polynomial algorithm for the [n/m/0,tij=1, tree/Cmax] open shop problem

In this paper the authors consider the open shop problem with unit processing times and tree constraints among the jobs. The objective is to minimize the schedule length Cmax. The complexity of this problem was open. The autors present a polynomial algorithm which decomposes the problem into subproblems by means of the occurrence of unavoidable idle times. They consider two types of subproblems which can be solved by constructing special latin rectangles.