Exploiting Problem Structure in Scheduling
Abstract
Many scheduling algorithms have been developed, but surprisingly there is little guidance as to which method to use for a given application. This project addressed this gap between the science and practice of scheduling by developing a methodology for assessing performance and applying it to two problems: scheduling a manufacturing flow shop and scheduling access requests for the Air Force satellite control network. We found flaws in the conventional practice of evaluating scheduling algorithms. In particular, performance on popular benchmark problems does not generalize to problems with realistic problem structure. Additionally, we found that the performance of algorithms previously deemed to be state-of-the-art may be dominated by much simpler and computationally faster algorithms. We were able to explain the differences in performance by characteristic patterns in the search spaces of structured problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 02, 2000
- Accession Number
- ADA388167
Entities
People
- Adele Howe
- L. D. Whitley
Organizations
- Colorado State University