A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem

Abstract

This paper proposes a hybrid modified global-best harmony search (hmgHS) algorithm for solving the blocking permutation flow shop scheduling problem with the makespan criterion. First of all the largest position value (LPV) rule is proposed to convert continuous harmony vectors into job permutations. Second an efficient initialization scheme based on the Nawaz-Enscore-Ham (NEH) heuristic is presented to construct the initial harmony memory with a certain level of quality and diversity. Third harmony search is employed to evolve harmony vectors in the harmony memory to perform exploration whereas a local search algorithm based on the insert neighborhood is embedded to enhance the local exploitation ability. Moreover a new pitch adjustment rule is developed to well inherit good structures from the global-best harmony vector. Computational simulations and comparisons demonstrated the superiority of the proposed hybrid harmony search algorithm in terms of solution quality. (C) 2011 Elsevier Ltd. All rights reserved.