Understanding Performance Tradeoffs in Algorithms for Solving Oversubscribed Scheduling

Laurence Kramer, Laura Barbulescu, and Stephen Smith
Proceedings 22nd Conference on Artificial Intelligence (AAAI-07), July, 2007.


Download
  • Adobe portable document format (pdf) (171KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
In recent years, planning and scheduling research has paid increasing attention to problems that involve resource oversubscription, where cumulative demand for resources outstrips their availability and some subset of goals or tasks must be excluded. Two basic classes of techniques to solve oversubscribed scheduling problems have emerged: searching directly in the space of possible schedules and searching in an alternative space of task permutations (by relying on a schedule builder to provide a mapping to schedule space). In some problem contexts, permutation-based search methods have been shown to outperform schedule-space search methods, while in others the opposite has been shown to be the case. We consider two techniques for which this behavior has been observed: TaskSwap (TS), a schedule-space repair search procedure, and Squeaky Wheel Optimization (SWO), a permutation-space scheduling procedure. We analyze the circumstances under which one can be expected to dominate the other. Starting from a real-world scheduling problem where SWO has been shown to outperform TS, we construct a series of problem instances that increasingly incorporate characteristics of a second real-world scheduling problem, where TS has been found to outperform SWO. Experimental results provide insights into when schedule-space methods and permutation-based methods may be most appropriate.

Keywords
scheduling, search

Notes
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory
Associated Project(s): AMC Barrelmaster Scheduling
Number of pages: 6

Text Reference
Laurence Kramer, Laura Barbulescu, and Stephen Smith, "Understanding Performance Tradeoffs in Algorithms for Solving Oversubscribed Scheduling," Proceedings 22nd Conference on Artificial Intelligence (AAAI-07), July, 2007.

BibTeX Reference
@inproceedings{Kramer_2007_5822,
   author = "Laurence Kramer and Laura Barbulescu and Stephen Smith",
   title = "Understanding Performance Tradeoffs in Algorithms for Solving Oversubscribed Scheduling",
   booktitle = "Proceedings 22nd Conference on Artificial Intelligence (AAAI-07)",
   month = "July",
   year = "2007",
}