Distributed Heterogeneous Hybrid Flow-shop Scheduling Considering Combined Buffer

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

Abstract

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

CLC Number:

TP49

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.

Figures/Tables 24

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Table 1

Table 2

Fig. 13

Table 3

Table 4

Table 5

Fig. 14

Table 6

Table 7

Table 8

Table 9

Test results for medium-scale instances

算例	χ				η/%			ϖ/%
算例	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

Table 9

Table 10

Test results for large-scale instances

算例	χ				η/%			ϖ/%
算例	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

Table 10

References 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