The Robotics Institute

Carnegie Mellon Robotics Institute

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.

Keywords

scheduling, iterated stochastic search, heuristics

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: 8

Text Reference

Laurence Kramer and Stephen 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",
}

The Robotics Institute

Menu