Article ID: | iaor201526801 |
Volume: | 66 |
Issue: | 9 |
Start Page Number: | 1542 |
End Page Number: | 1554 |
Publication Date: | Sep 2015 |
Journal: | Journal of the Operational Research Society |
Authors: | Kim Yeong-Dae, Lee Ju-Yong |
Keywords: | manufacturing industries, combinatorial optimization, maintenance, repair & replacement, programming: branch and bound, heuristics |
This research focuses on the problem of scheduling jobs on two identical parallel machines that are not continuously available with the objective of minimizing total tardiness. After processing a given number of jobs, each machine requires a preventive maintenance task, during which the machine cannot process jobs. We present dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as an upper bound obtained from a heuristic algorithm. Performance of the algorithm is evaluated through a series of computational experiments on randomly generated instances and results are reported.