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

Edwin Tai Chiu Cheng, Zhaohui Liu, Yakov M. Shafransky

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

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
Volume4
Issue number4
DOIs
Publication statusPublished - 1 Dec 2001

Keywords

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

ASJC Scopus subject areas

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

Cite this