A review of distributed flow shop scheduling

doi:10.16731/j.cnki.1671-3133.2024.10.019

Abstract

Abstract: The rapid development of new manufacturing modes such as intelligent manufacturing and network manufacturing has brought new opportunities and challenges to the promotion of distributed production mode. At present, domestic and foreign scholars have summarized and analyzed the problems of flexible job-shop scheduling and distributed job-shop scheduling, but there is still a lack of overview of distributed flow shop scheduling. Taking distributed flow shop as the research object, it summarizes the existing research results from the aspects of operation mode analysis, optimization target design, special constraint characterization, model solving methods and engineering applications, and prospects the future research direction of distributed flow shop scheduling.

Key words: distributed flow shop scheduling, optimization objective, restraint, algorithm, engineering application

CLC Number:

TP18

LI Meiyan, GAO Qin. A review of distributed flow shop scheduling[J]. Modern Manufacturing Engineering, 2024, 529(10): 146-157.

References

[1] NADERI, RUIZ. A scatter search algorithm for the distributed permutation flowshop scheduling problem[J]. European Journal of Operational Research, 2014,239(2):323-334.
[2] 孙爱中.我国机械制造业的发展现状与发展前景[J].机械管理开发,2021,36(8):291-292.
[3] JIA H Z,JERRY Y H Fuh, ANDREW Y C Nee, et al. Web-based multi-functional scheduling system for a distributed manufacturing environment[J]. Concurrent Engineering, 2002,10(1):27-39.
[4] JIA H, NEE A, FUH J, et al. A modified genetic algorithm for distributed scheduling problems[J]. Journal of Intelligent Manufacturing, 2003,14(3/4):351-362.
[5] SA Buncuoglu I. Distributed scheduling: a review of concepts and applications[J].Toptal A,International Journal of Production Research,2010,48(18):5235-5262.
[6] BHNAMIAN J, GHOMI S M T. A survey of multi-factory scheduling[J]. Journal of Intelligent Manufacturing,2016,27(1):231-249.
[7] 王凌,邓瑾,王圣尧.分布式车间调度优化算法研究综述[J].控制与决策,2016,31(1):1-11.
[8] 王思涵,李新宇,高亮,等.分布式车间调度研究综述[J].华中科技大学学报(自然科学版),2022,50(6):1-10.
[9] 余斌煌.柔性流水车间调度问题综述[J].现代制造工程,2022(9):154-162,71.
[10] PEREZ-GONZALEZ P, FRAMINAN J M. A review and classification on distributed permutation flowshop schedu-ling problems[J]. European Journal of Operational Research, 2023,312(1):1-21.
[11] PAN Q K, GAO L, WANG L. An effective cooperative co-evolutionary algorithm for distributed flowshop group scheduling problems[J]. IEEE Transactions on Cybernetics, 2020,52(7):5999-6012.
[12] HUANG Y Y, PAN Q K, HUANG J P. An improved iterated greedy algorithm for the distributed assembly permutation flowshop scheduling problem[J]. Computers & Industrial Engineering, 2021,152:107021.
[13] DENG J, WANG L. A competitive memetic algorithm for multi-objective distributed permutation flow shop scheduling problem[J]. Swarm and Evolutionary Computation, 2017,32:121-131.
[14] LI Y Z, PAN Q K, GAO K Z, et al. A green scheduling algorithm for the distributed flow shop problem[J]. Applied Soft Computing, 2021,109:107526.
[15] NADERI B, RUIZ R. The distributed permutation flow shop scheduling problem[J]. Computers & operations research, 2010,37(4):754-768.
[16] 周蓉. 基于改进遗传算法的分布式柔性车间调度问题研究[D].南昌:南昌航空大学,2012.
[17] VAIRAKTARAKIS G,ELHAFSI M. The use of flowlines to simplify routing complexity in two-stage flowshops[J]. Iie Transactions, 2000,32(8):687-699.
[18] YING K C, LIN S W. Minimizing makespan for the distributed hybrid flowshop scheduling problem with multi-processor tasks[J]. Expert systems with applications, 2018,92:132-141.
[19] 李庆华. 基于鲸鱼群算法的分布式装配流水车间调度[D].济南:山东师范大学,2021.
[20] HATAMI S,RUIZ R,ANDRES R. The distributed assembly permutation flowshop scheduling problem[J]. International Journal of Production Research, 2013,51(17):5292-5308.
[21] 李颖俐.基于人工蜂群算法的分布式混合流水车间调度方法研究[D].武汉:华中科技大学,2021.
[22] 李红.分布式车间调度研究方法研究[D].沈阳:沈阳工业大学,2008.
[23] 张晓辉.分布式阻塞流水车间调度方法研究[D].徐州:中国矿业大学,2021.
[24] QIN H, LI T, TENG Y, et al. Integrated production and distribution scheduling in distributed hybrid flow shops[J]. Memetic Computing, 2021,13(2):185-202.
[25] RIIFAI A P, MARA S T W, SUDIARSO A. Multi-objective distributed reentrant permutation flow shop scheduling with sequence-dependent setup time[J]. Expert Systems with Applications, 2021,183:115339.
[26] 孙志卫. 改进遗传算法求解分布式置换流水车间调度问题[D].天津:天津理工大学,2020.
[27] 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.
[28] LEI D, DAI T. A Shuffled Frog-Leaping Algorithm with Cooperations for Distributed Assembly Hybrid-Flow Shop Scheduling with Factory Eligibility[J]. Symmetry, 2023,15(4):786.
[29] CAI J, LEI D, WANG J, et al. A novel shuffled frog-leaping algorithm with reinforcement learning for distributed assembly hybrid flow shop scheduling[J]. International Journal of Production Research, 2023,61(4):1233-1251.
[30] JIA Yanhe, YAN QI, WANG Hongfeng. Q-learning driven multi-population memetic algorithm for distributed three-stage assembly hybrid flow shop scheduling with flexible preventive maintenance[J]. Expert Systems with Applications, 2023,120837.
[31] SHAO Weishi,SHAO Zhongshi,PI Dechang. Modeling and multi-neighborhood iterated greedy algorithm for distributed hybrid flow shop scheduling problem[J]. Knowledge-Based Systems, 2020,194:105527.
[32] 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.
[33] MAO J Y,PAN Q K,MIAO Z H,et al. A hash map-based memetic algorithm for the distributed permutation flowshop scheduling problem with preventive maintenance to minimize total flowtime[J]. Knowledge-Based Systems, 2022,242:108413.
[34] XIONG Fuli,CHU Mengling,LI Zhi,et al. Just-in-time scheduling for a distributed concrete precast flow shop system[J]. Computers & Operations Research, 2021,129:105204.
[35] CAI J, LU S, CHENG J, et al. Collaborative variable neighborhood search for multi-objective distributed scheduling in two-stage hybrid flow shop with sequence-dependent setup times[J]. Scientific Reports, 2022,12(1):15724.
[36] LEI Deming, SU Bin. A multi-class teaching-learning-based optimization for multi-objective distributed hybrid flow shop scheduling[J]. Knowledge-Based Systems, 2023,263:110252.
[37] WANG Zhen,DENG Qianwang,ZHANG Like,et al. Joint optimization of integrated mixed maintenance and distributed two-stage hybrid flow-shop production for multi-site maintenance requirements[J]. Expert Systems with Applications, 2023,215:119422.
[38] ZHENG Jie,WANG Ling,WANG Jingjing. A cooperative coevolution algorithm for multi-objective fuzzy distributed hybrid flow shop[J]. Knowledge-Based Systems, 2020,194:105536.
[39] DI Yuanzhu,DENG Libao,LIU Tong. A Knowledge-Based Cooperative Differential Evolution Algorithm for Energy-Efficient Distributed Hybrid Flow-Shop Rescheduling Problem[J]. Processes, 2023,11(3):755.
[40] GENG Kaifeng, YE Chunming. A memetic algorithm for energy-efficient distributed re-entrant hybrid flow shop scheduling problem[J]. Journal of Intelligent & Fuzzy Systems, 2021,41(2):3951-3971.
[41] HAN Xue, HAN Yuyan, ZHANG Biao, et al. An effective iterative greedy algorithm for distributed blocking flowshop scheduling problem with balanced energy costs criterion[J].Applied Soft Computing Journal, 2022,129:109502.
[42] SCHULZ Sven,SCHÖNHEIT Martin,NEUFELD Jani S. Multi-objective carbon-efficient scheduling in distributed permutation flow shops under consideration of transportation efforts[J]. Journal of Cleaner Production, 2022,365:132551.
[43] SHAO Weishi,SHAO Zhongshi,PI Dechang. A network memetic algorithm for energy and labor-aware distributed heterogeneous hybrid flow shop scheduling problem[J]. Swarm and Evolutionary Computation, 2022,75:101190.
[44] DONG Jun,YE Chunming. Green scheduling of distributed two-stage reentrant hybrid flow shop considering distributed energy resources and energy storage system[J]. Computers & Industrial Engineering, 2022,169:108146.
[45] FATHOLLAHI F, AMIR M,WOODWARD L,et al. Sustainable distributed permutation flow-shop scheduling model based on a triple bottom line concept[J]. Journal of Industrial Information Integration, 2021,24:100233.
[46] LU Chao,GAO Liang,GONG Wenyin,et al. Sustainable scheduling of distributed permutation flow-shop with non-identical factory using a knowledge-based multi-objective memetic optimization algorithm[J]. Swarm and Evolutionary Computation, 2021,60:100803.
[47] 隋杨.考虑优化应急响应时间的平行机调度研究[D].上海:东华大学,2022.
[48] 唐红涛,李悦,王磊. 模糊分布式柔性作业车间调度问题的求解算法[J]. 华中科技大学学报(自然科学版), 2022,50(6):81-88.
[49] CAI Jingcao,LEI Deming. A cooperated shuffled frog-leaping algorithm for distributed energy-efficient hybrid flow shop scheduling with fuzzy processing time[J]. Complex & Intelligent Systems, 2021,7(5):2235-2253.
[50] WANG Lei, LI Dongdong. Fuzzy distributed hybrid flow shop scheduling problem with heterogeneous factory and unrelated parallel machine: A shuffled frog leaping algorithm with collaboration of multiple search strategies[J]. IEEE Access, 2020,8:214209-214223.
[51] ZHENG J, WANG L, WANG J. A cooperative coevolution algorithm for multi-objective fuzzy distributed hybrid flow shop[J]. Knowledge-Based Systems, 2020,194:105536.
[52] SHAO Z, SHAO W, PI D. Effective heuristics and metaheuristics for the distributed fuzzy blocking flow-shop scheduling problem[J]. Swarm and Evolutionary Computation, 2020,59:100747.
[53] SHAO Z, SHAO W, PI D. Effective constructive heuristic and metaheuristic for the distributed assembly blocking flow-shop scheduling problem[J]. Applied Intelligence, 2020,50:4647-4669.
[54] YANG Y, LI X. A knowledge-driven constructive heuristic algorithm for the distributed assembly blocking flow shop scheduling problem[J]. Expert Systems with Applications, 2022,202:117269.
[55] SHAO Z, SHAO W, PI D. Effective constructive heuristic and iterated greedy algorithm for distributed mixed blocking permutation flow-shop scheduling problem[J]. Knowledge-Based Systems, 2021,221:106959.
[56] QIN H X, HAN Y Y, LIU Y P, et al. A collaborative iterative greedy algorithm for the scheduling of distributed heterogeneous hybrid flow shop with blocking constraints[J]. Expert Systems with Applications, 2022,201:117256.
[57] QIN H, HAN Y, CHEN Q, et al. Energy-Efficient Iterative Greedy Algorithm for the Distributed Hybrid Flow Shop Scheduling with Blocking Constraints[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2023,7(5):1442-1457.
[58] ZHANG G, XING K. Differential evolution metaheuristics for distributed limited-buffer flowshop scheduling with makespan criterion[J]. Computers & Operations Research, 2019,108:33-43.
[59] LU C, HUANG Y, MENG L, et al. A Pareto-based collaborative multi-objective optimization algorithm for energy-efficient scheduling of distributed permutation flow-shop with limited buffers[J]. Robotics and Computer-Integrated Manufacturing, 2022,74:102277.
[60] ZHU N,ZHAO F,WANG L,et al.A discrete learning fruit fly algorithm based on knowledge for the distributed no-wait flow shop scheduling with due windows[J]. Expert Systems with Applications,2022,198:116921.
[61] ZHAO F, ZHAO J, 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.
[62] 李浩然,高亮,李新宇. 基于离散人工蜂群算法的多目标分布式异构零等待流水车间调度方法[J]. 机械工程学报,2023,59(2):291-306.
[63] SHAO W, PI D, SHAO Z. Optimization of makespan for the distributed no-wait flow shop scheduling problem with iterated greedy algorithms[J]. Knowledge-Based Systems, 2017,137:163-181.
[64] 陈水琳,郑建国.考虑准备时间的分布式混合零空闲置换流水车间调度问题[J/OL].计算机集成制造系统,2024:1-32[2024-08-02].http://kns.cnki.net/kcms/detail/11.5946.TP.20230927.1142.010.html.
[65] LI Y Z, PAN Q K, LI J Q, et al. An adaptive iterated greedy algorithm for distributed mixed no-idle permutation flowshop scheduling problems[J]. Swarm and Evolutionary Computation, 2021,63:100874.
[66] YING K C, LIN S W, CHENG C Y, et al. Iterated reference greedy algorithm for solving distributed no-idle permutation flowshop scheduling problems[J]. Computers & industrial engineering, 2017,110:413-423.
[67] CHEN J, WANG L, PENG Z. A collaborative optimization algorithm for energy-efficient multi-objective distributed no-idle flow-shop scheduling[J]. Swarm and Evolutionary Computation, 2019,50:100557.
[68] 郭恒伟. 基于果蝇优化算法的分布式置换流水车间调度问题研究[D].聊城:聊城大学,2022.
[69] 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.
[70] HUANG J P, PAN Q K, MIAO Z H, et al. Effective constructive heuristics and discrete bee colony optimization for distributed flowshop with setup times[J]. Engineering Applications of Artificial Intelligence, 2021,97:104016.
[71] WANG J, WANG L. A cooperative memetic algorithm with feedback for the energy-aware distributed flow-shops with flexible assembly scheduling[J]. Computers & Industrial Engineering, 2022,168:108126.
[72] ZHAO F, BAO H, WANG L, et al. A heuristic and meta-heuristic based on problem-specific knowledge for distributed blocking flow-shop scheduling problem with sequence-dependent setup times[J]. Engineering Applications of Artificial Intelligence, 2022,116:105443.
[73] SHAO W S, PI D C, SHAO Z S. A Pareto-based estimation of distribution algorithm for solving multi objective distributed no-wait flow-shop scheduling problem with sequence-dependent setup time[J]. IEEE Transactions on Automation Science and Engineering, 2019,16(3):1344-1360.
[74] ROSSI F L, NAGAANO M S. Heuristics and iterated greedy algorithms for the distributed mixed no-idle flowshop with sequence-dependent setup times[J]. Computers & Industrial Engineering, 2021,157:107337.
[75] WU X, XIE Z. Improved MOEA/D with local search for solving multi-stage distributed reentrant hybrid flow shop scheduling problem[J]. Expert Systems with Applications, 2023,232:120893.
[76] RIFAI A P, MARA S T W, SUDIARSO A. Multi-objective distributed reentrant permutation flow shop scheduling with sequence-dependent setup time[J]. Expert Systems with Applications, 2021,183:115339.
[77] YING K C, LIN S W. Minimizing makespan for the distributed hybrid flowshop scheduling problem with multipro-cessor tasks[J]. Expert systems with applications, 2018,92:132-141.
[78] GHOLAMI H, SUN H. Toward automated algorithm configuration for distributed hybrid flow shop scheduling with multiprocessor tasks[J]. Knowledge-Based Systems, 2023,264:110309.
[79] CAI J, ZHOU R, LEI D. Dynamic shuffled frog-leaping algorithm for distributed hybrid flow shop scheduling with multiprocessor tasks[J]. Engineering Applications of Artificial Intelligence, 2020,90:103540.
[80] SHAO W, SHAO Z, PI D. Modelling and optimization of distributed heterogeneous hybrid flow shop lot-streaming scheduling problem[J]. Expert Systems with Applications, 2023,214:119151.
[81] LI J Q, SONG M X, WANG L, et al. Hybrid artificial bee colony algorithm for a parallel batching distributed flow-shop problem with deteriorating jobs[J]. IEEE transactions on cybernetics, 2019,50(6):2425-2439.
[82] CHENG Y, TAO F, LIU Y,et al. Energy-aware resource service scheduling based on utility evaluation in cloud-manufacturing system[J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture,2013,227(12):1901-1915.
[83] AKBARIPOUR H,HOUSHMAND M, VAN WOENSEL T, et al. Coud manufacturing service selection optimization andcheduling with transportation considerations: Mixed-integer programming models[J]. The International Journaof Advanced Manufacturing Technology,2018,95(1/2/3/4):43-70.
[84] LIU Y, XU X, ZHANG L. et al. An extensible model for multitask-oriented service composition and scheduling incloud manufacturing[J]. Journal of Computing and Information Science in Eneineering, 2016,16(4):041009.
[85] LIU Y, XU X, ZHANG L, et al. Workload-based multi-task scheduling in cloud manufacturing[J]. Robotics and Computer-integrated manufacturing, 2017,45:3-20.
[86] ZHOU L, ZHANG L, SARKER B R, et al. An event-triggered dynamic scheduling method for randomly arriving tasks in cloud manufacturing[J]. International Journal of Computer Integrated Manufacturing, 2018,31(3):318-333.
[87] CHEN J, WANG L, PENG Z. A collaborative optimization algorithm for energy-efficient multi-objective distributed no-idle flow-shop scheduling[J]. Swarm and Evolutionary Computation, 2019,50:100557.
[88] XIANG F, JIANG G Z, XU L L, et al. The case-library method for service composition and optimal selection of bigmanufacturing data in cloud manufacturing system[J]. The International Journal of Advanced Manufacturing Technolo-gy,2016,84(1/2/3/4):59-70.
[89] HAMZADAY A. An effective benders decomposition algorithm for solving the distributed permutation flowshop scheduling problem[J]. Computers & Operations Research, 2020,123:105006.
[90] 钱斌,刘荻飞,胡蓉,等. 混合迭代贪婪算法求解准时生产分布式流水线调度问题[J]. 控制与决策,2022,37(11):3042-3051.
[91] 王建华,邱荣根,王恒. 基于多目标混合迭代贪婪算法的分布式混合流水车间调度问题[J/OL]. 计算机集成制造系统,1-19[2024-10-15]. https://doi.org/10.13196/j.cims.2024.0195.
[92] SCHULZ S, SCHONHEIT M, NEUFELD J S. Multi-objective carbon-efficient scheduling in distributed permutation flow shops under consideration of transportation efforts[J]. Journal of Cleaner Production, 2022,365:132551.
[93] MIYATA H H, NAGNO M S. An iterated greedy algorithm for distributed blocking flow shop with setup times and maintenance operations to minimize makespan[J]. Computers & Industrial Engineering, 2022,171:108366.
[94] MIYATA H H, NAGANO M S. Optimizing distributed no-wait flow shop scheduling problem with setup times and maintenance operations via iterated greedy algorithm[J]. Journal of manufacturing Systems, 2021,61:592-612.
[95] 黄元元,钱斌,吴丽萍,等.混合果蝇算法求解分布式异构并行机调度[J].控制工程,2020,27(2):254-263.
[96] CUI H, LI X, GAO L. An improved multi-population genetic algorithm with a greedy job insertion inter-factory neighborhood structure for distributed heterogeneous hybrid flow shop scheduling problem[J]. Expert Systems with Applications, 2023,222:119805.
[97] LI Y Z, PAN Q K, GAO K Z, et al. A green scheduling algorithm for the distributed flow-shop problem[J]. Applied Soft Computing, 2021,109:107526.
[98] MOU J, DUAN P, GAO L, et al. An effective hybrid collaborative algorithm for energy-efficient distributed permutation flow-shop inverse scheduling[J]. Future Generation Computer Systems, 2022,128:521-537.
[99] 王光辰. 基于Memetic算法的分布式车间调度方法研究[D].武汉:华中科技大学,2021.
[100] HOU Y, WANG H, FU Y, et al. Multi-Objective brain storm optimization for integrated scheduling of distributed flow shop and distribution with maximal processing quality and minimal total weighted earliness and tardiness[J]. Computers & Industrial Engineering, 2023,179:109217.
[101] HOU Y, FU Y, GAO K, et al. Modelling and optimization of integrated distributed flow shop scheduling and distribution problems with time windows[J]. Expert Systems with Applications, 2022,187:115827.
[102] ZHAO F, XU Z, BAO H, et al. A cooperative whale optimization algorithm for energy-efficient scheduling of the distributed blocking flow-shop with sequence-dependent setup time[J]. Computers & Industrial Engineering, 2023,178:109082.
[103] WANG G, GAO L, LI X, et al. Energy-efficient distributed permutation flow shop scheduling problem using a multi-objective whale swarm algorithm[J]. Swarm and Evolutionary Computation, 2020,57:100716.
[104] WANG H, FU Y, HUANG M, et al. A NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem[J]. Computers & Industrial Engineering, 2017,113:185-194.
[105] ZHAO F, ZHAO L, WANG L, et al. An ensemble discrete differential evolution for the distributed blocking flowshop scheduling with minimizing makespan criterion[J]. Expert Systems with Applications, 2020,160:113678.
[106] LEI D, XI B. Diversified teaching-learning-based optimization for fuzzy two-stage hybrid flow shop scheduling with setup time[J]. Journal of Intelligent & Fuzzy Systems, 2021,41(2):4159-4173.
[107] SHAO Z, SHAO W, PI D. LS-HH: a learning-based selection hyper-heuristic for distributed heterogeneous hybrid blocking flow-shop scheduling[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2022,7(1):111-127.
[108] 肖航. 基于多智能体的智能工厂生产调度研究[D].绵阳:西南科技大学,2023.
[109] 李忠畅.Y公司分布式制造生产调度研究[D].徐州:中国矿业大学,2023.
[110] 吴锐.面向建材装备制造企业的分布式柔性作业车间调度问题研究[D].武汉:武汉理工大学,2019.
[111] 吴清华.分布式加工与集中式装配的运输集成调度研究与应用验证[D].重庆:重庆大学,2022.
[112] 姜卓群.基于遗传算法的A公司大齿轮生产调度优化研究[D].徐州:中国矿业大学,2022.
[113] LU Chao,GAO Liang,YI Jin,et al. Energy-efficient scheduling of distributed flow shop with heterogeneous factories: A real-world case from automobile industry in China[J].IEEE Transactions on Industrial Informatics,2020,17(10):6687-6696.
[114] 丁懿宁,徐哲,赵松,等.考虑员工请假情形的多技能分布式资源受限多项目反应型调度优化[J/OL].中国管理科学,2023:1-14[2023-10-20].https://doi.org/10.16381/j.cnki.issn1003-207x.2022.2456.
[115] 林文智.考虑需求响应不确定性的多园区综合能源系统分布式协同优化调度[D].广州:华南理工大学,2022.
[116] 李政阳,云昕,杨怡欣,等.在轨空间智能制造:分布式调度建模与优化[J].系统工程理论与实践,2019,39(3):705-724.