A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity

Abstract

The scheduling of maintenance activities has been extensively studied, with most studies focusing on single-machine problems. In real-world applications, however, multiple machines or assembly lines process numerous jobs simultaneously. In this paper, we study a parallel-machine scheduling problem in which the objective is to minimize the total tardiness given that there is a maintenance activity on each machine. We develop a branch-and-bound algorithm to solve the problem with a small problem size. In addition, we propose a hybrid genetic algorithm to obtain the approximate solutions when the number of jobs is large. The performance of the proposed algorithms is evaluated based mainly on computational results.

Keywords:

• scheduling
• total tardiness
• parallel machine
• makespan
• maintenance activity

Acknowledgements

The authors are grateful to the editor and the referees, whose constructive comments have led to a substantial improvement in the presentation of the paper. We would also thank T.B. Huang for giving us the real-world application. The first author was supported under NSC 100-2221-E-035-029-MY3 and the second author was supported under NSC 102-2221-E-241 -018.