Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
11012404 | European Journal of Operational Research | 2019 | 12 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Torben Kuschel, Stefan Bock,