An effective new island model genetic algorithm for job shop scheduling problem

This paper presents an effective new island model genetic algorithm to solve the well-known job shop scheduling problem with the objective of minimizing the makespan. To improve the effectiveness of the classical island model genetic algorithm, we have proposed a new naturally inspired evolution model and a new naturally inspired migration selection mechanism that are capable of improving the search diversification and delaying the premature convergence. In the proposed evolution model, islands employ different evolution methods during their self-adaptation phases, rather than employing the same methods. In the proposed migration selection mechanism, worst individuals who are least adapted to their environments migrate first, hoping in finding a better chance to live in a more suitable environment that imposes a more suitable self-adaptation method on them. The proposed algorithm is tested on 52 benchmark instances, with the proposed evolution model and migration selection mechanism, and without them using the classical alternatives, and also compared with other algorithms recently reported in the literature. Computational results verify the improvements achieved by the proposed evolution model and migration selection mechanism, and show the superiority of the proposed algorithm over the others in terms of effectiveness. (C) 2015 Elsevier Ltd. All rights reserved.