A proof for the longest‐job‐first policy in one‐machine scheduling

Edwin Tai Chiu Cheng, H. G. Kahlbacher

Research output: Journal article publicationJournal articleAcademic researchpeer-review

40 Citations (Scopus)


We consider a one‐machine scheduling problem with earliness and tardiness penalties. All jobs are assigned a common due date and the objective is to minimize the total penalty due to job earliness and tardiness. We are interested in finding the optimal combination of the common due‐date value and the job sequence. Despite the fact that this problem in general is very hard to solve, we prove that there exists at least a common property for all optimal solutions: The first job in an optimal sequence is one of the longest jobs. We also prove that this property holds for a general class of unimodal penalty functions.
Original languageEnglish
Pages (from-to)715-720
Number of pages6
JournalNaval Research Logistics (NRL)
Issue number5
Publication statusPublished - 1 Jan 1991
Externally publishedYes

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


Dive into the research topics of 'A proof for the longest‐job‐first policy in one‐machine scheduling'. Together they form a unique fingerprint.

Cite this