Scheduling maintenance services to three machines

We study a discrete problem of scheduling activities of three types under the constraint that at most a single activity can be scheduled to any one period. Applications of such a model are the scheduling of maintenance service to machines and multi-item replenishment of stock. We assume that the cost associated with any given type of activity increases linearly with the number of periods since the last execution of this type. The problem is to specify at which periods to execute each of the activity types in order to minimize the long-run average cost per period. We analyze various forms of optimal solution which may occur, relating them to the combination of the three machine cost constants. Some cases remain unsolved by this method and for these we develop a heuristic whose worst case performance is no more than 3.33% from the optimal.