A polynomial algorithm for an open shop problem with unit processing times and tree constraints

AbstractIn this paper we consider the open shop problem with unit processing times and tree constraints (outtree) between the jobs. The complexity of this problem was open. We present a polynomial algorithm which decomposes the problem into subproblems by means of the occurrence of unavoidable idle time. Each subproblem can be solved on the base of an algorithm for the corresponding open shop problem without tree constraints