Analyzing Basic Representation Choices in Oversubscribed Scheduling Problems

Laurence Kramer, Laura Barbulescu, and Stephen Smith
Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Application (MISTA-07), August, 2007.


Download
  • Adobe portable document format (pdf) (157KB)
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
Both direct schedule representations as well as indirect permutation-based representations in conjunction with schedule builders are successfully employed in oversubscribed scheduling research. Recent work has indicated that in some domains, searching the space of permutations as opposed to the schedule space itself can be more productive in maximizing the number of scheduled tasks. On the other hand, research in domains where task priority is treated as a hard constraint has shown the effectiveness of local repair methods that operate directly on the schedule representation. In this paper, we investigate the comparative leverage provided by techniques that exploit these alternative representations (and search spaces) in this latter oversubscribed scheduling context. We find that an inherent difficulty in specifying a permutation-based search procedure is making the tradeoff in guaranteeing that priority is enforced while giving the search sufficient flexibility to progress. Nonetheless, with some effort spent in tuning the move operator, we show that a permutation-space technique can perform quite well on this class of problem in cases of low oversubscription and in fact was able to find new optimal solutions to a few previously published benchmark problems. Not surprisingly, the permutation-space search does not perform as well as the schedule-space search in terms of maintaining schedule stability.

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: 8

Text Reference
Laurence Kramer, Laura Barbulescu, and Stephen Smith, "Analyzing Basic Representation Choices in Oversubscribed Scheduling Problems," Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Application (MISTA-07), August, 2007.

BibTeX Reference
@inproceedings{Kramer_2007_5850,
   author = "Laurence Kramer and Laura Barbulescu and Stephen Smith",
   title = "Analyzing Basic Representation Choices in Oversubscribed Scheduling Problems",
   booktitle = "Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Application (MISTA-07)",
   month = "August",
   year = "2007",
}