A hybrid evolutionary algorithm for the job shop scheduling problem

Abstract

In this paper, a hybrid metaheuristic method for the job shop scheduling problem is proposed. The optimization criterion is the minimization of makespan and the solution method consists of three components: a Differential Evolution-based algorithm to generate a population of initial solutions, a Variable Neighbourhood Search method and a Genetic Algorithm to improve the population; the latter two are interconnected. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches high quality solutions in short computational times using fixed parameter settings.

Keywords:

• Production scheduling
• job shop
• evolutionary algorithms
• VNS

Acknowledgements

This work was supported by the General Secretariat for Research and Technology under contract GSRT-05-ΠAB-71. Moreover, the authors would like to thank the anonymous Referees for their constructive comments and contribution to the completion of this work.