RI | Publications | Incremental Scheduling to Maximize Quality in a Dynamic Environment

Text only version of this site

Incremental Scheduling to Maximize Quality in a Dynamic Environment
A.T. Gallagher, T.L. Zimmerman, and S. Smith
ICAPS 2006 (International Conference on Automated Planning and Scheduling, AAAI Press, Menlo Park, CA, June, 2006.

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

Download [Help]

Adobe portable document format (pdf) [179 KB]
Compressed postscript (ps.gz) [182 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

We present techniques for incrementally managing schedules in domains where activities accrue quality as a function of the time and resources allocated to them and the goal is to maximize the overall quality of actions executed over time. The scheduling problem of interest is both over-subscribed and dynamic; there is generally more to do than is possible within imposed deadlines, and opportunities to execute new, potentially higher payoff activities continually arrive. Like other dynamic domains, schedule stability and computational cost concerns argue for the use of incremental techniques in this context. The novel emphasis on maintaining schedules that produce ``high value'' results when faced with a changing environment differentiates this problem focus from that of previous research. We develop and evaluate methods for incrementally maintaining schedules that maximize the quality (or utility) of executed activities. We contrast the performance of our incremental techniques to that of comparable schedule (re)generation techniques with respect to quality, stability and cost considerations. The results clearly favor incremental scheduling in this context, and suggest opportunities for broader schedule improvement search.

Notes

Sponsor: National Science Foundation
Grant ID: 9900298

Associated center: CIMDS
Associated lab/group: Intelligent Coordination and Logistics Laboratory

Number of pages: 10

Text Reference

A.T. Gallagher, T.L. Zimmerman, and S. Smith, "Incremental Scheduling to Maximize Quality in a Dynamic Environment," ICAPS 2006 (International Conference on Automated Planning and Scheduling, AAAI Press, Menlo Park, CA, June, 2006.

BibTeX Reference

@inproceedings{Gallagher_2006_5708,
   author = "Anthony T Gallagher and Terry Lyle Zimmerman and Stephen Smith",
   title = "Incremental Scheduling to Maximize Quality in a Dynamic Environment",
   booktitle = "ICAPS 2006 (International Conference on Automated Planning and Scheduling",
   month = "June",
   year = "2006",
   publisher = "AAAI Press",
   address = "Menlo Park, CA"
}