Scheduling two machines that require multiple types of maintenance, for a single operation

The problem explored was of using two machines, one at a time, to perform a continuous operation, where each machine is subject to different types and lengths of maintenance. The operation periods between maintenance periods can also vary in length. All the periods are deterministic in length. When the last period ends, the first period starts again. The objective is to maximize the portion of time with an operating machine. We conjecture this is an NP problem. This problem extends the study by J. Kreimer and A. Mehrez on an n-machine single type of maintenance scheduling problem. The no-interrupt policy, that was optimal for their problem is not optimal for ours. Properties of the optimal solution and identification of the state transition mechanism lead to a finite, but exponentially bounded, algorithm that constructs cyclic solutions. Heuristic methods are recommended and tested for small-sized problems. They achieve, on an average, more than 99% of the highest objective function value found by the algorithm, and equal that value in 55–80% of the random problems. The most efficient heuristic method consists of the shortest processing time scheduling rule.