Analyzing the Solvability of the Capacitated Planned Maintenance Problem

This chapter analyzes the solvability of the strongly $$\mathcal{N}\mathcal{P}$$ -hard Capacitated Planned Maintenance Problem (CPMP). The computational complexity of several problem variants is resolved. Finding a feasible solution is already strongly $$\mathcal{N}\mathcal{P}\,$$ complete and the CPMP is binary $$\mathcal{N}\mathcal{P}$$ -hard for two periods. The CPMP is solvable in time $$O(\min \{n \cdot \frac{\log T} {\sqrt{T}} \cdot \bar{ r}^{max\;T} \cdot 4^{T},n \cdot T^{n+1} \cdot 2^{n}\})$$ . Therefore, the CPMP is pseudo-polynomially solvable if the number of periods is a constant and strongly polynomially solvable if either the number of maintenance activities is a constant or if the number of periods and the maximal capacity over all periods are constants. Other optimal, strongly polynomial and pseudo-polynomial algorithms to different problem variants are provided. Valid inequalities and polyhedral properties are presented. The relative strength and the computational complexity of 99 lower bounds is evaluated. The lower bounds are derived from Lagrangean relaxation, decomposition and by neglecting constraints completely.