×
Brucker, Peter; Jurisch, Bernd; Tautenhahn, Thomas; Werner, Frank

Scheduling unit time open shops to minimize the weighted number of late jobs. (English) Zbl 0793.90028

Oper. Res. Lett. 14, No. 5, 245-250 (1993).
Summary: We present a polynomial algorithm for the problem of scheduling an open shop with unit time operations for a fixed number of machines such that the weighted number of late jobs is minimized. The algorithm is based on dynamic programming. The complexity of this problem was unknown for open shops with more than two machines.

Cited in 6 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
90C60 Abstract computational complexity for mathematical programming problems

Keywords:

unit processing times; polynomial algorithm; open shop; fixed number of machines; weighted number of late jobs
PDF BibTeX XML Cite
\textit{P. Brucker} et al., Oper. Res. Lett. 14, No. 5, 245--250 (1993; Zbl 0793.90028)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Brucker, P.; Jurisch, B.; Jurisch, M., Open shop problems with unit time operations, Z. Oper. Res., 37, 59-73 (1993) · Zbl 0776.90033
[2] Gonzalez, T.; Sahni, S., Open-Shop Scheduling to Minimize Finish Time, J. ACM, 23, 665-680 (1976) · Zbl 0343.68031
[3] Graham, R. E.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[4] Kubiak, W.; Sriskandarajah, C.; Zaras, K., A note on the complexity of open-shop scheduling problems, INFOR, 29, 284-294 (1991) · Zbl 0778.90027
[5] 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
[6] Tautenhahn, T., Scheduling unit time openshops with deadlines, Oper. Res. (1992), to appear
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.