Distributed Assembly Hybrid Flow Shop Scheduling with Dual Resource Constraints

doi:10.3969/j.issn.1004-132X.2026.07.022

Abstract

Abstract:

This paper proposes a knowledge-driven iterative greedy （KDIG） algorithm for the distributed assembly hybrid flow shop scheduling problem with dual resource constraints. The algorithm adopts a knowledge-based NEH （Nawaz-Enscore-Ham） initialization strategy to generate the initial solution. Based on the problem characteristics， four local search operators are designed. Combined with a Q-learning mechanism， these operators enable individuals to dynamically select the optimal local search operator during iterative updates， thereby significantly improving search efficiency. Experimental results on 81 large-scale instances， comparing the KDIG algorithm with five other mainstream algorithms， demonstrate that the proposed KDIG algorithm outperforms all benchmark algorithms.

Key words: distributed assembly hybrid flow shop scheduling, knowledge-driven, iterative greedy algorithm, Q-learning

摘要：

针对具有双资源约束的分布式装配混合流水车间调度问题，提出一种基于知识驱动的迭代贪婪（KDIG）算法。采用基于知识的NEH（Nawaz-Enscore-Ham）初始化策略，生成初始解决方案。基于问题特征设计了4种局部搜索算子。局部搜索算子与Q学习机制的结合使个体在迭代更新时动态选择最优的局部搜索算子，从而显著提升个体在搜索过程中的效率。KDIG算法与5种主流算法在81个大型实例上的测试结果表明，KDIG算法优于其他对比算法。

关键词: 分布式装配混合流车间调度, 知识驱动, 迭代贪婪算法, Q学习

CLC Number:

TP182

ZHAO Cai, WU Lianghong. Distributed Assembly Hybrid Flow Shop Scheduling with Dual Resource Constraints[J]. China Mechanical Engineering, 2026, 37(7): 1725-1733.

赵才, 吴亮红. 具有双资源约束的分布式装配混合流水车间调度[J]. 中国机械工程, 2026, 37(7): 1725-1733.

Figures/Tables 14

References 28

[1]	SHAO Zhongshi， SHAO Weishi， PI Dechang. 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， 2023， 7（1）： 111-127.
[2]	ZHANG Wenqiang， LI Chen， GEN M， et al. A Multiobjective Memetic Algorithm with Particle Swarm Optimization and Q-learning-based Local Search for Energy-efficient Distributed Heterogeneous Hybrid Flow-shop Scheduling Problem［J］. Expert Systems with Applications， 2024， 237： 121570.
[3]	DI Yuanzhu， DENG Libao， ZHANG Lili.A Collaborative-learning Multi-agent Reinforcement Learning Method for Distributed Hybrid Flow Shop Scheduling Problem［J］. Swarm and Evolutionary Computation， 2024， 91： 101764.
[4]	LIU Feige， LI Guiling， LU Chao， et al. A Tri-individual Iterated Greedy Algorithm for the Distributed Hybrid Flow Shop with Blocking［J］. Expert Systems with Applications， 2024， 237： 121667.
[5]	CUI Hanghao， LI Xinyu， GAO Liang， et al. Multi-population Genetic Algorithm with Greedy Job Insertion Inter-factory Neighbourhoods for Multi-objective Distributed Hybrid Flow-shop Scheduling with Unrelated-parallel Machines Considering Tardiness［J］. International Journal of Production Research， 2024， 62（12）： 4427-4445.
[6]	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.
[7]	魏光艳，叶春明. 分布式多柔性装配作业车间调度问题研究［J］. 中国机械工程， 2023， 34（20）： 2442-2455.
	WEI Guangyan， YE Chunming. Research on Distributed and Multi-flexible Assembly Job-shop Scheduling Problems［J］. China Mechanical Engineering， 2023， 34（20）： 2442-2455.
[8]	曹阳华，孔繁森. 基于装配线平衡的U形装配线生产效率研究［J］. 中国机械工程， 2015， 26（14）： 1908-1915.
	CAO Yanghua， KONG Fansen. Study on Production Efficiency of U-shaped Assembly Line Based on Assembly Line Balancing［J］. China Mechanical Engineering， 2015， 26（14）： 1908-1915.
