Experiments With a Decision- Theoretic Scheduler

Practical Approaches to Scheduling and Planning

Volume

Practical Approaches to Scheduling and Planning

Contents

This paper describes DTS, a decisiontheoretic scheduler designed to employ stateof- the-art probabilistic inference technology to speed the search for efficient solutions to constraint-satisfaction problems. Our approach involves assessing the performance of heuristic control strategies that are normally hard-coded into scheduling systems, and using probabilistic inference to aggregate this information in light of features of a given problem. BPS, the Bayesian Problem-Solver [2], introduced a similar approach to solving singleagent and adversarial graph search problems, yielding orders-of-magnitude improvement over traditional techniques. Initial efforts suggest that similar improvements will be realizable when applied to typical constraint-satisfaction scheduling problems.