考虑组合缓冲的分布式异构混合流水车间调度

doi:10.16182/j.issn1004731x.joss.24-0510

摘要/Abstract

摘要：

为了减少交货延迟造成的成本损耗，以总加权提前/延迟为优化目标，针对有限缓冲和零等待的组合缓冲条件下分布式异构混合流水车间调度问题，提出了一种基于Q学习的混合分布估计算法。对于有限缓冲和零等待的组合缓冲，设计了基于平均工厂分配策略和最短路径法的动态解码；结合反向学习优化初始工件群，将Q学习嵌入概率模型中，依据群体状态对工件群进行智能搜索和更新；利用切比雪夫混沌映射对工件群重构，以提升工件群质量。仿真结果表明：该算法在考虑运输时间的组合缓冲条件下，求解分布式异构混合流水车间调度具有较好性能。

关键词: 分布式异构混合流水车间, 有限缓冲和零等待, 总加权提前/延迟, 混合分布估计算法, Q学习

Abstract:

In order to reduce cost losses caused by delivery delays, distributed heterogeneous hybrid flow-shop scheduling problems under combined buffer conditions of finite buffer and zero-wait were studied. A hybrid estimation of distribution algorithm based on Q-learning was proposed to minimize total weighted earliness and tardiness. For the combined buffer, dynamic decoding was designed based on the average factory allocation strategy and the shortest path method. The initial job group was optimized by reverse learning. Q-learning was embedded in the probabilistic model for intelligent searching and updating based on the group state. Reconstruction of the job group was completed using Chebyshev chaotic mapping to improve the group quality. Simulation results show that the proposed algorithm performs well in solving distributed heterogeneous hybrid flow-shop scheduling problems under combined buffer conditions, with transportation time taken into account.

Key words: distributed heterogeneous hybrid flow-shop scheduling, finite buffer and zero-wait, total weighted earliness and tardiness, hybrid estimation of distribution algorithm, Q-learning

中图分类号:

TP49

轩华,吕琳,李冰 . 考虑组合缓冲的分布式异构混合流水车间调度[J]. 系统仿真学报, 2025, 37(10): 2672-2686.

Xuan Hua,Lü Lin,Li Bing . Distributed Heterogeneous Hybrid Flow-shop Scheduling Considering Combined Buffer[J]. Journal of System Simulation, 2025, 37(10): 2672-2686.

图/表 24

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

表1

表2

图13

表3

表4

表5

图14

表6

表7

表8

表9

中规模算例的测试结果

