Modeling and Solving the Periodic Maintenance Problem

We study the problem of scheduling maintenance services. Given is a set of mmachines and integral cost-coefficients ai and bi for each machine i (1 < i < m). Timeis discretized into unit-length periods; in each period at most one machine can beserviced at a given service cost bi. The operating cost of machine i in a period equalsai times the number of periods since the last servicing of that machine i. The problemis to find a cyclic maintenance schedule of a given length T that minimizes total serviceand 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 flowformulation and a set-partitioning formulation, appear to have good linear programmingrelaxations. We exploit the problem structure by showing how the column generationsubproblem can be solved in polynomial time. Our work leads to the first exactsolutions for larger sized problem instances, and we present extensive computationalresults.