×
Bräsel, Heidemarie; Kluge, Dagmar; Werner, Frank

A polynomial algorithm for an open shop problem with unit processing times and tree constraints. (English) Zbl 0833.90066

Discrete Appl. Math. 59, No. 1, 11-21 (1995).
Summary: 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.

Cited in 3 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems
68Q25 Analysis of algorithms and problem complexity

Keywords:

open shop problem; unit processing times; tree constraints; polynomial algorithm
PDF BibTeX XML Cite
\textit{H. Bräsel} et al., Discrete Appl. Math. 59, No. 1, 11--21 (1995; Zbl 0833.90066)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Adiri, I.; Amit, N., Openshop and flowshop scheduling to minimize sum of completion times, Comput. Oper. Res., 11, 275-284 (1984) · Zbl 0608.90050
[2] Bräsel, H., Lateinische Rechtecke und Maschinenbelegung, (Dissertation B (1990), TU Magdeburg)
[3] Bräsel, H.; Kluge, D.; Werner, F., A polynomial algorithm for the \([n/m/O, t_{ ij } = 1\), tree/\(C_{ max } ]\) problem European, J. Oper. Res., 72, 125-134 (1994) · Zbl 0798.90081
[4] Brucker, P.; Jurisch, B.; Jurisch, M., Open shop problems with unit time operations, Z. Oper. Res., 37, 339-354 (1993) · Zbl 0776.90033
[5] Gonzales, T., Unit execution time shop problems, Math. Oper. Res., 7, 57-66 (1982) · Zbl 0499.90047
[6] Lageweg, B. J.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. Rinnooy, Computer aided complexity classification of deterministic scheduling problems, (Report BW 138/81 (1981), Department of Operations Research) · Zbl 0452.90035
[7] Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. Rinnooy; Shmoys, D. B., Sequencing and scheduling: algorithms and complexity, (Report BS-R8909 (1989), Department of Operations Research, Statistics and System Theory)
[8] Liu, C. Y.; Bulfin, R. L., Scheduling open shops with unit execution times to minimize functions of due dates, Oper. Res., 36, 553-559 (1988) · Zbl 0652.90063
[9] McNaughton, R., Scheduling with deadlines and loss functions, Management Sci., 6, 1-2 (1959) · Zbl 1047.90504
[10] Tanaev, V. S.; Sotskov, Y. N.; Strusewich, V. A., Theory of Scheduling-Multistage Systems (1989), Nauka: Nauka Moscow, (in Russian)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.