算例	χ				η/%			ϖ/%
算例	EDA	HEDAQ	DABC	HDDE	EDA	DABC	HDDE	EDA	HEDAQ	DABC	HDDE
平均	6 605.42	5 722.19	6 222.91	6 141.97	17.32	9.30	7.77	2.30	0.60	1.49	1.35
2	8 492.13	7 817.07	8 227.60	8 020.40	8.64	5.25	2.60	1.81	0.87	1.44	1.16
3	7 717.40	6 947.00	7 542.33	7 263.80	11.09	8.57	4.56	1.38	0.60	1.21	1.08
4	13 150.73	12 050.93	12 200.80	12 393.07	9.13	1.24	2.84	1.60	0.63	0.77	0.94
5	17 848.80	16 489.00	17 401.80	16 934.80	8.25	5.54	2.70	1.57	0.68	1.28	0.97
10	3 681.00	3 420.90	3 582.40	3 597.70	7.60	4.72	5.17	1.16	0.37	0.86	0.91
11	6 960.00	5 960.50	6 735.00	6 260.00	16.77	12.99	5.02	1.91	0.20	1.52	0.71
12	10 976.00	9 294.30	10 602.60	9 603.50	18.09	14.08	3.33	1.97	0.14	1.57	0.48
13	11 685.00	8 826.60	10 001.00	9 843.00	32.38	13.31	11.52	3.43	0.15	1.50	1.32
18	1 905.20	1 423.60	1 794.60	1 639.40	33.83	26.06	15.16	4.41	0.77	3.57	2.40
19	1 189.20	1 094.40	1 061.20	1 080.60	8.66	-3.03	-1.26	1.51	0.32	0.27	0.46
20	1 303.40	1 131.80	1 145.40	1 154.40	15.16	1.20	2.00	2.02	1.31	1.44	1.53
21	1 524.00	1 179.40	1 325.80	1 401.40	29.22	12.41	18.82	2.14	0.09	1.34	1.99
26	3 798.27	2 748.00	3 411.33	3 321.40	38.22	24.14	20.87	3.93	0.80	2.99	2.86
27	6 308.56	5 856.18	5 979.11	5 950.49	7.72	2.10	1.61	1.07	0.28	0.49	0.44
28	12 373.33	9 232.02	11 806.00	12 183.00	34.03	27.88	31.96	3.71	0.53	2.09	2.50
29	12 969.33	12 176.67	12 305.07	12 706.87	6.51	1.05	4.35	0.68	0.03	0.13	0.46
34	4 346.00	4 048.60	4 173.60	4 209.60	7.35	3.09	3.98	1.15	0.38	0.70	0.80
35	5 546.93	5 200.67	5 288.53	5 163.33	6.66	1.69	-0.72	0.95	0.23	0.44	0.19
36	10 383.33	7 602.13	9 942.00	9 985.00	36.58	30.78	31.34	3.36	0.81	2.75	2.80
37	9 996.00	9 224.00	9 473.60	9 514.60	8.37	2.71	3.15	1.15	0.29	0.57	0.61
42	2 659.00	2 181.40	2 426.20	2 337.00	21.89	11.22	7.13	3.76	1.29	2.55	2.09
43	2 353.33	1 893.13	2 185.13	2 094.13	24.31	15.42	10.62	4.39	1.58	3.36	2.81
44	2 290.00	1 995.73	2 110.00	2 160.00	14.74	5.73	8.23	3.56	1.82	2.49	2.79
45	2 319.20	1 848.00	2 092.80	2 052.00	25.50	13.25	11.04	3.38	0.66	2.08	1.84
49	6 163.67	5 243.13	6 018.87	5 509.40	17.56	14.80	5.08	2.09	0.28	1.80	0.80
50	8 889.67	7 447.87	8 016.93	7 971.27	19.36	7.64	7.03	2.30	0.30	1.09	1.03
51	9 637.60	8 850.60	9 153.60	9 235.60	8.89	3.42	4.35	1.43	0.50	0.85	0.95
55	5 448.00	4 699.40	5 065.60	4 974.40	15.93	7.79	5.85	2.61	0.87	1.72	1.51
56	6 375.00	5 523.00	6 013.00	5 950.00	15.43	8.87	7.73	1.98	0.38	1.30	1.18
57	9 407.00	8 661.60	9 032.20	8 987.00	8.61	4.28	3.76	1.14	0.26	0.70	0.64
61	3 609.80	3 388.80	3 500.00	3 441.80	6.52	3.28	1.56	1.56	0.85	1.21	1.02
62	2 701.00	2 166.00	2 436.00	2 394.00	24.70	12.47	10.53	3.97	1.21	2.60	2.38
63	3 971.00	3 210.00	3 306.00	3 352.00	23.71	2.99	4.42	2.71	0.28	0.58	0.73

表9

表10

大规模算例的测试结果