[9]	魏书鹏，唐红涛，李西兴，等. 考虑双资源约束的柔性机械加工车间逆调度问题研究［J］. 中国机械工程， 2024， 35（3）： 457-471.
	WEI Shupeng， TANG Hongtao， LI Xixing， et al. Dual-resource Constrained Flexible Machining Workshop Inverse Scheduling Problem［J］. China Mechanical Engineering， 2024， 35（3）： 457-471.
[10]	梁向檩，宋豫川，雷琦，等. 考虑工人数量配置优化的柔性作业车间调度问题研究［J］. 中国机械工程， 2023， 34（17）： 2065-2076.
	LIANG Xianglin， SONG Yuchuan， LEI Qi， et al. Research on Flexible Job-shop Scheduling Problems Considering Optimization of Worker Number Allocation［J］. China Mechanical Engineering， 2023， 34（17）： 2065-2076.
[11]	张维存，顾洪羽. 一人多机模式下考虑相似学习效应的车间调度问题［J］. 中国机械工程， 2023， 34（14）： 1701-1709.
	ZHANG Weicun， GU Hongyu. Job-shop Scheduling Problems Considering Similar Learning Effect in One-worker and Multiple-machine Partterns［J］. China Mechanical Engineering， 2023， 34（14）： 1701-1709.
[12]	RUIZ R， STÜTZLE T. A Simple and Effective Iterated Greedy Algorithm for the Permutation Flowshop Scheduling Problem［J］. European Journal of Operational Research， 2007， 177（3）： 2033-2049.
[13]	JING Xuelei， PAN Quanke， GAO Liang， et al. An Effective Iterated Greedy Algorithm for a Robust Distributed Permutation Flowshop Problem with Carryover Sequence-dependent Setup Time［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2022， 52（9）： 5783-5794.
[14]	ZOU Wenqiang， PAN Quanke， MENG Leilei， et al. An Effective Self-adaptive Iterated Greedy Algorithm for a Multi-AGVs Scheduling Problem with Charging and Maintenance［J］. Expert Systems with Applications， 2023， 216： 119512.
[15]	QIN Haoxiang， HAN Yuyan， ZHANG Biao， et al. An Improved Iterated Greedy Algorithm for the Energy-efficient Blocking Hybrid Flow Shop Scheduling Problem［J］. Swarm and Evolutionary Computation， 2022， 69： 100992.
[16]	ZHAO Fuqing， XU Zesong， WANG Ling， et al. A Population-based Iterated Greedy Algorithm for Distributed Assembly No-wait Flow-shop Scheduling Problem［J］. IEEE Transactions on Industrial Informatics， 2023， 19（5）： 6692-6705.
[17]	KARIMI-MAMAGHAN M， MOHAMMADI M， PASDE LOUP B， et al. Learning to Select Operators in Meta-heuristics： an Integration of Q-learning into the Iterated Greedy Algorithm for the Permutation Flowshop Scheduling Problem［J］. European Journal of Operational Research， 2023， 304（3）： 1296-1330.
[18]	YU Fei， LU Chao， ZHOU Jiajun， et al. Mathematical Model and Knowledge-based Iterated Greedy Algorithm for Distributed Assembly Hybrid Flow Shop Scheduling Problem with Dual-resource Constraints［J］. Expert Systems with Applications， 2024， 239： 122434.
[19]	YANG Yahong， LI Xun. A Knowledge-driven Constructive Heuristic Algorithm for the Distributed Assembly Blocking Flow Shop Scheduling Problem［J］. Expert Systems with Applications， 2022， 202： 117269.
[20]	RUIZ R， MAROTO C. A Genetic Algorithm for Hybrid Flowshops with Sequence Dependent Setup Times and Machine Eligibility［J］. European Journal of Operational Research， 2006， 169（3）： 781-800.
[21]	NAWAZ M， ENSCORE E E， HAM I. A Heuristic Algorithm for the M-machine， N-job Flow-shop Sequencing Problem［J］. Omega， 1983， 11（1）： 91-95.
[22]	ZHAO Fuqing， HU Xiaotong， WANG Ling， et al. A Reinforcement Learning Brain Storm Optimization Algorithm with Learning Mechanism［J］.Knowledge Based Systems，2022，235：107645.
[23]	KOU Lei， WANG Yukuan， ZHANG Fangfang， et al. A Chaotic Simulated Annealing Genetic Algorithm with Asymmetric Time for Offshore Wind Farm Inspection Path Planning［J］. International Journal of Bio-Inspired Computation， 2025， 25（2）： 69-78.
[24]	SMITH J R， LARSON C. Statistical Approaches in Surface Finishing. Part 3. Design-of-experiments［J］. Transactions of the IMF， 2019， 97（6）： 289-294.
[25]	SANG Hongyan， PAN Quanke， LI Junqing， 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.
[26]	SHAO Weishi， PI Dechang， SHAO Zhongshi. Optimization of Makespan for the Distributed No-wait Flow Shop Scheduling Problem with Iterated Greedy Algorithms［J］. Knowledge-Based Systems， 2017， 137： 163-181.
[27]	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.
[28]	ZHAO Fuqing， SHAO Dongqu， WANG Ling， et al. An Effective Water Wave Optimization Algorithm with Problem-specific Knowledge for the Distributed Assembly Blocking Flow-shop Scheduling Problem［J］. Knowledge-Based Systems， 2022， 243： 108471.

