On complexity of minimizing weighted number of late jobs in unit time open shops. (English) Zbl 0872.90047
Summary: We show that the problem of minimizing the weighted number of late jobs in open shop with given release dates and unit time operations is strongly \({\mathcal N}{\mathcal P}\)-hard. The complexity status of this problem was unknown.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C60 | Abstract computational complexity for mathematical programming problems |
Keywords:
weighted number of late jobs; open shop; release dates; unit time operations; \({\mathcal N}{\mathcal P}\)-hardReferences:
| [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] | Brucker, P.; Jurisch, B.; Tautenhahn, T.; Werner, F., Scheduling unit time open shops to minimize the weighted number of late jobs, Oper. Res. Lett., 14, 245-250 (1993) · Zbl 0793.90028 |
| [3] | Graham, R. E.; Lawler, E. L.; Lenstra, J. K.; Kann, A. H.G. Rinnooy, 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 (1985) · Zbl 0652.90063 |
| [6] | Tautenhahn, T., Open-shop-Probleme mit Einheitsbearbeitungszeiten, Thesis (1993), Magdeburg |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
