Maximizing Flexibility: A Retraction Heuristic for Oversubscribed Scheduling Problems

Laurence Kramer and Stephen Smith
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, August, 2003.


Download
  • Adobe portable document format (pdf) (112KB)
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 this paper we consider the solution of scheduling problems that are inherently over-subscribed. In such problems, there are always more tasks to execute within a given time frame than available resource capacity will allow, and hence decisions must be made about which tasks should be included in the schedule and which should be excluded. We adopt a controlled, iterative repair search approach, and focus on improving the results of an initial priority-driven solution generation procedure. Central to our approach is a new retraction heuristic, termed max-flexibility, which is responsible for identifying which tasks to (temporarily) retract from the schedule for reassignment in an effort to incorporate additional tasks into the schedule. The max-flexibility heuristic chooses those tasks that have maximum flexibility for assignment within their feasible windows. We empirically evaluate the performance of max-flexibility using problem data and the basic scheduling procedure from a fielded airlift mission scheduling application. We show that it produces better improvement results than two contention-based retraction heuristics, including a variant of min-conflicts, with significantly less search and computational cost.

Keywords
scheduling, heuristics, constraint satisfaction

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
Note: prepublication copy - Copyright International Joint Conference On Artificial Intelligence, Inc.

Text Reference
Laurence Kramer and Stephen Smith, "Maximizing Flexibility: A Retraction Heuristic for Oversubscribed Scheduling Problems," Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, August, 2003.

BibTeX Reference
@inproceedings{Kramer_2003_4373,
   author = "Laurence Kramer and Stephen Smith",
   title = "Maximizing Flexibility: A Retraction Heuristic for Oversubscribed Scheduling Problems",
   booktitle = "Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence",
   month = "August",
   year = "2003",
   Notes = "prepublication copy - Copyright International Joint Conference On Artificial Intelligence, Inc."
}