Survey on Distributed Assembly Permutation Flowshop Scheduling Problem

doi:10.3778/j.issn.1002-8331.2307-0276

Abstract

Abstract: As the rapid development of modern manufacturing, the past decades have witnessed a trend in which jobs are firstly processed in distributed production factories and then assembled into the final products in an assembly factory after completion. Such manufacturing mode brings many advantages as well as some new challenges on resource scheduling. This paper surveys literature on the distributed assembly permutation flowshop scheduling problem (DAPFSP). Firstly, the background and main issues in DAPFSP are introduced. Then, mathematical models, encoding and decoding schemes, and global and local search algorithms are thoroughly discussed for DAPFSP with the objective of minimizing the maximal completion time. Additionally, recent advances on DAPFSP with various objectives, such as total flow time, DAPFSP with other constraints like no-wait, and DAPFSP by taking issues including setup time into consideration are also surveyed. Finally, several future research directions worthy further investigation are pointed out.

Key words: distributed assembly, permutation flowshop, resource scheduling, search algorithms

摘要： 近几十年来，现代制造业发展迅速，一种趋势是在分布式生产工厂进行工件的加工，待完成后到装配工厂集中装配成最终产品。该模式在带来诸多好处的同时，对资源调度提出了新的挑战。针对分布式装配置换流水车间调度问题（distributed assembly permutation flowshop scheduling problem， DAPFSP），介绍了DAPFSP的背景和存在的主要困难，进而对以最小化最大完工时间为优化目标的DAPFSP，从数学模型、编解码策略、全局和局部搜索算法角度进行探讨，分别综述了以最小化总流程时间等为优化目标，具有零等待等约束，以及考虑准备时间等因素的DAPFSP研究成果。最后，对有待进一步开展的研究工作进行展望。

关键词: 分布式装配, 置换流水车间, 资源调度, 搜索算法

ZHANG Jing, SONG Hongbo, LIN Jian. Survey on Distributed Assembly Permutation Flowshop Scheduling Problem[J]. Computer Engineering and Applications, 2024, 60(6): 1-9.

张静, 宋洪波, 林剑. 分布式装配置换流水车间调度问题研究综述[J]. 计算机工程与应用, 2024, 60(6): 1-9.

References

