A well-studied problem in the electric power industry is that of optimally scheduling preventative maintenance of power generating
units within a power plant [
1,
3]. The general purpose of determining a maintenance schedule is to determine the duration and sequence of outages of power
generating units over a given time period, while minimizing operating and maintenance costs over the planning period, subject
to various constraints. We show how maintenance scheduling can be cast as a constraint satisfaction problem and used to define
the structure of randomly generated non-binary CSPs. These random problem instances are then used to evaluate several previously
studied backtracking-based algorithms, including backjumping and dynamic variable ordering augmented with constraint learning
and look-ahead value ordering [
2].
We also define and report on a new ⩼erative learning’ algorithm which solves maintenance scheduling problems in the following
manner. In order to find an optimal schedule, the algorithm solves a series of CSPs with successively tighter cost-bound constraints.
For the solution of each problem in the series constraint learning is applied, which involves recording additional constraints
that are uncovered during search. However, instead of solving each problem in the series independently, after a problem is
solved successfully with a certain cost-bound, the new constraints recorded by learning are used in subsequent attempts to
find a schedule with a lower cost-bound. We show empirically that on a class of randomly generated maintenance scheduling
problems iterative learning reduces the time required to find a good schedule.