Journal article
Dominance and Decomposition Heuristics for Single Machine Scheduling
Operations research, Vol.39(4), pp.639-647
07/01/1991
DOI: 10.1287/opre.39.4.639
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.
Details
- Title: Subtitle
- Dominance and Decomposition Heuristics for Single Machine Scheduling
- Creators
- Robert J. Chambers - Emory UniversityRobert L. Carraway - University of VirginiaTimothy J. Lowe - University of IowaThomas L. Morin - Purdue University West Lafayette
- Resource Type
- Journal article
- Publication Details
- Operations research, Vol.39(4), pp.639-647
- DOI
- 10.1287/opre.39.4.639
- ISSN
- 0030-364X
- eISSN
- 1526-5463
- Number of pages
- 9
- Language
- English
- Date published
- 07/01/1991
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963191802771
Metrics
1 Record Views