CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

The replacement problem: A polyhedral and complexity analysis

Torgny Almgren ; Niclas Andréasson ; Michael Patriksson (Institutionen för matematiska vetenskaper, matematik) ; Ann-Brith Strömberg (Institutionen för matematiska vetenskaper, matematik) ; Adam Wojciechowski (Institutionen för matematiska vetenskaper, matematik)

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.

Nyckelord: mixed binary linear programming, polyhedral analysis, complexity analysis, opportunistic maintenance, replacement problem

Denna post skapades 2009-01-26. Senast ändrad 2014-10-27.
CPL Pubid: 89043


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)


Optimeringslära, systemteori

Chalmers infrastruktur

Ingår i serie

Preprint - Department of Mathematical Sciences, Chalmers University of Technology and Göteborg University