Dominance and Decomposition Heuristics for Single Machine Scheduling

Robert J. Chambers, Robert L. Carraway, Timothy J. Lowe and Thomas L. Morin
Additional contact information
Robert J. Chambers: Emory University, Atlanta, Georgia
Robert L. Carraway: University of Virginia, Charlottesville, Virginia
Timothy J. Lowe: The University of Iowa, Iowa City, Iowa
Thomas L. Morin: Purdue University, West Lafayette, Indiana

Operations Research, 1991, vol. 39, issue 4, 639-647

Abstract: New heuristic dominance rules and a flexible decomposition heuristic are developed for the problem of minimizing weighted tardiness on a single processor. Extensive computational experience demonstrates that, when our new heuristic dominance rules were incorporated into an optimal algorithm, optimal or nearly optimal solutions were obtained quickly. In fact, solution times were orders of magnitude faster than those using the optimal algorithm alone. On larger problems, our decomposition heuristic obtained better solutions than previous heuristics. Furthermore, on 50-job problems our decomposition heuristic obtained an optimal solution over ten times more often on the average than the best competing heuristic (22% versus 2% of the time). Since both our approaches are basically relaxations of optimal solution algorithms, they could easily be adapted for use in the solution of other scheduling problems.

Keywords: production/scheduling; deterministic: dominance and decomposition heuristics; production/scheduling; approximations; heuristic: single machine sequencing (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.4.639 (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:39:y:1991:i:4:p:639-647

Access Statistics for this article

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