Solving the Weighted Capacitated Planned Maintenance Problem and its variants

This paper introduces, analyzes, and solves the Weighted Capacitated Planned Maintenance Problem (WCPMP) and its practically relevant variants. The problem pursues the finding of a maintenance schedule that incurs minimum total fixed and variable cost. Each executed maintenance activity guarantees the operability of the respective component for an interval of predetermined length. Moreover, a feasible schedule has to obey period-dependent predetermined time limitations for the scheduled maintenance activities. After providing a literature classification of the WCPMP and proving that the unweighted CPMP is strongly NP-hard, the complexity status of further problem variants is established. For instance, a solution procedure is proposed for the WCPMP that guarantees an optimal solution in strongly-polynomial time if the number of maintenance activities is a constant. Moreover, the algorithm becomes pseudo-polynomial if the number of periods is a constant. In order to deal with strongly NP-hard variants, a multi-state Tabu Search approach is proposed. Its efficiency is evaluated in a computational study.