| Article ID: | iaor19971038 |
| Country: | Netherlands |
| Volume: | 59 |
| Issue: | 1 |
| Start Page Number: | 11 |
| End Page Number: | 21 |
| Publication Date: | Apr 1995 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Werner F., Brsel H., Kluge D. |
| Keywords: | scheduling |
In this paper the authors consider the optn shop problem with unit processing times and tree constarints (outtree) between the jobs. The complexity of this problem was open. The authors 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.