Article ID: | iaor20103995 |
Volume: | 47 |
Issue: | 7 |
Start Page Number: | 1753 |
End Page Number: | 1771 |
Publication Date: | Apr 2009 |
Journal: | International Journal of Production Research |
Authors: | Azizolu M, Batun S |
Keywords: | programming: branch and bound, maintenance, repair & replacement |
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.