Article ID: | iaor20121284 |
Volume: | 39 |
Issue: | 9 |
Start Page Number: | 2196 |
End Page Number: | 2205 |
Publication Date: | Sep 2012 |
Journal: | Computers and Operations Research |
Authors: | Kim Yeong-Dae, Lee Ju-Yong |
Keywords: | scheduling, heuristics, combinatorial optimization, maintenance, repair & replacement |
This research focuses on the problem of scheduling jobs on a single machine that requires periodic maintenance with the objective of minimizing the number of tardy jobs. We present a two‐phase heuristic algorithm in which an initial solution is obtained first with a method modified from Moore's algorithm for the problem without maintenance and then the solution is improved in the second phase. Performance of the proposed heuristic algorithm is evaluated through computational experiments on randomly generated problem instances and results show that the heuristic gives solutions close to those obtained from a commercial integer programming solver in much shorter time and works better than an existing heuristic algorithm in terms of the solution quality.