Sequencing to Minimize the Maximum Job Cost

Clyde L. Monma
Additional contact information
Clyde L. Monma: Bell Laboratories, Holmdel, New Jersey

Operations Research, 1980, vol. 28, issue 4, 942-951

Abstract: Consider the problem of sequencing a set of jobs in order to minimize the maximum job cost. Examples of such a problem include the one-machine maximum lateness and maximum earliness problems, the maximum cumulative cost problem, and Johnson's two-machine maximum completion time flow-shop problem. The relationships among various maximum cost problems are explored. One such result is that the first three examples cited above are special cases of the final one; even though they appear to be quite different on the surface. A consequence of this fact is that the two-machine maximum completion time flow-shop problem is NP-hard when general precedence constraints are allowed. A maximum cost problem is formulated and shown to generalize the above-mentioned problems. An extension of Lawler's back-to-front sequencing algorithm efficiently solves the unconstrained version of this problem. Finally, two insertion properties, which were motivated by Smith's adjacent pairwise interchange (API) property, lead to efficient algorithms for sequencing with general precedence constraints.

Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.28.4.942 (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:28:y:1980:i:4:p:942-951

Access Statistics for this article

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