Algorithms for the Capacitated Planned Maintenance Problem

The Capacitated Planned Maintenance Problem (CPMP) schedules maintenance activities that cover a set of periods before they must be executed again and require a maintenance time. This chapter presents specific heuristics because finding a feasible solution is already strongly $$\mathcal{N}\mathcal{P}$$ -complete. Three construction heuristics are presented and the obtained initial feasible solution is potentially improved by metaheuristics. Two Lagrangean heuristics are provided that use the Lagrangean relaxations of the period covering constraint and of the capacity constraint. The fundamental difference in the so called pseudo-subgradient optimization is that the Lagrangean relaxation is solved heuristically, whereas many approaches in literature prefer an optimal solution to derive subgradients from. For this purpose new lower and upper bounds to a Lagrangean relaxation are presented. A general, problem independent approach links two Lagrangean relaxations and uses the relations between Benders’ and Lagrangean decomposition. This yields a novel Lagrangean hybrid heuristic. A tabu search heuristic is proposed, which features a multi-state search and an extended objective function.