A note on the complexity of family scheduling to minimize the number of late jobs

Citation
Tce. Cheng et al., A note on the complexity of family scheduling to minimize the number of late jobs, J SCHED, 4(4), 2001, pp. 225-229
Citations number
6
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Engineering Management /General
Journal title
JOURNAL OF SCHEDULING
ISSN journal
1094-6136 → ACNP
Volume
4
Issue
4
Year of publication
2001
Pages
225 - 229
Database
ISI
SICI code
1094-6136(200107/08)4:4<225:ANOTCO>2.0.ZU;2-G
Abstract
The single-machine family scheduling problem of minimizing the number of la te jobs has been known to be NP-hard, but whether it is NP-hard in the stro ng sense is cited as an open problem in several reviews. In this note, we p rove that this problem is strongly NP-hard even if all set-up times and pro cessing times are one unit. Copyright (C) 2001 John Wiley & Sons, Ltd.