Using adaptive priority weighting to direct search in probabilistic scheduling

Andrew M. Sutton, Adele E. Howe, L. Darrell Whitley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Many scheduling problems reside in uncertain and dynamic environments - tasks have a nonzero probability of failure and may need to be rescheduled. In these cases, an optimized solution for a short-term time horizon may have a detrimental impact over a broader time scale. We examine a scheduling domain in which time and energy on a phased array radar system is allocated to track objects in orbit around the earth. This domain requires probabilistic modeling to optimize the expected number of successful tasks on a particular day. Failed tasks must be attempted again on subsequent days. Given a set of task requests, we study two long-term objectives: percentage of requests initially successful, and the average time between successful request updates. We investigate adaptive priority weighting strategies that directly influence the short-term objective function and thus indirectly influence the long-term goals. We find that adapting priority weights based on when individual tasks succeed or fail allows a catalog of requests to be filled more quickly. Furthermore, with adaptive priorities, we observe a Pareto-front effect between the two long-term objectives as we modify how priorities are weighted, but an inverse effect of weighting when the priorities are not adapted.

Original languageEnglish (US)
Title of host publicationICAPS 2007, 17th International Conference on Automated Planning and Scheduling
Pages320-327
Number of pages8
StatePublished - Dec 1 2007
EventICAPS 2007, 17th International Conference on Automated Planning and Scheduling - Providence, RI, United States
Duration: Sep 22 2007Sep 26 2007

Other

OtherICAPS 2007, 17th International Conference on Automated Planning and Scheduling
CountryUnited States
CityProvidence, RI
Period9/22/079/26/07

Fingerprint Dive into the research topics of 'Using adaptive priority weighting to direct search in probabilistic scheduling'. Together they form a unique fingerprint.

  • Cite this

    Sutton, A. M., Howe, A. E., & Whitley, L. D. (2007). Using adaptive priority weighting to direct search in probabilistic scheduling. In ICAPS 2007, 17th International Conference on Automated Planning and Scheduling (pp. 320-327)