An effective new island model genetic algorithm for job shop scheduling problem. (March 2016)

• Record Type: Journal Article
• Authors: Kurdi, Mohamed
• Is Part Of: Computers & operations research. Volume 67(2016)
• Page Start: 132
• Page End: 142
• Publication Date: 2016-03
• Subjects: Job shop scheduling -- Island model -- Parallel genetic algorithm -- Evolutionary computation; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2015.10.005
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: A new island model genetic algorithm which is a more realistic model of the nature. A new naturally inspired evolution model and migration selection mechanism. Islands employ different evolution methods during their self-adaptation phases. Individuals who are least adapted to their environments migrate first. Computational results validate the effectiveness of the proposed algorithm.