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)
(2009)
[Preprint]

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)

Ämnesområden

Optimeringslära, systemteori

Chalmers infrastruktur

Ingår i serie

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