Single machine scheduling with preventive maintenances
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, vol.47, no.7, pp.1753-1771, 2009 (SCI-Expanded, Scopus)
- Publication Type: Article / Article
- Volume: 47 Issue: 7
- Publication Date: 2009
- Doi Number: 10.1080/00207540701636348
- Journal Name: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
- 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
Abstract
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.