R70a  
Constraint Processing for Optimal Maintenance Scheduling
Daniel Frost(frost@ics.uci.edu) &
Rina Dechter (dechter@ics.uci.edu)

Abstract A wellstudied problem in the electric power industry is that of optimally scheduling preventative maintenance of power generating units within a power plant. We show how these problems can be cast as constraint satisfaction problems and provide an "iterative learning" algorithm which solves the problem in the following manner. In order to find an optimal schedule, the algorithm solves a series of CSPs with successively tighter costbound constraints. For the solution of each problem in the series we use constraint learning, which involves recording additional constraints that are uncovered during search. However, instead of solving each problem independently, after a problem is solved successfully with a certain costbound, the new constraints recorded by learning are used in subsequent attempts to find a schedule with a lower costbound. We show empirically that on a class of randomly generated maintenance scheduling problems iterative learning reduces the time to find a good schedule. We also provide a comparative study of the most competitive CSP algorithms on the maintenance scheduling benchmark. [ps] [pdf] 