Single-machine scheduling to minimize earliness and number of tardy jobs

Edwin Tai Chiu Cheng, H. G. Kahlbacher

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)


This paper considers the problem of assigning a common due-date to a set of simultaneously available jobs and sequencing them on a single machine. The objective is to determine the optimal combination of the common due-date and job sequence that minimizes a cost function based on the assigned due-date, job earliness values, and number of tardy jobs. It is shown that the optimal due-date coincides with one of the job completion times. Conditions are derived to determine the optimal number of nontardy jobs. It is also shown that the optimal job sequence is one in which the nontardy jobs are arranged in nonincreasing order of processing times. An efficient algorithm of O(n log n) time complexity to find the optimal solution is presented and an illustrative example is provided. Finally, several extensions of the model are discussed.
Original languageEnglish
Pages (from-to)563-573
Number of pages11
JournalJournal of Optimization Theory and Applications
Issue number3
Publication statusPublished - 1 Jun 1993
Externally publishedYes


  • early jobs
  • Scheduling
  • sequencing
  • single-machine systems
  • tardy jobs

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics
  • Management Science and Operations Research

Cite this