增强三维分布估计算法求解分布式生产-运输-装配集成调度问题

doi:10.3901/JME.2024.02.323

机械工程学报 ›› 2024, Vol. 60 ›› Issue (2): 323-341.doi: 10.3901/JME.2024.02.323

扫码分享

增强三维分布估计算法求解分布式生产-运输-装配集成调度问题

张博茹¹, 胡蓉^1,2, 钱斌^1,2, 金怀平¹, 向凤红¹

1. 昆明理工大学信息工程与自动化学院昆明 650500;
2. 昆明理工大学云南省人工智能重点实验室昆明 650500

收稿日期:2023-01-03 修回日期:2023-08-18 出版日期:2024-01-20 发布日期:2024-04-09
通讯作者: 胡蓉(通信作者)，女，1974年出生，副教授，硕士研究生导师。主要研究方向为智能优化调度、物流优化。E-mail：ronghu@vip.163.com
作者简介:张博茹，女，1998年出生。主要研究方向为智能算法与优化调度。E-mail：2233289476@qq.com
钱斌，男，1976年出生，教授，博士研究生导师。主要研究方向为优化调度理论与方法、智能优化方法。E-mail：bin.qian@vip.163.com
金怀平，男，1987年出生，副教授，硕士研究生导师。主要研究方向为机器学习与数据挖掘。E-mail：jinhuaiping@gmail.com
向凤红，男，1964年出生，教授，硕士研究生导师。主要研究方向为智能优化方法。E-mail：xiangfh5447@sina.com
基金资助:
国家自然科学基金(62173169，61963022)和云南省应用基础研究重点(202201AS070030)资助项目。

Enhanced Three-dimensional Estimation of Distribution Algorithm for Solving Integrated Scheduling Problem of Distributed Production, Transportation and Assembly

ZHANG Boru¹, HU Rong^1,2, QIAN Bin^1,2, JIN Huaiping¹, XIANG Fenghong¹

1. Faculty of Information Engineering and Automation， Kunming University of Science and Technology，Kunming 650500;
2. Yunnan Key Laboratory of Artificial Intelligence， Kunming University of Science and Technology，Kunming 650500

Received:2023-01-03 Revised:2023-08-18 Online:2024-01-20 Published:2024-04-09

摘要/Abstract

摘要： 针对一类广泛存在的分布式生产-运输-装配集成调度问题(Integrated scheduling problem of distributed production, transportation and assembly, ISPDPTA)，建立问题模型并提出一种增强三维分布估计算法(Enhanced three-dimensional estimation of distribution algorithm, E3DEDA)进行求解。在E3DEDA的全局搜索部分，先根据ISPDPTA的问题特性，对包含工厂信息的工件与产品进行多段编码，并依据最短路径规则获得各车辆路径；再采用双三维概率模型分别学习和积累种群中较优个体的工件块与产品块结构及其位置信息，并采样生成新个体，从而增强算法发现优质解空间区域的能力。在E3DEDA的局部搜索部分，设计自适应变邻域局部搜索来增强算法的局部搜索能力。具体而言，针对问题各阶段特性，设计10种有效的邻域操作组成备选集合，并采用二维概率模型学习由不同邻域操作所构成的优质邻域结构信息，进而采样生成合理的邻域操作排列并依次执行，以实现对全局搜索所发现优质区域的深入搜索。此外，设计块结构概率评价更新机制，可提升算法执行效率。最后，通过仿真试验与算法对比验证E3DEDA可有效求解ISPDPTA。

关键词: 分布式生产, 车辆运输, 集成调度, 三维分布估计算法, 块结构

Abstract: Aiming at a kind of integrated scheduling problem of distributed production, transportation and assembly(ISPDPTA), which widely exists in real-life applications, the model of the problem is established first. And then, an enhanced three-dimensional estimation of distribution algorithm(E3DEDA) is proposed to solve the model. In global search stage, E3DEDA uses a multi-segment encoding mechanism to represent jobs and productions that contain factory information based on the characteristics of ISPDPTA, in which each vehicle path is determined by applying the shortest path rule. Besides, two three-dimensional probability matrices are adopted to enhance the ability of E3DEDA for finding promising search regions. That is, the matrices separately learn and accumulate the information about the structure and location of job blocks and product blocks stemming from elite individuals found during the search process. Thereby, new individuals are generated by sampling the two matrices. In local search stage, E3DEDA adopts adaptive variable neighborhood local search to improve the local search ability of the algorithm. Especially, ten neighborhood operations are used to form the alternative set based on the characteristics of each stage of ISPDPTA, and a two-dimensional probability matrix is used to learn the information about high-quality neighborhood structures regarding different neighborhood operations. By sampling the matrix, permutations are generated and a series of neighborhood operations are in turn performed on the solutions of E3DEDA, so as to intensively examine promising search regions discovered by the global search stage. Moreover, a probability evaluation updating mechanism of block structure is proposed to improve the efficiency of the algorithm. Finally, simulations and comparisons demonstrate that E3DEDA can effectively solve ISPDPTA.

