Modeling and solving the periodic maintenance problem

A. Grigoriev, J. van de Klundert, F.C.R. Spieksma

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

71 Citaten (Scopus)


We study the problem of scheduling maintenance services. Given is a set of m machines and integral cost-coefficients ai and bi for each machine i (1 ⩽ i ⩽ m). Time is discretized into unit-length periods; in each period at most one machine can be serviced at a given service cost bi. The operating cost of machine i in a period equals ai times the number of periods since the last servicing of that machine i. The problem is to find a cyclic maintenance schedule of a given length T that minimizes total service and operating costs. We call this problem the periodic maintenance problem or PMP.

In this work we are interested in computing optimal solutions to instances of PMP. We investigate several formulations for PMP. Two formulations, referred to as a flow formulation and a set-partitioning formulation, appear to have good linear programming relaxations. We exploit the problem structure by showing how the column generation subproblem can be solved in polynomial time. Our work leads to the first exact solutions for larger sized problem instances, and we present extensive computational results.

Originele taal-2Engels
Pagina's (van-tot)783-797
TijdschriftEuropean Journal of Operational Research
Nummer van het tijdschrift3
StatusGepubliceerd - 1 aug 2006
Extern gepubliceerdJa


Duik in de onderzoeksthema's van 'Modeling and solving the periodic maintenance problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit