R70b  
Maintenance Scheduling Problems As Benchmarks
For Constraint Algorithms
Daniel Frost(frost@ics.uci.edu) &
Rina Dechter (dechter@ics.uci.edu)

Abstract The paper focuses on evaluating constraint satisfaction search algorithms on application based random problem instances. The application we use is a wellstudied problem in the electric power industry: optimally scheduling preventive maintenance of power generating units within a power plant. We show how these scheduling problems can be cast as constraint satisfaction problems and used to define the structure of randomly generated nonbinary CSPs. The random problem instances are then used to evaluate several previously studied algorithms. The paper also demonstrates how constraint satisfaction can be used for optimization tasks. To find an optimal maintenance schedule, a series of CSPs are solved with successively tighter costbound constraints. We introduce and experiment with an "iterative learning" algorithm which records additional constraints uncovered during search. The constraints recorded during the solution of one instance with a certain costbound are used again on subsequent instances with tighter costbounds. Our results show that on a class of randomly generated maintenance scheduling problems, iterative learning reduces the time required to find a good schedule. [ps] [pdf] 