Analyzing the Solvability of the Capacitated Planned Maintenance Problem

Torben Kuschel
Additional contact information
Torben Kuschel: University of Wuppertal

Chapter Chapter 5 in Capacitated Planned Maintenance, 2017, pp 103-164 from Springer

Abstract: Abstract 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.

Keywords: Extreme Point; Maintenance Activity; Vertex Cover; Lagrangean Relaxation; Valid Inequality (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnechp:978-3-319-40289-5_5

Ordering information: This item can be ordered from
http://www.springer.com/9783319402895

DOI: 10.1007/978-3-319-40289-5_5

Access Statistics for this chapter

More chapters in Lecture Notes in Economics and Mathematical Systems from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().