Minimizing the number of late jobs on unrelated machines

Jianzhong Du, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


We consider the problem of preemptively scheduling a set of independent jobs with release times on an arbitrary number of unrelated machines so as to minimize the number of late jobs. We show that the problem is NP-hard in the strong sense, giving the first strong NP-hardness result for this problem.

Original languageEnglish (US)
Pages (from-to)153-158
Number of pages6
JournalOperations Research Letters
Issue number3
StatePublished - Apr 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


  • due date
  • late job
  • preemptive scheduling
  • release time
  • strong NP-hardness
  • unrelated machines


Dive into the research topics of 'Minimizing the number of late jobs on unrelated machines'. Together they form a unique fingerprint.

Cite this