Key words: distributed production, vehicle transportation, integrated scheduling, three-dimensional estimation of distribution algorithm, block structure

中图分类号:

TP273

张博茹, 胡蓉, 钱斌, 金怀平, 向凤红. 增强三维分布估计算法求解分布式生产-运输-装配集成调度问题[J]. 机械工程学报, 2024, 60(2): 323-341.

ZHANG Boru, HU Rong, QIAN Bin, JIN Huaiping, XIANG Fenghong. Enhanced Three-dimensional Estimation of Distribution Algorithm for Solving Integrated Scheduling Problem of Distributed Production, Transportation and Assembly[J]. Journal of Mechanical Engineering, 2024, 60(2): 323-341.

参考文献

[1] 孟博洋, 李茂月, 刘献礼, 等.机床智能控制系统体系架构及关键技术研究进展[J].机械工程学报, 2021, 57(9):147-166.
MENG Boyang, LI Maoyue, LIU Xianli, et al. Research progress on architecture and key technologies of intelligent control system for machine tools[J]. Journal of Mechanical Engineering, 2021, 57(9):147-166.
[2] WANG Lihui, SHEN Weiming. Process planning and scheduling for distributed manufacturing[M]. London:Springer, 2007.
[3] YIEN J T, TSENG M M. Manufacturing systems design:A review of state-of-the-art methodologies[J]. Integrated Product, Process and Enterprise Design, 1997, 2:392-434.
[4] KAHN K B, CASTELLION G A, GRIFFIN A. The PDMA handbook of new product development[M]. New York:Wiley, 2004:203-204.
[5] 王凌, 邓瑾, 王圣尧.分布式车间调度优化算法研究综述[J].控制与决策, 2016, 31(1):1-11.
WANG Ling, DENG Jin, WANG Shengyao. Survey on optimization algorithms for distributed shop scheduling[J]. Control and Decision, 2016, 31(1):1-11.
[6] HATAMI S, RUIZ R, ANDRES-ROMANO C. The distributed assembly permutation flowshop scheduling problem[J]. International Journal of Production Research, 2013, 51(17-18):5292-5308.
[7] LIN Jian, ZHANG Shuai. An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem[J]. Computers & Industrial Engineering, 2016, 97:106869.
[8] LIN Jian, WANG Zhoujing, LI Xiaodong. A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem[J]. Swarm and Evolutionary Computation, 2017, 36:124-135.
[9] 佘明哲, 钱斌, 胡蓉, 等.混合交叉熵算法求解模糊分布式装配流水线低碳调度问题[J].控制理论与应用, 2020, 37(10):2081-2092.
SHE Mingzhe, QIAN Bin, HU Rong, et al. Hybrid cross-entropy algorithm for fuzzy distributed assembly permutation flow-shop low-carbon scheduling problem[J]. Control Theory and Applications, 2020, 37(10):2081-2092.
[10] 罗文冲, 钱斌, 胡蓉, 等.超启发式交叉熵算法求解分布式装配柔性作业车间调度问题[J].控制理论与应用, 2021, 38(10):1551-1568.
LUO Wenchong, QIAN Bin, HU Rong, et al. Hyper-heuristic cross-entropy algorithm for distributed assembly flexible job-shop scheduling problem[J]. Control Theory and Applications, 2021, 38(10):1551-1568.
[11] MOONS S, RAMAEKERS K, AN C, et al. Integrating production scheduling and vehicle routing decisions at the operational decision level:A review and discussion[J]. Computers& Industrial Engineering, 2016, 104(2):224-245.
[12] HOU Yushuang, FU Yaping, GAO Kaizhou, 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.
[13] PORNSING C, THARAWETCHARAK P, JOMTHOG P, et al. Particle swarm optimization for integrated production-distribution scheduling problem[C]//2017 3rd International Conference on Control, Automation and Robotics (ICCAR), April 24-26, 2017, Nagoya, Japan, New York:IEEE, 2017:16947630.
[14] KARAOGLAN I, KESEN S E. The coordinated production and transportation scheduling problem with a time-sensitive product:A branch-and-cut algorithm[J]. International Journal of Production Research, 2017, 55(1-2):1-22.
[15] YANG Shengluo, XU Zhigang. The distributed assembly permutation flowshop scheduling problem with flexible assembly and batch delivery[J]. International Journal of Production Research, 2020, 59(13):4053-4071.
[16] BADHOTIYA G K, SONI G, MITTAL M L. Fuzzy multi-objective optimization for multi-site integrated production and distribution planning in two echelon supply chain[J]. The International Journal of Advanced Manufacturing Technology, 2019, 102:635-645.
[17] GHARAEI A, JOLAI F, et al. A multi-agent approach to the integrated production scheduling and distribution problem in multi-factory supply chain[J]. Applied Soft Computing, 2018, 65:577-589.
[18] MARANDI F, FATEMI G S M T. Integrated multi-factory production and distribution scheduling applying vehicle routing approach[J]. International Journal of Production Research, 2019, 57(3):722-748.
[19] GHARAEI A, JOLAI F. A pareto approach for the multi-factory supply chain scheduling and distribution problem[J]. Operational Research, 2019, 21(4):2333-2364.
[20] 张梓琪, 钱斌, 胡蓉, 等.基于多维EDA算法的低碳分布式装配流水车间调度[J].控制与决策, 2022, 37(5):1367-1377.
ZHANG Ziqi, QIAN Bin, HU Rong, et al. Low carbon distributed assembly flowshop scheduling based on multi-dimensional EDA algorithm[J]. Control and Decision, 2022, 37(5):1367-1377.
[21] LARRANAGA P, LOZANO J A. Estimation of distribution algorithms:A new tool for evolutionary computation[M]. Boston:Kluwer Press, 2002.
[22] 杨海军, 李建武, 李敏强.进化算法的模式、涌现与困难性研究[M].北京:科学出版社, 2012.
YANG Haijun, LI Jianwu, LI Minqiang. Evolutionary algorithms:Schema, emergence and hardness[M]. Beijing:Science Press, 2012.
[23] WANG Kai, HUANG Yun, QIN Hu. A fuzzy logic-based hybrid estimation of distribution algorithm for distributed permutation flowshop scheduling problems under machine breakdown[J]. Journal of the Operational Research Society, 2016, 67(1):68-82.
[24] WANG Shengyao, WANG Ling. 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, 2015, 46(1):139-149.
[25] ZHANG Ziqi, QIAN Bin, HU Rong, 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.
[26] 邓超, 胡蓉, 钱斌.混合分布估计算法求解考虑同步性和准时性的三阶段装配集成调度问题[J].控制理论与应用, 2020, 37(5):1090-1102.
DENG Chao, HU Rong, QIAN Bin. Hybrid estimation of distribution algorithm for three-stage assembly integrated scheduling problem considering assembly synchronization and delivery punctuality[J]. Control Theory and Applications, 2020, 37(5):1090-1102.
[27] NADERI B, RUIZ R. The distributed permutation flowshop scheduling problem[J]. Computers& Operations Research, 2010, 37(4):754-768.
[28] MONTGOMERY D C. Design and analysis of experiments[M]. Hoboken:John Wiley and Sons, 2005.
[29] FENG Xin, XU Zhongyue. Integrated production and transportation scheduling on parallel batch-processing machines[J]. IEEE Access, 2019, 7:148393-148400.

增强三维分布估计算法求解分布式生产-运输-装配集成调度问题

Enhanced Three-dimensional Estimation of Distribution Algorithm for Solving Integrated Scheduling Problem of Distributed Production, Transportation and Assembly

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	王彦森, 冯立杰, 王金凤, 刘鹏, 赵华东. 面向节能的复杂机械零部件生产与物流集成调度[J]. 机械工程学报, 2024, 60(20): 403-416.
[2]	孙在省, 钱斌, 胡蓉, 张梓琪, 张长胜. 基于块结构性质的花粉算法求解可重入作业车间调度问题[J]. 机械工程学报, 2019, 55(16): 220-232.