Single machine scheduling with preventive maintenances

We consider the single machine total flow time problem in which the jobs are non-resumable and the machine is subject to preventive maintenance activities of known starting times and durations. We propose a branch-and-bound algorithm that employs powerful optimality properties and bounding procedures. Our extensive computational studies show that our algorithm can solve large-sized problem instances with up to 80 jobs in reasonable times. We also study a two-alternative maintenance planning problem with minor and major maintenances. We give a polynomial-time algorithm to find the optimal maintenance times when the job sequence is fixed.

Citation Formats
S. Batun and M. Azizoğlu, “Single machine scheduling with preventive maintenances,” INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, vol. 47, no. 7, pp. 1753–1771, 2009, Accessed: 00, 2020. [Online]. Available: