The complexity of scheduling job families about a common due date

Research output: Contribution to journalArticlepeer-review

42 Scopus citations


Family scheduling problems are characterized by a setup time structure where setups are only required between jobs from different families. We consider the problem of scheduling job families on parallel machines to minimize weighted deviation about a common due date. Various special cases of this problem have been considered in the literature. This note summarizes known complexity results and introduces new complexity results. We show that the total earliness/tardiness problem is unary NP-hard when the number of machines and families are arbitrary, thus generalizing an earlier result and answering a longstanding open question in the literature.

Original languageEnglish (US)
Pages (from-to)65-74
Number of pages10
JournalOperations Research Letters
Issue number2
StatePublished - Feb 1997
Externally publishedYes


  • Analysis of algorithms
  • Computational complexity
  • Job families
  • Multiple machine
  • Nonregular performance measure
  • Production/scheduling

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


Dive into the research topics of 'The complexity of scheduling job families about a common due date'. Together they form a unique fingerprint.

Cite this