# Bayesian Problem-Solving Applied to Scheduling

### Othar Hansson

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-98-1028

1998

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1998/CSD-98-1028.pdf

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.

**Advisor:** Stuart J. Russell

BibTeX citation:

@phdthesis{Hansson:CSD-98-1028, Author = {Hansson, Othar}, Title = {Bayesian Problem-Solving Applied to Scheduling}, School = {EECS Department, University of California, Berkeley}, Year = {1998}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1998/6416.html}, Number = {UCB/CSD-98-1028}, 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. <p>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. <p>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. <p>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. <p>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.} }

EndNote citation:

%0 Thesis %A Hansson, Othar %T Bayesian Problem-Solving Applied to Scheduling %I EECS Department, University of California, Berkeley %D 1998 %@ UCB/CSD-98-1028 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1998/6416.html %F Hansson:CSD-98-1028