The replacement problem: A polyhedral and complexity analysis. The complete version

• We consider an optimization model for determining optimal opportunistic maintenance (that is, component replacement) schedules when data is deterministic. This problem, which generalizes that of Dickman et al., is a natural starting point for the modelling of replacement schedules when component lives are non-deterministic, whence a mathematical study of the model is of large interest. We show that the convex hull of the set of feasible replacement schedules is full-dimensional, and that all the necessary inequalities are facet-inducing. Additional facets are then provided through Chvatal-Gomory rounding. We show that when maintenance occasions are fixed, the remaining problem reduces to a linear program; in some cases the latter is solvable through a greedy procedure. We further show that this basic replacement problem is NP-hard.

Subject headings

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

Keyword

mixed binary linear programming

polyhedral analysis

complexity analysis

opportunistic maintenance

replacement problem

opportunistic maintenance

Publication and Content Type

vet (subject category)

ovr (subject category)