THE SCHEDULING OF MAINTENANCE SERVICE

We study a discrete problem of scheduling activities of several types under the constraint that at most a single activity can be scheduled t o any one period. Applications of such a model are the scheduling of m aintenance service to machines and multi-item replenishment of stock. In this paper we assume that the cost associated with any given type o f activity increases linearly with the number of periods since the las t execution of this type, The problem is to find an optimal schedule s pecifying at which periods to execute each of the activity types in or der to minimize the long-run average cost per period. We investigate p roperties of an optimal solution and show that there is always a cycli c optimal policy. We propose a greedy algorithm and report on computat ional comparison with the optimal. We also provide a heuristic, based on regular cycles for ail but one activity type, with a guaranteed wor se case bound. (C) 1998 Elsevier Science B.V. All rights reserved.