Minimizing total flow time in the single-machine scheduling problem with periodic maintenance

This paper deals with a single-machine scheduling problem with limited machine availability. The limited availability of machine results from periodic maintenance activities. In our research, a periodic maintenance schedule consists of several maintenance periods. Each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the total flow time subject to periodic maintenance and nonresumable jobs. Some important theorems are proved for the problem. A branch-and-bound algorithm that utilizes several theorems is proposed to find the optimal schedule. We also develop a heuristic to solve large sized problems. In this paper, computational results show that the proposed heuristic is highly accurate and efficient.