Heuristic algorithm for the single-machine scheduling with periodic maintenance

This paper considers a single-machine scheduling problem with availability constraints. In many realistic situations, machines may not be always available due to various reasons such as maintenance, breakdown and repair. However, most literature on scheduling assumes that the machines are available at all times. This paper deals with a single-machine scheduling problem with periodic maintenance. If the maintenance decision is made jointly with the job scheduling, the system will be more effective. The objective is to minimize the total completion time of jobs. This problem is proved to be NP-hard in the strong sense. The proposed breaking heuristic (BH) algorithm rule is established by some theorems and conditions. Our computational results show that the BH algorithm is much more efficient than existing heuristic.