A novel discrete water wave optimization algorithm for blocking flow-shop scheduling problem with sequence-dependent setup times

作者：Shao, Zhongshi; Pi, Dechang^*; Shao, Weishi

来源：Swarm and Evolutionary Computation, 2018, 40: 53-75.

DOI：10.1016/j.swevo.2017.12.005

• Flow shop with blocking
• Setup times
• Scheduling
• Heuristic
• Metaheuristic

This paper considers n-job m-machines blocking flow-shop scheduling problem (BFSP) with sequence-dependent setup times (SDST), which has important ramifications in the modern industry. To solve this problem, two efficient heuristics are firstly presented according to the property of the problem. Then, a novel discrete water wave optimization (DWWO) algorithm is proposed. In the proposed DWWO, an initial population with high quality and diversity is constructed based on the presented heuristic and a perturbation procedure. A two-stage propagation is designed to direct the algorithm towards the good solutions. The path relinking technique is employed in refraction phase to help individuals escape from local optima. A variable neighborhood search is developed and embedded in breaking phase to enhance local exploitation capability. A new population updating scheme is applied to accelerate the convergence speed. Moreover, a speedup method is presented to reduce the computational efforts needed for evaluating insertion neighborhood. Finally, extensive numerical tests are carried out, and the results compared to some state-of-the-art metaheuristics demonstrate the effectiveness of the proposed DWWO in solving BFSP with SDST.

• 出版日期2018-6
• 单位南京航空航天大学