Algorithms for the Capacitated Planned Maintenance Problem

Torben Kuschel
Additional contact information
Torben Kuschel: University of Wuppertal

Chapter Chapter 6 in Capacitated Planned Maintenance, 2017, pp 165-222 from Springer

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

Keywords: Feasible Solution; Mean Absolute Percentage Error; Open Period; Maintenance Activity; Lagrangean Relaxation (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_6

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

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

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 ().