算例	χ				η/%			ϖ/%
算例	EDA	HEDAQ	DABC	HDDE	EDA	DABC	HDDE	EDA	HEDAQ	DABC	HDDE
平均	21 577.08	18 909.83	20 410.40	19 872.90	39.40	17.26	16.37	2.73	0.53	1.65	1.41
6	35 180.00	30 359.93	32 271.00	31 428.53	15.88	6.29	3.52	2.26	0.58	1.24	0.95
7	39 124.00	37 585.80	38 311.93	38 539.27	4.09	1.93	2.54	0.97	0.54	0.74	0.81
8	77 634.00	72 993.00	74 894.60	74 382.00	6.36	2.61	1.90	1.20	0.53	0.80	0.73
14	27 456.00	23 079.60	24 339.40	26 984.80	18.96	5.46	16.92	3.22	1.11	1.72	2.99
15	23 410.00	19 711.00	21 378.00	20 142.40	18.77	8.46	2.19	3.04	0.98	1.91	1.22
16	41 545.80	34 796.80	39 790.00	37 069.00	19.40	14.35	6.53	1.80	0.72	2.26	1.42
22	379.00	217.20	329.00	318.00	74.49	51.47	46.41	5.14	1.97	4.62	4.06
23	257.00	59.20	76.80	154.20	334.12	29.73	160.47	4.56	1.03	3.02	2.14
24	36.00	13.80	30.40	16.20	160.87	120.29	17.39	6.69	0.62	1.38	2.46
30	25 038.44	21 330.09	24 353.62	24 451.47	17.39	14.17	14.63	1.92	0.16	1.60	1.64
31	34 014.89	31 920.13	32 458.76	32 640.36	6.56	1.69	2.26	0.97	0.30	0.47	0.53
32	46 510.00	42 553.20	45 786.07	44 807.73	9.30	7.60	5.30	1.19	0.24	1.02	0.78
38	12 013.67	11 149.07	11 521.47	11 435.40	7.75	3.34	2.57	0.92	0.14	0.47	0.40
39	22 033.67	18 724.47	20 896.33	19 893.93	17.67	11.60	6.25	2.31	0.46	1.67	1.11
40	29 139.00	26 508.80	28 687.20	27 056.00	9.92	8.22	2.06	1.43	0.40	1.25	0.61
46	2 352.33	1 994.00	2 083.33	2 143.20	17.97	4.48	7.48	2.45	0.56	1.03	1.35
47	1 577.40	1 035.60	1 267.27	1 490.47	52.32	22.37	43.92	4.01	0.51	2.87	3.13
48	541.00	352.40	528.40	481.80	53.52	49.94	36.72	3.96	0.40	2.59	2.21
52	23 941.67	18 874.93	20 580.67	19 281.00	26.84	9.04	2.15	2.76	0.06	0.97	0.27
53	29 959.33	24 618.80	29 489.13	25 021.20	21.69	19.78	1.63	2.33	0.13	2.14	0.30
54	40 178.00	33 651.20	38 393.40	35 612.40	19.40	14.09	5.83	2.05	0.10	0.82	0.68
58	15 592.00	10 244.00	13 775.00	12 745.00	52.21	34.47	24.41	5.59	0.24	3.78	2.75
59	17 325.00	16 491.50	16 536.00	16 801.00	5.05	0.27	1.88	0.84	0.31	0.34	0.51
60	28 888.00	25 554.00	27 045.00	26 421.00	13.05	5.83	3.39	1.76	0.41	1.01	0.76
64	2 971.00	2 673.00	2 837.00	2 762.00	11.15	6.14	3.33	1.50	0.35	0.98	0.69
65	2 892.00	2 193.00	2 297.00	2 338.00	31.87	4.74	6.61	4.46	0.97	1.49	1.69
66	2 592.00	1 891.00	2 224.00	2 152.00	37.07	17.61	13.80	4.41	0.51	2.36	1.96

表10

参考文献 25

[1]	袁帅鹏, 李铁克, 王柏琳. 带运输时间混合流水车间成组调度的协同进化文化基因算法[J]. 控制理论与应用, 2023, 40(3): 430-440.
	Yuan Shuaipeng, Li Tieke, Wang Bailin. Co-evolutionary Memetic Algorithm for the Hybrid Flow Shop Group Scheduling with Transportation Times[J]. Control Theory & Applications, 2023, 40(3): 430-440.
