Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems

Laurence Kramer and Stephen Smith
Proceedings 15th International Conference on Automated Planning and Scheduling, July, 2005.


Download
  • Adobe portable document format (pdf) (189KB)
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 reconsider a "task-swapping" procedure for improving schedules in the face of resource oversubscription. Prior work has demonstrated that use of a retraction heuristic to determine which tasks to rearrange in an existing schedule allows for addition of new tasks which would otherwise fail to be scheduled. The existing task swap procedure employs a variable ordering heuristic for task insertion that is the same as the retraction heuristic, but scored in the reverse. That is, the least constrained tasks are retracted, and of these the most constrained are committed first. Value selection for commitment is defaulted to a task's earliest feasible start time. We have found that by applying a value selection heuristic, max-availability, to the choice of where to assign the retracted tasks, both solution quality and runtime performance of task swap can be improved greatly. Max-availability considers resource contention for an unassigned task and places it where availability is predicted to be maximal over the range of that task. This heuristic is applicable not only in a repair context, but can also promote resource levelling in the context of constructive task allocation. Finally, we show that use of max-availability in task swapping promotes schedule stability when compared to the prior greedy task insertion policy.

Keywords
scheduling, heuristic 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: 9

Text Reference
Laurence Kramer and Stephen Smith, "Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems," Proceedings 15th International Conference on Automated Planning and Scheduling, July, 2005.

BibTeX Reference
@inproceedings{Kramer_2005_5059,
   author = "Laurence Kramer and Stephen Smith",
   title = "Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems",
   booktitle = "Proceedings 15th International Conference on Automated Planning and Scheduling",
   month = "July",
   year = "2005",
}