Bayesian Problem-Solving Applied to Scheduling

This dissertation describes several advances to the theory and practice of artificial intelligence scheduling and constraint-satisfaction techniques. I have developed and implemented these techniques during the con-struction of DTS, the Decision-Theoretic Scheduler, and its successor, SchedKit, a toolkit of scheduling algorithms and data structures. The dissertation describes and analyzes the three orthogonal approaches to improving a scheduler’s perfor-mance. These are: (1) reducing the size of the state space to be searched, (2) reducing the per-state cost of state generation and evaluation, and (3) reducing the number of states examined by selective search. To reduce the size of the state space, I have developed several new preprocessing algorithms designed to exploit resource constraints, including resource capacity and resource/task compatibility. Experiments show that it is possible to exploit resource capacity constraints efficiently despite their inherently disjunctive nature. To reduce the cost of state generation, I employ computational geometry data structures that optimize incre-mental heuristic evaluation, constraint-checking and state-variable maintenance. These data structures can be compiled from a formal attribute grammar specification of the heuristics and constraints. Experience wit