[2]	Meng Leilei, Gao Kaizhou, Ren Yaping, et al. Novel MILP and CP Models for Distributed Hybrid Flowshop Scheduling Problem with Sequence-dependent Setup Times[J]. Swarm and Evolutionary Computation, 2022, 71: 101058.
[3]	Qin Haoxiang, Han Yuyan, Liu Yiping, 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.
[4]	Shao Weishi, Shao Zhongshi, Pi Dechang. Modelling and Optimization of Distributed Heterogeneous Hybrid Flow Shop Lot-streaming Scheduling Problem[J]. Expert Systems with Applications, 2023, 214: 119151.
[5]	郦仕云, 杨孟平, 易文超, 等. 基于混合离散差分进化算法的分布式异构混合流水车间调度[J/OL]. 计算机集成制造系统. (2023-05-16) [2023-12-20]. .
	Li Shiyun, Yang Mengping, Yi Wenchao, et al. Hybrid Discrete Differential Evolution Algorithm for Distributed Heterogeneous Hybrid Flowshop Scheduling Problem[J/OL]. Computer Integrated Manufacturing Systems. (2023-05-16) [2023-12-20]. .
[6]	Missaoui Ahmed, Ruiz Rubén. A Parameter-less Iterated Greedy Method for the Hybrid Flowshop Scheduling Problem with Setup Times and Due Date Windows[J]. European Journal of Operational Research, 2022, 303(1): 99-113.
[7]	Oğuzhan Ahmet Arık, Schutten Marco, Topan Engin. Weighted Earliness/Tardiness Parallel Machine Scheduling Problem with a Common Due Date[J]. Expert Systems with Applications, 2022, 187: 115916.
[8]	Missaoui Ahmed, Boujelbene Younès. An Effective Iterated Greedy Algorithm for Blocking Hybrid Flow Shop Problem with Due Date Window[J]. RAIRO- Operations Research, 2021, 55(3): 1603-1616.
[9]	雷德明, 苏斌. 基于多班教学优化的多目标分布式混合流水车间调度[J]. 控制与决策, 2021, 36(2): 303-313.
	Lei Deming, Su Bin. Multi-class Teaching-learning-based Optimization for Multi-objective Distributed Hybrid Flow Shop Scheduling[J]. Control and Decision, 2021, 36(2): 303-313.
[10]	Shao Weishi, Pi Dechang, Shao Zhongshi. A Pareto-based Estimation of Distribution Algorithm for Solving Multiobjective 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.
[11]	Li Haoran, Li Xinyu, Gao Liang. A Discrete Artificial Bee Colony Algorithm for the Distributed Heterogeneous No-wait Flowshop Scheduling Problem[J]. Applied Soft Computing, 2021, 100: 106946.
[12]	Zhu Ningning, Zhao Fuqing, Wang Ling, 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.
[13]	Zhao Fuqing, Zhao Jinlong, Wang Ling, 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]	袁庆欣, 董绍华. 带有限缓冲区的混合流水车间多目标调度[J]. 工程科学学报, 2021, 43(11): 1491-1498.
	Yuan Qingxin, Dong Shaohua. Optimizing Multi-objective Scheduling Problem of Hybrid Flow Shop with Limited Buffer[J]. Chinese Journal of Engineering, 2021, 43(11): 1491-1498.
[15]	轩华, 郑倩倩, 李冰. 带不相关并行机和有限缓冲MHFS调度的混合启发式算法[J]. 控制与决策, 2021, 36(3): 565-576.
	Xuan Hua, Zheng Qianqian, Li Bing. Hybrid Heuristic Algorithm for Multi-stage Hybrid Flow Shop Scheduling with Unrelated Parallel Machines and Finite Buffers[J]. Control and Decision, 2021, 36(3): 565-576.
