Single-machine scheduling with periodic maintenance and nonresumable jobs

We study a single-machine scheduling problem where periodic maintenance is required in a complete schedule. Although the scheduling problem with maintenance has attracted some researchers’ attention, most of them consider only one maintenance period. In this paper, several maintenance periods are under consideration where each maintenance is required after a periodic time interval. Specifically, the problem is to minimize the maximum tardiness with periodic maintenance and nonresumable jobs. A branch-and-bound algorithm that utilizes several inherent theorems is developed to derive the optimal schedule for the problem. To solve large-sized problems, a heuristic is also developed. Computational results are provided to demonstrate the effectiveness of the heuristic.