RI | Publications | Task Swapping for Schedule Improvement: A Broader Analysis

Text only version of this site

Task Swapping for Schedule Improvement: A Broader Analysis
L. Kramer and S. Smith
Proceedings 14th International Conference on Automated Planning and Scheduling, June, 2004.

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

Download [Help]

Adobe portable document format (pdf) [146 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 analyze and extend a recently developed ``task-swapping procedure'' for improving schedules in oversubscribed situations. In such situations, there are tasks which cannot be directly added to the current schedule without introducing capacity conflicts. A schedule is improved if one or more of these tasks can be feasibly included, and the goal of task swapping is to rearrange some portion of the current schedule to make this possible. Key to effective task swapping is an ability to exploit the scheduling flexibility inherent in the constraints associated with various scheduled tasks, and previous work has shown that the use of retraction heuristics that favor tasks with greater rescheduling flexibility can give rise to strong schedule improvement capabilities. We extend this work by developing and evaluating several improvements to the core task swapping procedure. We introduce three pruning techniques and show that each significantly improves computational efficiency while maintaining solution quality. We then investigate the possibility of improving the ``end'' solutions by stochastically exploring the ``neighborhood'' around them, and demonstrate that improved solutions are possible given the ability to spend additional time.

Notes

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

Number of pages: 8

Text Reference

L. Kramer and S. Smith, "Task Swapping for Schedule Improvement: A Broader Analysis," Proceedings 14th International Conference on Automated Planning and Scheduling, June, 2004.

BibTeX Reference

@inproceedings{Kramer_2004_4613,
   author = "Laurence Kramer and Stephen Smith",
   title = "Task Swapping for Schedule Improvement: A Broader Analysis",
   booktitle = "Proceedings 14th International Conference on Automated Planning and Scheduling",
   month = "June",
   year = "2004"
}