Incremental scheduling to maximize quality in a dynamic environment

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 max-imize 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, poten-tially 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 en-vironment differentiates this problem focus from that of pre-vious research. We develop and evaluate methods for incre-mentally maintaining schedules that maximize the quality (or utility) of executed activities. We contrast the performance of our incremental techniques to that of comparable sched-ule (re)generation techniques with respect to quality, stability and cost considerations. The results clearly favor incremen-tal scheduling in this context, and suggest opportunities for broader schedule improvement search