A factorial based particle swarm optimization with a population adaptation mechanism for the no-wait flow shop scheduling problem with the makespan objective

• Published in: Expert systems with applications 2019-07, Vol.126, p.41-53
• Main Authors: Zhao, Fuqing, Qin, Shuo, Yang, Guoqiang, Ma, Weimin, Zhang, Chuck, Song, Houbin
• Format: Article
• Language: English
• Subjects: Adaptation; Algorithms; Digits; Factorial representation; Job shop scheduling; Makespan; No-wait flow shop scheduling problem; Particle swarm optimization; Permutations; Population; Production scheduling; Runtime analysis; Variable neighborhood search
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2019.01.084

•An FPAPSO algorithm is proposed for solving NWFSP.•The factorial representation is employed to map the search space to integer domain.•A VNS is introduced to search around the promising area in each generation.•The PA mechanism is designed to control the diversity of population.•The runtime analysis of FPAPSO is performed with the level-based theorem. The no-wait flow shop scheduling problem (NWFSP) performs an essential role in the manufacturing industry. In this paper, a factorial based particle swarm optimization with a population adaptation mechanism (FPAPSO) is implemented for solving the NWFSP with the makespan criterion. The nearest neighbor mechanism and NEH method are employed to generate a potential initial population. The factorial representation, which uniquely represents each number as a string of factorial digits, is designed to transfer the permutation domain to the integer domain. A variable neighbor search strategy based on the insert and swap neighborhood structure is introduced to perform a local search around the current best solution. A population adaptation (PA) mechanism is designed to control the diversity of the population and to avoid the particles being trapped into local optima. Furthermore, a runtime analysis of FPAPSO is performed with the level-based theorem. The computational results and comparisons with other state-of-the-art algorithms based on the Reeve's and Taillard's instances demonstrate the efficiency and performance of FPAPSO for solving the NWFSP.