A new hybrid island model genetic algorithm for job shop scheduling problem

This paper presents a new hybrid island model genetic algorithm (HIMGA) to solve the well-known job shop scheduling problem (ISSP) with the objective of makespan minimization. To improve the effectiveness of the island model genetic algorithm (IMGA), we have proposed a new naturally inspired self-adaptation phase strategy that is capable of striking a better balance between diversification and intensification of the search process. In the proposed self-adaptation phase strategy, the best individuals are recruited to perform a local search using tabu search (TS), and the worst ones are recruited to perform a global search using a combination of 3 classical random mutation operators. The proposed algorithm is tested on 76 benchmark instances, with the proposed self-adaptation strategy, and without it using the classical alternatives, and also compared with other 15 algorithms recently reported in the literature. Computational results verify the improvements achieved by the proposed self-adaptation strategy, and show the superiority of the proposed algorithm over 13 of the compared works in terms of solution quality, and validate its effectiveness. (C) 2015 Elsevier Ltd. All rights reserved.