Scheduling maintenance services to three machines

We study a discrete problem of scheduling activities of three types under t he constraint that at most a single activity can be scheduled to any one pe riod. Applications of such a model are the scheduling of maintenance servic e to machines and multi-item replenishment of stock. We assume that the cos t associated with any given type of activity increases linearly with the nu mber of periods since the last execution of this type. The problem is to sp ecify at which periods to execute each of the activity types in order to mi nimize the long-run average cost per period. We analyze various forms of op timal solution which may occur, relating them to the combination of the thr ee machine cost constants. Some cases remain unsolved by this method and fo r these we develop a heuristic whose worst case performance is no more than 3.33% from the optimal.