[16]	Zhang Chunjiang, Tan Jiawei, Peng Kunkun, et al. A Discrete Whale Swarm Algorithm for Hybrid Flow-shop Scheduling Problem with Limited Buffers[J]. Robotics and Computer-Integrated Manufacturing, 2021, 68: 102081.
[17]	Zhang Guanghui, Xing Keyi. Differential Evolution Metaheuristics for Distributed Limited-buffer Flowshop Scheduling with Makespan Criterion[J]. Computers & Operations Research, 2019, 108: 33-43.
[18]	张其亮, 陈永生. 求解具有混合约束流水车间调度问题的迭代贪婪算法[J]. 计算机应用研究, 2016, 33(2): 352-355.
	Zhang Qiliang, Chen Yongsheng. Iterated Greedy Algorithm for Mixed Constraints Flow Shop Scheduling Problem[J]. Application Research of Computers, 2016, 33(2): 352-355.
[19]	孙厚权, 张其亮. 人工蜂群算法求解混合约束流水车间调度问题[J]. 计算机技术与发展, 2019, 29(3): 144-148, 153.
	Sun Houquan, Zhang Qiliang. Artificial Bee Colony Algorithm for Flow Shop Scheduling Problem with Mixed Buffering Requirements[J]. Computer Technology and Development, 2019, 29(3): 144-148, 153.
[20]	张其亮, 陈永生. 解决具有混合约束柔性流水车间调度问题的粒子群优化算法[J]. 计算机应用研究, 2013, 30(11): 3253-3256, 3260.
	Zhang Qiliang, Chen Yongsheng. Particle Swarm Optimization Algorithm for Flexible Flow Shop Scheduling Problem with Mixed Constraints[J]. Application Research of Computers, 2013, 30(11): 3253-3256, 3260.
[21]	轩华, 付鑫博, 李冰. 基于混合离散人工蜂群算法的混合零等待柔性流水车间优化研究[J]. 工业工程与管理, 2023, 28(1): 170-180.
	Xuan Hua, Fu Xinbo, Li Bing. Research on Optimization of Mixed Zero-wait Flexible Flowshop Based on Hybrid Discrete Artificial Bee Colony Algorithm[J]. Industrial Engineering and Management, 2023, 28(1): 170-180.
[22]	Zhuang Zilong, Zhang Zhanluo, Teng Hao, et al. Optimization for Integrated Scheduling of Intelligent Handling Equipment with Bidirectional Flows and Limited Buffers at Automated Container Terminals[J]. Computers & Operations Research, 2022, 145: 105863.
[23]	Xi Bingjie, Lei Deming. Q-learning-based Teaching-learning Optimization for Distributed Two-stage Hybrid Flow Shop Scheduling with Fuzzy Processing Time[J]. Complex System Modeling and Simulation, 2022, 2(2): 113-129.
[24]	Li Yingli, Li Xinyu, Gao Liang, et al. A Discrete Artificial Bee Colony Algorithm for Distributed Hybrid Flowshop Scheduling Problem with Sequence-dependent Setup Times[J]. International Journal of Production Research, 2021, 59(13): 3880-3899.
[25]	孟磊磊, 张超勇, 任彩乐, 等. 求解带有阻塞限制的HFSP的MILP模型与改进回溯搜索算法[J]. 中国机械工程, 2018, 29(22): 2647-2658.
	Meng Leilei, Zhang Chaoyong, Ren Caile, et al. MILP Models and an Improved BSA for Hybrid Flow Shop Scheduling Problems with Blocking[J]. China Mechanical Engineering, 2018, 29(22): 2647-2658.

算例	J
1, 9, 17, 25, 33, 41	20
2, 10, 18, 26, 34, 42	30
3, 11, 19, 27, 35, 43, 49, 55, 61	40
4, 12, 20, 28, 36, 44, 50, 56, 62	50
5, 13, 21, 29, 37, 45, 51, 57, 63	60
6, 14, 22, 30, 38, 46, 52, 58, 64	80
7, 15, 23, 31, 39, 47, 53, 59, 65	100
8, 16, 24, 32, 40, 48, 54, 60, 66	120
算例	F
1~24	2
25~48	3
49~66	4
算例	N	M_n_,_f
1~8，25~32，49~54	2	3
9~16，33~41，55~60	4	4
17~24，42~48，61~66	8	4

