DOI:10.19850/j.cnki.2096-4706.2021.24.032

中图分类号：TP301.1                                           文献标识码：A                              文章编号：2096-4706（2021）24-0124-06

Resolving Distributed Assembly Permutation Flow Shop Scheduling Problem Based on Discrete Artificial Bee Colony Algorithm

DUAN Xiushan

(College of Mechanical Engineering, Chongqing University of Technology, Chongqing 400054, China)

Abstract: For the distributed assembly permutation flow shop scheduling problem, a discrete artificial bee colony algorithm is proposed to minimize the makespan. Firstly, an initial solution generation method based on random product order and workpiece order is proposed. Secondly, an population individual neighborhood search strategy based on the critical path is designed, and tournament selection and novel elite retention strategy are employed to accelerate population convergence. Finally, the balance of exploitation and exploration capability is achieved by transforming the population individuals caught in local traps. A large number of computational experiments based on 1710 instances are carried out. The results verify the superiority of the proposed algorithm.

Keywords: flow shop; scheduling; artificial bee colony algorithm; makespan

参考文献：

[1] LEE C Y，CHENG T C E，LIN B M T. Minimizing the Makespan in the 3-Machine Assembly-Type Flowshop Scheduling Problem [J].Management Science，1993，39（5）：616-625.

[2] POTTS C N，SEVAST’JANOV S V，STRUSEVICH V A， et al. The Two-Stage Assembly Scheduling Problem：Complexity and Approximation [J].Operations Research，1995，43（2）：346-355.

[3] CHENG T C E，WANG G. Scheduling the fabrication and assembly of components in a two-machine flowshop [J].IIE Transactions，1999，31（2）：135-143. 2021.12 129 第 24 期

[4] ALI A，HARUN A. The two stage assembly flowshop scheduling problem to minimize total tardiness [J].Journal of Intelligent Manufacturing，2015，26（2）：225-237.

[5] ALI A，AL-ANZI F S. The two-stage assembly scheduling problem to minimize total completion time with setup times [J]. Computers and Operations Research，2009，36（10）：2740-2747.

[6] ZANG Y，ZHOU Z L，LIU J Y. The production scheduling problem in a multi-page invoice printing system [J].Computers and Operations Research，2010，37（10)：1814-1821.

[7] BEHNAMIAN J，GHOMI S M T F. A survey of multi-factory scheduling [J].Journal of Intelligent Manufacturing，2016，27（1）： 231-249.

[8] NADERI B，RUIZ R. The distributed permutation flowshop scheduling problem [J].Computers and Operations Research，2010，37 （4）：754-768.

[9] HATAMIS，Ruiz R，ANDRES-ROMANO C. The Distributed Assembly Permutation Flowshop Scheduling Problem [J]. International Journal of Production Research，2013，51（17）：5292- 5308.

[10] LIN J，ZHANG S. An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flowshop scheduling problem [J].Computers & Industrial Engineering， 2016，97：128-136.

[11] WANG S Y，WANG L. An Estimation of Distribution Algorithm-Based Memetic Algorithm for the Distributed Assembly Permutation Flow-Shop Scheduling Problem [J].IEEE Transactions on Systems, Man, and Cybernetics: Systems，2016，46（1）：139-149.

[12] LIN J，WANG Z J，LI X. A backtracking search hyperheuristic for the distributed assembly flow-shop scheduling problem [J]. Swarm and Evolutionary Computation，2017，36：124-135.

[13] PAN Q K，GAO L，LI X Y，et al. Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem [J].Applied Soft Computing，2019，81： 105492.

[14] FERONE D，HATAMI S，GONZÁLEZ‐NEIRA EM， et al. A biased‐randomized iterated local search for the distributed assembly permutation flow‐shop problem [J]. International Transactions in Operational Research，2020，27（3）：1368-1391.

[15] ZHANG G H，XING K Y，Zhang G Y，et al. Memetic algorithm with meta-Lamarckian learning and simplex search for distributed flexible assembly permutation flowshop scheduling problem [J].IEEE Access，2020，8：96115-96128.

[16] ZHANG Z Q，QIAN B，HU R，et al. A matrix-cubebased estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem [J].Swarm and Evolutionary Computation，2021，60：100785.

[17] HATAMI S，RUIZ R，ANDRES-ROMANO C. Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times [J]. International Journal of Production Economics，2015，169：76-88.

[18] SONG H B，LIN J . A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times [J].Swarm and Evolutionary Computation，2021，60：100807.

[19] GONZALEZ-NEIRA E M，FERONE D，HATAMI S， et al. A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times [J]. Simulation Modelling Practice and Theory，2017，79：23-36.

[20] ZHANG G H，XING K Y，CAO F. Scheduling distributed flowshops with flexible assembly and set-up time to minimize makespan [J].International Journal of Production Research，2018，56（9-10）： 3226-3244.

[21] SANG H Y，PAN Q K，LI J Q，et al. Effective invasive weed optimization algorithms for distributed assembly permutation flowshop problem with total flowtime criterion [J]. Swarm and Evolutionary Computation，2019，44：64-73.

[22] LI D N，Li M，Meng X W，et al. A Hyperheuristic Approach for Intercell Scheduling With Single Processing Machines and Batch Processing Machines [J].IEEE Transactions on Systems, Man, and Cybernetics: Systems，2015，45（2）：315-325.

[23] OZTURK C，GORKEMLI B，KARABOGA D，et al. A comprehensive survey: artificial bee colony (ABC) algorithm and applications [J].Artificial Intelligence Review: An International Science and Engineering Journal，2014，42：21-57.

[24] LIU Z M. A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem [J].Computers & Industrial Engineering，2012，62（4）：917-926.

[25] RUIZ R，MAROTO C，ALCARAZ J. Two new robust genetic algorithms for the flowshop scheduling problem [J].Omega， 2006，34（5）：461-476.

作者简介：段秀山（1995—），男，汉族，重庆彭水人，硕士研究生在读，研究方向：智能制造。