基于协同优化算法的分布式装配车间调度

doi:10.19678/j.issn.1000-3428.0068736

摘要/Abstract

摘要：

在分布式调度中, 调度策略的协同优化已逐渐成为分布式调度研究者与分布式制造行业决策者的重点关注方向之一。针对带装配机的分布式阻塞流水车间调度问题DBFSP-A, 以最大装配完成时间为优化目标, 提出一种基于Q-Learning的协同优化算法QLBC。首先, 建立了以最大装配完成时间为优化目标的数学模型, 以增强DBFSP-A的可解释性, 在算法构造初始化阶段, QLBC充分利用DBFSP-A的问题特征, 分别根据加工任务的总处理时间、前置延迟时间等特定的排序规则, 构造式地产生高质量的、多样性的可行调度序列作为算法的初始解; 其次, 在QLBC的后续迭代中, 采用基于Q-Learning的协同搜索策略, 自主学习地指导当前解根据其各自状态及先验反馈选择合适的搜索操作, 从而实现全局搜索和局部搜索、加工过程与组装过程的协同进化与协同优化; 最后, 在不同实例中, 测试和检验了QLBC算法的性能。实验结果表明, 相较于其他6种先进算法, QLBC求解的可行调度序列时间平均节省32.09 h, 在提高生产效率、节约生产成本方面更具优势。

关键词: 协同优化, 分布式制造, 阻塞约束, 产品装配, Q-Learning算法

Abstract:

In distributed scheduling, collaborative optimization has gradually become one of the most important focus areas for researchers and decision-makers in distributed manufacturing. A Q-Learning-Based Collaborative (QLBC) optimization algorithm is proposed to solve the distributed blocking flow-shop scheduling problem with an assembly machine DBFSP-A, considering the maximum assembly completion time. First, a mathematical model is established with the objective of maximizing the assembly completion time to enhance the interpretability of DBFSP-A. The problem characteristics of DBFSP-A are utilized to constructively generate high-quality, high-diversity scheduling sequences based on specific ordering rules according to the total processing time and front delay. Subsequently, during QLBC iterations, a Q-Learning-based collaborative search strategy is used to achieve co-evolution and co-optimization by selecting appropriate search operations based on the respective states and prior feedback from the solutions. Finally, the performance of QLBC algorithm has been tested and verified in different instances. The experimental results and statistical analysis indicated that compared with the other six advanced algorithms, the scheduling sequence solved by QLBC saves an average of 32.09 h, which is advantageous in terms of improving productivity and saving production costs.

Key words: collaborative optimization, distributed manufacturing, blocking constraint, product assembly, Q-Learning algorithm

杜松霖, 仵大奎, 余云涛, 刘亚, 周文举. 基于协同优化算法的分布式装配车间调度[J]. 计算机工程, 2025, 51(3): 274-282.

DU Songlin, WU Dakui, YU Yuntao, LIU Ya, ZHOU Wenju. Distributed Assembly Workshop Scheduling Based on Collaborative Optimization Algorithm[J]. Computer Engineering, 2025, 51(3): 274-282.

https://www.ecice06.com/CN/Y2025/V51/I3/274

图/表 13

图1 带装配机的分布式阻塞流水车间生产过程

Fig.1 Production process of distributed blocking flow workshop with assembly machine

图2 优化目标计算实例甘特图

Fig.2 Gantt chart of optimization target calculation instance

图3 排序时间示意图

Fig.3 Schematic diagram of sorting time

图4 基于Q-Learning的协同优化策略

Fig.4 Collaborative optimation strategy based on the Q-Learning

图5 不同算法的相对百分比偏差对比

Fig.5 Comparison of relative percentage deviation of different algorithms

图6 95%置信区间结果对比

Fig.6 Comparison of 95% confidence interval results

图7 实验结果箱形图

Fig.7 Box plot of experimental results

参考文献 28

1	柴天佑, 刘强, 丁进良, 等. 工业互联网驱动的流程工业智能优化制造新模式研究展望. 中国科学(技术科学), 2022, 52 (1): 14- 25.
	CHAI T Y , LIU Q , DING J L , et al. Perspectives on industrial-Internet-driven intelligent optimized manufacturing mode for process industries. Scientia Sinica (Technologica), 2022, 52 (1): 14- 25.
2	QIAN F , ZHONG W M , DU W L . Fundamental theories and technologies for smart and optimal manufacturing in the process industry. Engineering, 2017, 3 (1): 154- 160.
3	OKWUDIRE C , MADHYASTHA H . Distributed manufacturing for and by the masses. Science, 2021, 372 (6540): 341- 342. doi: 10.1126/science.abg4924
4	王思涵, 李新宇, 高亮, 等. 分布式车间调度研究综述. 华中科技大学学报(自然科学版), 2022, 50 (6): 1- 10.
	WANG S H , LI X Y , GAO L , et al. A review of distributed shop scheduling problems. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2022, 50 (6): 1- 10.
5	蔡倩倩, 史旭华. 自适应迁移的分解多目标多任务进化算法. 计算机工程, 2023, 49 (7): 55- 64. URL
	CAI Q Q , SHI X H . Decomposition multi-objective multi-task evolutionary algorithm with adaptive transfer. Computer Engineering, 2023, 49 (7): 55- 64. URL
