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

T. C. E. Cheng and H. G. Kahlbacher

Naval Research Logistics (NRL), 1991, vol. 38, issue 5, 715-720

Abstract: 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.

Date: 1991
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199110)38:53.0.CO;2-6

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:38:y:1991:i:5:p:715-720

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().