A POLYNOMIAL ALGORITHM FOR THE [N M/O, T(IJ) = 1, TREE/CMAX] OPEN SHOP PROBLEM/

Authors
BRASEL H KLUGE D WERNER F
Citation
H. Brasel et al., A POLYNOMIAL ALGORITHM FOR THE [N M/O, T(IJ) = 1, TREE/CMAX] OPEN SHOP PROBLEM/, European journal of operational research, 72(1), 1994, pp. 125-134
Citations number
8
Categorie Soggetti
Management,"Operatione Research & Management Science
Journal title
European journal of operational research → ACNP
ISSN journal
03772217
Volume
72
Issue
1
Year of publication
1994
Pages
125 - 134
Database
ISI
SICI code
0377-2217(1994)72:1<125:APAFT[>2.0.ZU;2-F
Abstract
In this paper we consider the open shop problem with unit processing t imes and tree constraints among the jobs. The objective is to mimimize the schedule length C(max). The complexity of this problem was open. We present a polynomial algorithm which decomposes the problem into su bproblems by means of the occurrence of unavoidable idle times. We con sider two types of subproblems which can be solved by constructing spe cial latin rectangles.