Island-based Modified Harmony Search Algorithm with Neighboring Heuristics Methods for Flow Shop Scheduling with Blocking

摘要

The flow shop scheduling with blocking involves assigning several jobs to machines with minimum time complexity. This problem can be considered as a combinatorial optimization problem that does not have an algorithmic solution. Recently, the modified harmony search algorithm with neighboring heuristics methods (MHSNH) is proposed to tackle this problem. In this paper, the flow shop scheduling with blocking problem is tackled using the island harmony search version of MHSNH. Recently, a new version of harmony search algorithm (iHS) is proposed for global optimization problems. In i HS, the population stored in the harmony memory is divided into a set of sub-populations called islands. After a predefined number of iterations, some of the migrant individuals determined by migration rate are exchanged between islands following a migration topology to control the population diversity. In order to evaluate the island modified harmony search algorithm with neighboring heuristics methods (iMHSNH), a de facto standard job scheduling dataset, Taillard’s benchmark, is used. The proposed algorithm is compared to a number of well-established methods in terms of the mean total flow time and the average relative percentage deviation. The proposed method outperforms other comparative algorithms. Finally, the proposed algorithm is compared against MHSNH in terms of locating multiple optimal solutions, which has not been studied before in the literature.