The Robotics Institute

Carnegie Mellon Robotics Institute

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",
}

The Robotics Institute

Menu