RI | Publications | Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems

Text only version of this site

Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems
L. Kramer and S. Smith
Proceedings 15th International Conference on Automated Planning and Scheduling, June, 2005.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Download [Help]

Adobe portable document format (pdf) [188 KB]

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.

Notes

Associated center: CIMDS
Associated lab/group: Intelligent Coordination and Logistics Laboratory
Associated project: AMC Barrelmaster Scheduling

Number of pages: 9

Text Reference

L. Kramer and S. Smith, "Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems," Proceedings 15th International Conference on Automated Planning and Scheduling, June, 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 = "June",
   year = "2005"
}