6	HUANG Y Y , PAN Q , GAO L , et al. A two-phase evolutionary algorithm for multi-objective distributed assembly permutation flowshop scheduling problem. Swarm and Evolutionary Computation, 2022, 74, 101128- 101141. doi: 10.1016/j.swevo.2022.101128
7	YU H , GAO K Z , MA Z F , et al. Improved meta-heuristics with Q-learning for solving distributed assembly permutation flowshop scheduling problems. Swarm and Evolutionary Computation, 2023, 80, 101335. doi: 10.1016/j.swevo.2023.101335
8	SHAO W S , SHAO Z S , PI D C . Multi-local search-based general variable neighborhood search for distributed flow shop scheduling in heterogeneous multi-factories. Applied Soft Computing, 2022, 125, 109138. doi: 10.1016/j.asoc.2022.109138
9	LUO C , GONG W Y , LU C . Knowledge-driven two-stage memetic algorithm for energy-efficient flexible job shop scheduling with machine breakdowns. Expert Systems with Applications, 2024, 235, 121149. doi: 10.1016/j.eswa.2023.121149
10	ZHANG M , TAO F , NEE A Y C . Digital twin enhanced dynamic job-shop scheduling. Journal of Manufacturing Systems, 2021, 58, 146- 156. doi: 10.1016/j.jmsy.2020.04.008
11	WANG J J , WANG L . A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020, 50 (5): 1805- 1819. doi: 10.1109/TSMC.2017.2788879
12	PAN Q , GAO L , WANG L , et al. Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem. Expert Systems with Applications, 2019, 124 (15): 309- 324.
13	BAO H Z , PAN Q K , RUIZ R , et al. A collaborative iterated greedy algorithm with reinforcement learning for energy-aware distributed blocking flow-shop scheduling. Swarm and Evolutionary Computation, 2023, 83, 101399. doi: 10.1016/j.swevo.2023.101399
14	WANG J J , WANG L . A cooperative memetic algorithm with feedback for the energy-aware distributed flow-shops with flexible assembly scheduling. Computers & Industrial Engineering, 2022, 168, 108126.
15	赖李媛君, 张霖, 任磊, 等. 工业互联网智能调度建模与方法研究综述. 计算机集成制造系统, 2022, 28 (7): 1966- 1980.
	LAI L Y J , ZHANG L , REN L , et al. Overview on intelligent scheduling models and methods for industrial Internet-of-things. Computer Integrated Manufacturing Systems, 2022, 28 (7): 1966- 1980.
16	王凌, 邓瑾, 王圣尧. 分布式车间调度优化算法研究综述. 控制与决策, 2016, 31 (1): 1- 11.
	WANG L , DENG J , WANG S Y . Survey on optimization algorithms for distributed shop scheduling. Control and Decision, 2016, 31 (1): 1- 11.
17	WANG S Y , WANG L . An estimation of distribution algorithm-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2016, 46 (1): 139- 149.
18	PAN Q K , GAO L , LI X Y , et al. Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem. Applied Soft Computing, 2019, 81, 105492.
19	SHAO W S , PI D C , SHAO Z S . Local search methods for a distributed assembly no-idle flow shop scheduling problem. IEEE Systems Journal, 2019, 13 (2): 1945- 1956.
20	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. Expert Systems with Applications, 2023, 225, 120113.
21	FRAMINAN J M , PEREZ-GONZALEZ P , FERNANDEZ-VIAGAS V . Deterministic assembly scheduling problems: a review and classification of concurrent-type scheduling models and solution procedures. European Journal of Operational Research, 2019, 273 (2): 401- 417.
22	SHAO Z S , SHAO W S , PI D C . Effective constructive heuristic and metaheuristic for the distributed assembly blocking flow-shop scheduling problem. Applied Intelligence, 2020, 50 (12): 4647- 4669.
23	YANG Y H , LI X . A knowledge-driven constructive heuristic algorithm for the distributed assembly blocking flow shop scheduling problem. Expert Systems with Applications, 2022, 202, 117269.
24	ZHAO F Q , DI S L , WANG L , et al. A self-learning hyper-heuristic for the distributed assembly blocking flow shop scheduling problem with total flowtime criterion. Engineering Applications of Artificial Intelligence, 2022, 116, 105418.
25	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. Knowledge-Based Systems, 2022, 243, 108471.
26	徐啸, 顾玲丽, 陈建平, 等. 一种智能多路径路由及子流分配协同算法. 计算机工程, 2021, 47 (9): 136-144, 152. URL
	XU X , GU L L , CHEN J P , et al. An intelligent cooperative algorithm for multi-path routing and subflow allocation. Computer Engineering, 2021, 47 (9): 136-144, 152. URL
27	李雅明, 张斌. 基于Q-learning算法解决多目标柔性作业车间调度问题. 工业控制计算机, 2023, 36 (9): 112- 114.
	LI Y M , ZHANG B . Solving multi-objective flexible job shop scheduling problem based on Q-learning algorithm. Industrial Control Computer, 2023, 36 (9): 112- 114.
28	王维祺, 叶春明, 谭晓军. 基于Q学习算法的作业车间动态调度. 计算机系统应用, 2020, 29 (11): 218- 226.
	WANG W Q , YE C M , TAN X J . Job shop dynamic scheduling based on Q-learning algorithm. Computer Systems & Applications, 2020, 29 (11): 218- 226.

[1]	周运腾, 张雪英, 李凤莲, 刘书昌, 焦江丽, 田豆. Q-learning算法优化的SVDPP推荐算法[J]. 计算机工程, 2021, 47(2): 46-51.
[2]	施钊, 孙长印, 江帆. 毫米波网络中基于Q-Learning的阻塞感知功率分配[J]. 计算机工程, 2020, 46(12): 185-192.
[3]	黄郡, 单洪, 满毅, 陈娟. 基于分布式优化的协同干扰任务分配研究[J]. 计算机工程, 2011, 37(21): 264-266.

选择文件类型/文献管理软件名称

选择包含的内容