A hybrid biogeography-based optimization with variable neighborhood search mechanism for no-wait flow shop scheduling problem. (15th July 2019)

• Record Type: Journal Article
• Authors: Zhao, Fuqing; Qin, Shuo; Zhang, Yi; Ma, Weimin; Zhang, Chuck; Song, Houbin
• Is Part Of: Expert systems with applications. Volume 126(2019)
• Page Start: 321
• Page End: 339
• Publication Date: 2019-07-15
• Subjects: Biogeography-based optimization -- No-wait flow shop scheduling problem -- Block neighborhood structure -- Markov model -- Path relink technique; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2019.02.023
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A HBV algorithm is proposed for solving NWFSP. The migration operator is redifined by path relink and self-improvement strategy. The IG is embedded into mutation operator to balance the exploration and exploitation. A modified VNS is designed to enhance the exploration ability. The convergence performance of HBV is analyzed with the Markov model. Abstract: The no-wait flow shop scheduling problem (NWFSP) plays an essential role in the manufacturing industry. Inspired by the overall process of biogeography theory, the standard biogeography-based optimization (BBO) was constructed with migration and mutation operators. In this paper, a hybrid biogeography-based optimization with variable neighborhood search (HBV) is implemented for solving the NWFSP with the makespan criterion. The modified NEH and the nearest neighbor mechanism are employed to generate a potential initial population. A hybrid migration operator, which combines the path relink technique and the block-based self-improvement strategy, is designed to accelerate the convergence speed of HBV. The iterated greedy (IG) algorithm is introduced into the mutation operator to obtain a promising solution in exploitation phase. A variable neighbor search strategy, which is based on the block neighborhood structure and the insert neighborhood structure, is designed to perform the local search around the current best solution in each generation. Furthermore, the global convergence performance of the HBV is analyzed with the Markov model. The computational results and comparisons with other state-of-art algorithms based on Taillard and VRF benchmark show that the efficiency and performance of HBV for solving NWFSP.