The Robotics Institute

Carnegie Mellon Robotics Institute

Menu

• About RI
• People
• Research
• Education
• Careers
• News & Media
• Events

• RI History

• Contact Us

• Maps & Directions

• About this Site

• Faculty

• Adjunct Faculty

• Students

• Postdoctoral Fellows

• Project Staff

• Institute Staff

• Visitors

• Alumni

• All RI Members

• Faculty Research Interests

• Research Centers

• Consortia

• Labs & Groups

• Projects

• Publications

• Academic Programs

• Admissions

• Policies and Forms

• Courses

• Student Services

• Student Life

• Faculty Positions

• Staff Positions

• Postdoctoral Positions

• Internships

• Employers Seeking Graduating Students

• Graduate Students Seeking Employment

• Official Press Releases

• Recent News

• Videos

• Events and Activities

• Talks and Seminars

Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems

Laurence Kramer and Stephen Smith
Proceedings 15th International Conference on Automated Planning and Scheduling, June, 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.

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, 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", }