A chaotic harmony search algorithm for the flow shop scheduling problem with limited buffers

In this paper, a chaotic harmony search (CHS) algorithm is proposed to minimize makespan for the permutation flow shop scheduling problem with limited buffers. First of all, to make the harmony search algorithm suitable for solving the problem under consideration, a rank-of-value rule is applied to convert continuous harmony vectors to discrete job permutations. Secondly, an efficient initialization scheme based on the Nawaz-Enscore-Ham heuristic [M. Nawaz, E.E.J. Enscore, I. Ham, A heuristic algorithm for the m-machine, n-job flow shop sequencing problem, OMEGA-International Journal of Management Science 11 (1983) 91-95] and its variants is presented to construct an initial harmony memory with a certain level of quality and diversity. Thirdly, a new improvisation scheme is developed to well inherit good structures from the best harmony vector in the last generation. In addition, a chaotic local search algorithm with probabilistic jumping scheme is presented and embedded in the proposed CHS algorithm to enhance the local searching ability. Computational simulations and comparisons based on the well-known benchmark instances are provided. It is shown that the proposed CHS algorithm generates better results not only than the two recently developed harmony search algorithms but also than the existing hybrid genetic algorithm and hybrid particle swarm optimization in terms of solution quality and robustness.