量符号	说明
i，i′	工件索引，i，i′=1，2，…，N
j	阶段的索引，j=1，2，…，N_S
k	机器的索引，k=1，2，…，N_M
w	工人索引，w=1，2，…，N_W
f	工厂索引，f=1，2，…，N_F
p，p′	产品索引，p，p′=1，2，…，N_P
I	工件集合
I_p	产品p的工件集合
S	阶段集合
P	产品集合
F	工厂集合
K_f	工厂f中机器的集合
K_i_，_j_，_f	工厂f中工件O_i_，_j 的加工机器集合
W_f	工厂f中工人的集合
W_i_，_j_，_f	工厂f中工件O_i_，_j 的加工工人集合
J_i	第i个工件
O_i_，_j	第j阶段的工件i
F_f	第f个工厂
M_j_，_k	第j阶段的第k台机器
W_j_，_w	第j阶段的第w个工人
C_i_，_j	O_i_，_j 的完工时间
N_F	工厂总数
N_P	产品总数
N_M	工厂中的机器总数
N_M，_j	第j阶段的机器总数
N_W	工人总数
N_W，_j	第j阶段的工人总数
T_p	产品p的延迟时间
T_i_，_j_，_f_，_k_，_w	工件的实际加工时间
T_p	产品p的装配时间
D_p	产品p的离开时间
G_i_，_p	工件i属于产品p
C_p	产品p的完工时间
S_p	产品p的开始时间
L	无穷大的正数
S_i_，_j	O_i_，_j 的开始时间
T_TD	总延迟
V_i_，_j_，_f_，_k_，_w_，_s	若工件由工人w处理，则为1，否则为0
X_i_，_i′_，_j_，_f_，_k	若机器在工件i后加工i′，则为1，否则为0
Y_i_，_i′_，_j_，_f_，_k	若工人在工件i后加工i′，则为1，否则为0
Z_i_，_f	若工件i在工厂f中加工，则为1，否则为0
H_p_，_p′	产品p后紧跟p′产品，则为1，否则为0

