Time-Critical Scheduling in Stochastic Domains

Abstract

In this work we look at extending the work of (Dean et al. 1993) to handle more complicated schedul-ing problems in which the sources of complexity stem not only from large state spaces but from large ac-tion spaces as well. In these problems it is no longer tractable to compute optimal policies for re-stricted state spaces via policy iteration. We, in-stead, borrow from operations research in applying bottleneck-centered scheduling heuristics (Adams et al. 1988). Additionally, our techniques draw from the work of (Drummond and Bresina 1990). Consider the problem of scheduling planes and gates at a busy airport. A stochastic process describes the arrival of planes at-the airport and is affected by uncon-trollable events such as weather. Stochastic processes