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

• A new algorithm combining island model genetic algorithm (IMGA) and tabu search (TS) is proposed.
• It utilizes a new self-adaptation phase strategy: best individuals do a local search, and worst ones do a global search.
• It was tested on 76 benchmark instances, and compared with other 15 similar works.
• Computational results show its superiority over 13 of the compared works, and validate its effectiveness.

This paper presents a new hybrid island model genetic algorithm (HIMGA) to solve the well-known job shop scheduling problem (JSSP) 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.