量符号	说明
i，i′	工件索引，i，i′=1，2，…，N
j	阶段的索引，j=1，2，…，N_S
k	机器的索引，k=1，2，…，N_M
w	工人索引，w=1，2，…，N_W
f	工厂索引，f=1，2，…，N_F
p，p′	产品索引，p，p′=1，2，…，N_P
I	工件集合
I_p	产品p的工件集合
S	阶段集合
P	产品集合
F	工厂集合
K_f	工厂f中机器的集合
K_i_，_j_，_f	工厂f中工件O_i_，_j 的加工机器集合
W_f	工厂f中工人的集合
W_i_，_j_，_f	工厂f中工件O_i_，_j 的加工工人集合
J_i	第i个工件
O_i_，_j	第j阶段的工件i
F_f	第f个工厂
M_j_，_k	第j阶段的第k台机器
W_j_，_w	第j阶段的第w个工人
C_i_，_j	O_i_，_j 的完工时间
N_F	工厂总数
N_P	产品总数
N_M	工厂中的机器总数
N_M，_j	第j阶段的机器总数
N_W	工人总数
N_W，_j	第j阶段的工人总数
T_p	产品p的延迟时间
T_i_，_j_，_f_，_k_，_w	工件的实际加工时间
T_p	产品p的装配时间
D_p	产品p的离开时间
G_i_，_p	工件i属于产品p
C_p	产品p的完工时间
S_p	产品p的开始时间
L	无穷大的正数
S_i_，_j	O_i_，_j 的开始时间
T_TD	总延迟
V_i_，_j_，_f_，_k_，_w_，_s	若工件由工人w处理，则为1，否则为0
X_i_，_i′_，_j_，_f_，_k	若机器在工件i后加工i′，则为1，否则为0
Y_i_，_i′_，_j_，_f_，_k	若工人在工件i后加工i′，则为1，否则为0
Z_i_，_f	若工件i在工厂f中加工，则为1，否则为0
H_p_，_p′	产品p后紧跟p′产品，则为1，否则为0

来源	平方和	自由度	均方	F-ratio	p-value
β	456.8	3	86.582	891.76	0.0000
Γ	352.3	3	69.485	423.26	0.0000
T₀	6.9	3	3.852	65.42	0.0000
a	3.2	2	1.262	9.59	0.0000
b	2.5	2	1.258	7.66	0.0000
β×Γ	39.8	9	3.256	1.78	0.6629
β×T₀	0.6	9	0.266	1.56	0.8413
Γ×a	2.5	6	0.521	1.44	0.5130
Γ×b	6.4	6	0.636	4.56	0.4790
Γ×T₀	3.5	9	0.466	3.85	0.5364
β×a	1.1	6	0.226	2.65	0.6449
β×b	0.9	6	0.255	1.25	0.7418
T₀×a	0.3	6	0.236	0.45	0.8234
T₀×b	0.2	6	0.126	1.34	0.6950
a×b	0.1	4	0.236	0.45	0.8074
残差	6964.0	76728
总计	7603.2	76800

来源	平方和	自由度	均方	F-ratio	p-value
β	456.8	3	86.582	891.76	0.0000
Γ	352.3	3	69.485	423.26	0.0000
T₀	6.9	3	3.852	65.42	0.0000
a	3.2	2	1.262	9.59	0.0000
b	2.5	2	1.258	7.66	0.0000
β×Γ	39.8	9	3.256	1.78	0.6629
β×T₀	0.6	9	0.266	1.56	0.8413
Γ×a	2.5	6	0.521	1.44	0.5130
Γ×b	6.4	6	0.636	4.56	0.4790
Γ×T₀	3.5	9	0.466	3.85	0.5364
β×a	1.1	6	0.226	2.65	0.6449
β×b	0.9	6	0.255	1.25	0.7418
T₀×a	0.3	6	0.236	0.45	0.8234
T₀×b	0.2	6	0.126	1.34	0.6950
a×b	0.1	4	0.236	0.45	0.8074
残差	6964.0	76728
总计	7603.2	76800

参数	规模	KDIG	KDIG1	KDIG2	KDIG3
N_F	2	1.15	17.52	7.63	23.64
	4	2.39	10.96	5.95	18.89
	6	4.05	9.85	4.25	15.89
N	20	3.54	4.05	3.08	14.68
	40	0.96	11.48	3.09	20.65
	60	0.25	22.85	5.67	21.66
N_S	2	2.90	12.58	8.94	20.69
	4	2.39	13.57	6.84	16.36
	6	2.39	11.78	6.04	14.65
N_P	2	2.85	11.74	5.09	19.67
	4	1.68	13.85	6.98	18.65
	6	3.18	12.45	6.28	18.55