Bayesian Problem-Solving Applied to Scheduling

Othar Hansson

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-98-1028
1998

http://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/6416.html
%F Hansson:CSD-98-1028