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

Edwin Tai Chiu Cheng, Z.H. Liu, Y.M. Shafransky

Research output: Journal article publicationJournal articleAcademic researchpeer-review


The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and processing times are one unit.
Original languageEnglish
Pages (from-to)225-229
Number of pages5
JournalJournal of Scheduling
Issue number4
Publication statusPublished - 2001


  • Family scheduling
  • Number of late jobs
  • Strong NP-hardness

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Management Science and Operations Research
  • Engineering(all)

Cite this