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

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

0.00 Avg rating0 Votes
Article ID: iaor201527528
Volume: 88
Issue: 4
Start Page Number: 273
End Page Number: 283
Publication Date: Oct 2015
Journal: Computers & Industrial Engineering
Authors:
Keywords: scheduling, heuristics: genetic algorithms, heuristics, search, heuristics: tabu search
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.