A POLYNOMIAL ALGORITHM FOR AN OPEN SHOP PROBLEM WITH UNIT PROCESSING TIMES AND TREE CONSTRAINTS

Authors
BRASEL H KLUGE D WERNER F
Citation
H. Brasel et al., A POLYNOMIAL ALGORITHM FOR AN OPEN SHOP PROBLEM WITH UNIT PROCESSING TIMES AND TREE CONSTRAINTS, Discrete applied mathematics, 59(1), 1995, pp. 11-21
Citations number
10
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
59
Issue
1
Year of publication
1995
Pages
11 - 21
Database
ISI
SICI code
Abstract
In this paper we consider the open shop problem with unit processing t imes and tree constraints (outtree) between the jobs. The complexity o f this problem was open. We present a polynomial algorithm which decom poses the problem into subproblems by means of the occurrence of unavo idable idle time. Each subproblem can be solved on the base of an algo rithm for the corresponding open shop problem without tree constraints .