[1] BEHNAMIAN J, FATEMI GHOMI S M T. A survey of multi-factory scheduling[J]. Journal of Intelligent Manufacturing, 2016, 27: 231-249.
[2] NADERI B, RUIZ R. The distributed permutation flowshop scheduling problem[J]. Computer & Operation Research, 2010, 37: 754-768.
[3] 王凌, 邓瑾, 王圣尧.分布式车间调度优化算法研究综述[J].控制与决策, 2016, 31(1):1-11.
WANG L, DENG J, WANG S Y. Survey on optimization algorithms for distributed shop scheduling[J]. Control and Decision, 2016, 31(1): 1-11.
[4] KOMAKI G, SHEIKH S, MALAKOOTI B. Flow shop scheduling problems with assembly operations: a review and new trends[J]. International Journal of Production Research, 2019, 57(10): 2926-2955.
[5] KOULAMAS C, KYPARISIS G J. The three-stage assembly flowshop scheduling problem[J]. Computer & Operation Research, 2001, 28: 689-704.
[6] HATAMI S, RUIZ R, ANDRéS-ROMANO C. The distributed assembly permutation flowshop scheduling problem[J]. International Journal of Production Research, 2013, 51(17): 5292-5308.
[7] 王凌.车间调度及其遗传算法[M].北京: 清华大学出版社, 2003: 1-2.
WANG L. Shop scheduling with genetic algorithms[M]. Beijing: Tsinghua University & Springer Press, 2003: 1-2.
[8] 王万良, 吴启迪.生产调度智能算法及其应用[M].北京:科学出版社, 2007: 1-3.
WANG W L, WU Q D. Intelligent algorithms and applications for production scheduling[M]. Beijing: Science Press, 2007: 1-3.
[9] JOHNSON S M. Optimal two and three-stage production schedules with set up times included[J]. Naval Research Logistics Quarterly, 1954, 1(1): 61-68.
[10] OSMAN I H, POTTS C N. Simulated annealing for permutation flow-shop scheduling[J]. Omega, 1989, 17(6): 551-557.
[11] HAMZADAYI A, ARVAS M A, ELMIV A. Distributed assembly permutation flow shop problem: single seekers society algorithm[J]. Journal of Manufacturing Systems, 2021, 61: 613-631.
[12] 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.
[13] ZHAO F Q, ZHAO J L, WANG L, et al. An optimal block knowledge driven backtracking search algorithm for distributed assembly no-wait flow shop scheduling problem[J]. Applied Soft Computing, 2021, 112 : 107750.
[14] YANG Y H, LI X. A knowledge-driven constructive heuristic algorithm for the distributed assembly blocking flow shop scheduling problem[J]. Expert Systems with Application, 2022, 202: 117269.
[15] SHAO W S, PI D C, SHAO Z S. Local search methods for a distributed assembly no-idle flow shop scheduling problem[J]. IEEE Systems Journal, 2019, 13(2): 1945-1956.
[16] 张松灿, 普杰信, 司彦娜, 等. 蚁群算法在移动机器人路径规划中的应用综述[J].计算机工程与应用, 2020, 56(8): 10-19.
ZHANG S C, PU J X, SI Y N, et al. Survey on application of ant colony algorithm in path planning of mobile robot[J]. Computer Engineering and Applications, 2020, 56(8): 10-19.
[17] 罗雄, 钱谦, 伏云发.遗传算法解柔性作业车间调度问题应用综述[J].计算机工程与应用, 2019, 55(23): 15-21.
LUO X, QIAN Q, FU Y F. Review of application of genetic algorithms for solving flexible job shop scheduling problems[J]. Computer Engineering and Applications, 2019, 55(23): 15-21.
[18] 史春天, 曾艳阳, 侯守明. 群体智能算法在图像分割中的应用综述[J].计算机工程与应用, 2021, 57(8): 36-47.
SHI C T, ZENG Y Y, HOU S M. Summary of application of swarm intelligence algorithms in image segmentation[J]. Computer Engineering and Applications, 2021, 57(8): 36-47.
[19] HATAMI S, RUIZ R, ANDRéS-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.
[20] 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?Cybernetics-Systems, 2016, 46(1): 139-149.
[21] ZHANG Z Q, QIAN B, HU R, et al. A matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem[J]. Swarm?and Evolutionary Computation, 2021, 60: 100785.
[22] FERONE D, HATAMI S, GONZALEZ E M, et al. A biased-randomized iterated local search for the distributed assembly permutation flow-shop problem[J]. International Transactions in Operational Research, 2020, 27: 1368-1391.
[23] LIN J, ZHANG S. An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem[J]. Computer & Industrial Engineering, 2016, 97: 128-136.
[24] LIN J, WANG Z J, LI X. A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem[J]. Swarm and Evolutionary Computation, 2017, 36: 124-135.
[25] SONG H B, YANG Y H, LIN J, et al. An effective hyper heuristic-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem[J]. Applied Soft Computing, 2023, 135: 110022.
[26] LI X T, ZHANG X, YIN M H, et al. A genetic algorithm for the distributed assembly permutation flowshop scheduling problem[C]//Proceeding of the 2015 IEEE Congress on Evolutionary Computation, Sendai, May 25-28, 2015. Piscataway, NJ: IEEE, 2015: 3096-3101.
[27] ZHANG X, LI X T, YIN M H. An enhanced genetic algorithm for the distributed assembly permutation flowshop scheduling problem[J]. International Journal of Bio-Inspired Computation, 2020, 15(2): 113-124.
[28] OCHI H, DRISS O B. Scheduling the distributed assembly flowshop problem to minimize the makespan[J]. Procedia Computer Science, 2019, 164: 471-477.
[29] 黄佳琳, 张丫丫, 顾幸生.基于改进生物地理学优化算法的分布式装配置换流水车间调度问题[J].华东理工大学学报(自然科学版), 2020, 46(6):758-769.
HUANG J L, ZHANG Y Y, GU X S. Distributed assembly permutation flowshop scheduling problem based on modified biogeography-based optimization[J].?Journal of East China University of Science and Technology (Natural Science Edition), 2020, 46(6): 758-769.
[30] 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.
[31] HUANG Y Y, PAN Q K, HUANG J P, et al. An improved iterated greedy algorithm for the distributed assembly permutation flowshop scheduling problem[J]. Computer & Industrial Engineering, 2020, 152: 107021.
[32] ZHANG Z Q, HU R, QIAN B, et al. A matrix cube-based estimation of distribution algorithm for the energy-efficient distributed assembly permutation flow-shop scheduling problem[J]. Expert Systems with Applications, 2022, 194: 116484.
[33] 佘明哲, 钱斌, 胡蓉, 等.混合交叉熵算法求解模糊分布式装配流水线低碳调度问题[J].控制理论与应用, 2020, 37(10): 2081-2092.
SHE M Z, QIAN B, HU R, et al. Hybrid cross-entropy algorithm for fuzzy distributed assembly permutation flow-shop low-carbon scheduling problem[J]. Control Theory & Applications, 2020, 37(10): 2081-2092.
[34] 张梓琪, 钱斌, 胡蓉, 等.基于多维EDA算法的低碳分布式装配流水车间调度[J].控制与决策, 2022, 37(5):1367-1377.
ZHANG Z Q, QIAN B, HU R, et al. Multidimensional estimation of distribution algorithm for low carbon scheduling of distributed assembly permutation flow-shop[J]. Control and Decision, 2022, 37(5): 1367-1377.
[35] 李浩然, 高亮, 李新宇.基于离散人工蜂群算法的多目标分布式异构零等待流水车间调度方法[J].机械工程学报, 2023, 59(2): 291-306.
LI H R, GAO L, LI X Y. Discrete artificial bee colony algorithm for multi-objective distributed heterogeneous no-wait flowshop scheduling problem[J]. Journal of Mechanical Engineering, 2023, 59(2): 291-306.
[36] ZHAO F Q, XU Z S, WANG L, et al. A population-based iterated greedy algorithm for distributed assembly no-wait flow-shop scheduling problem[J]. IEEE Transactions on Industrial Informatics, 2023, 19(5): 6692-6705.
[37] ZHAO F Q, ZHANG L, CAO J, et al. A cooperative water wave optimization algorithm with reinforcement learning for the distributed assembly no-idle flowshop scheduling problem[J]. Computers & Industrial Engineering, 2020, 153: 107082.
[38] SHAO Z S, SHAO W S, PI D C. Effective constructive heuristic and metaheuristic for the distributed assembly blocking flow-shop scheduling problem[J]. Applied Intelligence, 2020, 50: 4647-4669.
[39] DU S L, ZHOU W J, WU D K, et al. An effective discrete monarch butterfly optimization algorithm for distributed blocking flow shop scheduling with an assembly machine[J]. Expert Systems with Applications, 2023, 225: 120113.
[40] 赵付青, 杜松霖, 曹洁, 等.分布式装配阻塞流水车间调度算法研究[J].华中科技大学学报(自然科学版), 2022, 50(5):138-142.
ZHAO F Q, DU S L, CAO J, et al. Study on distributed assembly blocking flow shop scheduling algorithm[J]. Journal Huazhong University of Science & Technology (Natural Science Edition), 2022, 50(5): 138-142.
[41] ZHAO F Q, DI S L, WANG L. A self-learning hyper-heuristic for the distributed assembly blocking flow shop scheduling problem with total flowtime criterion[J]. Engineering Applications of Artificial Intelligence, 2022, 116: 105418.
[42] ZHAO F Q, SHAO D Q, WANG L, et al. An effective water wave optimization algorithm with problem-specific knowledge for the distributed assembly blocking flow-shop scheduling problem[J]. Knowledge-Based Systems, 2022, 243: 108471.
[43] XIONG F L, XING K Y. Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time[J]. International Journal of Production Research, 2014, 52: 2743-2766.
[44] XIONG F L, XING K Y, FENG W, et al. Minimizing the total completion time in a distributed two stage assembly system with setup times[J]. Computer & Operation Research, 2014, 47: 92-105.
[45] DENG J, WANG L, WANG S Y, et al. A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem[J]. International Journal of Production Research, 2016, 54(12): 3561-3577.
[46] HUANG J L, GU X S. Distributed assembly permutation flow-shop scheduling problem with sequence-dependent set-up times using a novel biogeography-based optimization algorithm[J]. Engineering Optimization, 2022, 54(4): 593-613.
[47] LI M, SU B, LEI D M. A novel imperialist competitive algorithm for fuzzy distributed assembly flow shop scheduling[J]. Journal of Intelligent and Fuzzy Systems, 2021, 40: 4545-4561.
[48] 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.
[49] BEHESHTINIA M A, GHASEMI A, FAROKHNIA M. Supply chain scheduling and routing in multi-site manufacturing system (case study: a drug manufacturing company)[J]. Journal of Modeling in Management, 2018, 13(1): 27-49.
[50] BEHESHTINIA M A, GHASEMI A. A multi-objective and integrated model for supply chain scheduling optimization in a multi-site manufacturing system[J]. Engineering Optimization, 2018, 50(9): 1415-1433.
[51] YANG S L, XU Z G. The distributed assembly permutation flowshop scheduling problem with flexible assembly and batch delivery[J]. International Journal of Production Research, 2021, 59(13): 4053-4071.
[52] LEI D M, LI G L. Distributed energy-efficient assembly scheduling problem with transportation capacity[J]. Symmetry-Basel, 2022, 14(11): 2225.
[53] WANG J, TANG H T, LEI D M. A Q-learning artificial bee colony for distributed assembly flow shop scheduling with factory eligibility, transportation capacity and setup time[J]. Engineering Applications of Artificial Intelligence, 2023, 123: 106230.
[54] PAN Q K, LIANG G C, LI X, et al. Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem[J]. Applied Soft Computing, 2019, 81: 105492.