Affiliation of Author(s):计算机科学与技术学院/人工智能学院/软件学院

Journal:SWARM AND EVOLUTIONARY COMPUTATION

Key Words:Flow shop with blocking Setup times Scheduling Heuristic Metaheuristic

Abstract: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.

ISSN No.:2210-6502

Translation or Not:no

Date of Publication:2018-06-01

Co-author:邵仲世,邵炜世

Correspondence Author:Pi Dechang