Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms

摘要

In this paper, three hybrid harmony search (HS) algorithms, namely, hybrid harmony search (hHS) algorithm, hybrid globalbest harmony search (hgHS) algorithm and hybrid modified globalbest harmony search (hmgHS) algorithm, are developed for solving the flow shop scheduling with blocking to minimize the total flow time. Firstly, a largest position value (LPV) rule is proposed to convert continuous harmony vectors into job permutations. Secondly, an initialization scheme based on a variant of the NEH heuristic is presented to construct the initial harmony memory with certain quality and diversity. Thirdly, HS 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. In addition, some new pitch adjustment rules are developed to well inherit good structures from the globalbest harmony vector. Based on a set of well-known benchmark instances, extensive computational experiments are carried out. Computational results show the effectiveness of the hybrid harmony search algorithms, especially the (hmgHS) algorithm, in solving the blocking flow shop scheduling with total flow time criterion.