Solving the Weighted Capacitated Planned Maintenance Problem and its variants

Torben Kuschel and Stefan Bock ()

European Journal of Operational Research, 2019, vol. 272, issue 3, 847-858

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

Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718306131
Full text for ScienceDirect subscribers only

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:eee:ejores:v:272:y:2019:i:3:p:847-858

DOI: 10.1016/j.ejor.2018.07.008

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().