Single machine scheduling with preventive maintenances

Batun S., Azizoğlu M.

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, vol.47, no.7, pp.1753-1771, 2009 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 47 Issue: 7
  • Publication Date: 2009
  • Doi Number: 10.1080/00207540701636348
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.1753-1771
  • Keywords: scheduling, preventive maintenance, branch-and-bound algorithm, FLOW-TIME, AVAILABILITY
  • Middle East Technical University Affiliated: Yes


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.