实验	因子等级						平均目标值
实验	W	Ʋ_max	λ	γ	ε	θ	平均目标值
1	1	1	1	1	1	1	2 188.9
2	1	2	2	2	2	2	3 048.5
3	1	3	3	3	3	3	3 532.6
4	1	4	4	4	4	4	3 573.7
5	1	5	5	5	5	5	3 307.9
6	2	1	2	3	4	5	3 680.5
7	2	2	3	4	5	1	4 195.0
8	2	3	4	5	1	2	3 268.9
9	2	4	5	1	2	3	3 972.7
10	2	5	1	2	3	4	4 053.2
11	3	1	3	5	2	4	4 064.8
12	3	2	4	1	3	5	2 790.6
13	3	3	5	2	4	1	3 755.4
14	3	4	1	3	5	2	2 602.8
15	3	5	2	4	1	3	3 412.0
16	4	1	4	2	5	3	2 173.0
17	4	2	5	3	1	4	3 251.0
18	4	3	1	4	2	5	2 721.0
19	4	4	2	5	3	1	4 267.0
20	4	5	3	1	4	2	3 508.0
21	5	1	5	4	3	2	3 744.1
22	5	2	4	5	4	3	2 869.8
23	5	3	3	1	5	4	2 724.5
24	5	4	2	2	1	5	3 184.9
25	5	5	1	3	2	1	3 846.0

算例	HEDAQ
算例	B_n =0	B_n =1	B_n =2	B_n =3	B_n =4
9	3 029.8	2 889.8	2 804.2	2 780.0	2 681.0
10	4 900.6	4 662.8	4 518.0	4 242.6	4 114.0
11	6 487.2	5 615.2	5 325.2	5 246.4	5 157.4
12	12 073.0	9 262.0	9 065.0	8 998.8	8 563.6
13	14 910.0	11 069.0	10 854.0	10 713.0	9 978.0
14	24 514.0	16 543.0	16 432.0	16 017.0	15 924.0

算例	HEDA	HEDAQ	η/%
平均	13 691.9	13 153.5	3.80
9	2 559.5	2 448.2	4.55
10	3 462.8	3 310.9	4.59
11	5 397.8	5 260.5	2.61
12	9 332.4	9 094.3	2.62
13	8 898.0	8 626.6	3.15
14	23 517.6	22 979.6	2.34
15	20 686.0	19 711.0	4.95
16	35 681.4	33 796.8	5.58

算例	χ				η/%			ϖ/%
算例	EDA	HEDAQ	DABC	HDDE	EDA	DABC	HDDE	EDA	HEDAQ	DABC	HDDE
平均	2 573.27	2 238.68	2 423.28	2 391.24	15.08	8.54	6.90	2.99	1.61	2.16	2.16
1	2 887.80	2 542.40	2 751.33	2 697.93	13.59	8.22	6.12	3.75	2.52	2.89	2.80
9	3 007.60	2 558.20	2 753.60	2 601.90	17.57	7.64	1.71	3.23	1.25	2.11	1.44
17	1 692.80	1 428.00	1 609.40	1 512.60	18.54	12.70	5.92	3.28	2.28	2.30	2.47
25	2 423.33	2 112.47	2 328.42	2 389.69	14.72	10.22	13.12	2.10	0.95	1.63	1.94
33	2 449.73	2 288.13	2 353.87	2 383.33	7.06	2.87	4.16	2.25	1.44	1.77	1.92
41	2 978.33	2 502.87	2 743.07	2 762.00	19.00	9.60	10.35	3.34	1.21	2.28	2.37