A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem

Abstract

In this paper a local-best harmony search (HS) algorithm with dynamic sub-harmony memories (HM) namely DLHS algorithm is proposed to minimize the total weighted earliness and tardiness penalties for a lot-streaming flow shop scheduling problem with equal-size sub-lots. First of all to make the HS algorithm suitable for solving the problem considered a rank-of-value (ROV) rule is applied to convert the continuous harmony vectors to discrete job sequences and a net benefit of movement (NBM) heuristic is utilized to yield the optimal sub-lot allocations for the obtained job sequences. Secondly an efficient initialization scheme based on the NEH variants is presented to construct an initial HM with certain quality and diversity. Thirdly during the evolution process the HM is dynamically divided into many small-sized sub-HMs which evolve independently so as to balance the fast convergence and large diversity. Fourthly a new improvisation scheme is developed to well inherit good structures from the local-best harmony vector in the sub-HM. Meanwhile a chaotic sequence to produce decision variables for harmony vectors and a mutation scheme are utilized to enhance the diversity of the HM. In addition a simple but effective local search approach is presented and embedded in the DLHS algorithm to enhance the local searching ability. Computational experiments and comparisons show that the proposed DLHS algorithm generates better or competitive results than the existing hybrid genetic algorithm (HGA) and hybrid discrete particle swarm optimization (HDPSO) for the lot-streaming flow shop scheduling problem with total weighted earliness and tardiness criterion. (C) 2010 Elsevier Ltd. All rights reserved.