One-Machine Sequencing to Minimize Certain Functions of Job Tardiness

Hamilton Emmons
Additional contact information
Hamilton Emmons: Cornell University, Ithaca, New York

Operations Research, 1969, vol. 17, issue 4, 701-715

Abstract: This paper first considers the problem of sequencing n jobs on one machine to minimize total tardiness. It proves theorems that establish the relative order in which pairs of jobs are processed in an optimal schedule; frequently they permit the jobs to be completely ordered, thus solving the problem without any searching. In particular, corollaries establish more general conditions than are currently recognized under which sequencing in order of nondecreasing processing times and sequencing in order of nondecreasing due dates are optimal. In general, even large problems may be at least partially ordered to the point that very few schedules remain to be searched. These results are then partly extended to the more general criterion of minimizing a sum of identical, convex, nondecreasing functions of job tardiness, and an efficient algorithm is proposed.

Date: 1969
References: Add references at CitEc
Citations: View citations in EconPapers (49)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.17.4.701 (application/pdf)

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:inm:oropre:v:17:y:1969:i:4:p:701-715

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().