Othar Hansson
Bayesian Problem-Solving Applied to Scheduling
Phd Dissertation, University of California, Berkeley, 1998

Abstract


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 construction 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 performance. 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 incremental 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 with these techniques in DTS shows significant speedups and other advantages over manually-coded software.

Finally, to reduce the number of states examined during search, I have applied the Bayesian Problem-Solving (BPS) approach to the problem of search ordering in backtracking algorithms. The approach estimates, for each subtree, the search cost and probability that a solution exists. These estimates are conditioned on raw heuristic features used by other ordering techniques from the literature. Experiments with the BPS ordering heuristic on a state-of-the-art propositional satisfiability solver show that it overcomes a performance anomaly of an existing strong heuristic on two sets of benchmark problems.