To Appear: Proceedings 14th International Conference on Automated Planning and Scheduling (ICAPS 04), Whistler CA, June 2004
Task Swapping for Schedule Improvement: A Broader Analysis
Laurence A. Kramer and Stephen F. Smith
The Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213, USA
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.
Copyright 2004, Kramer and Smith.
All rights reserved.
Full paper in .pdf format