Integrated Scheduling for Flexible Job Shops with Heterogeneous Transport Resources

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

Abstract

Abstract:

This paper addresses the integrated scheduling problem of heterogeneous transportation resources—comprising an overhead crane and automated guided vehicles—in flexible job shops. A reinforcement learning-based multi-objective evolutionary algorithm is proposed to minimize both makespan and total energy consumption. Three hybrid initialization strategies are designed to enhance population quality and diversity. Subsequently， a reinforcement learning mechanism is introduced for adaptive control of genetic operator parameters， and a critical-path-based hybrid neighborhood structure is constructed to simultaneously optimize makespan and energy consumption， thereby guiding efficient exploration of high-quality solutions. Finally， ablation and comparative experiments validate the effectiveness and stability of the proposed algorithm in solving the heterogeneous-transportation-resource flexible job shop scheduling problem.

Key words: flexible job shop, heterogeneous transportation resources, reinforcement learning-based NSGA-II, neighborhood structure

摘要：

针对天车与自动引导小车构成的异构运输资源在柔性作业车间中的集成调度问题，以最小化最大完工时间和总能耗为优化目标，提出一种融合强化学习机制的多目标进化算法。设计了三种混合初始化策略以提升种群质量与多样性；引入强化学习以实现遗传算子参数的自适应控制，构建基于关键路径的混合邻域结构以同时优化最大完工时间和总能耗，引导算法高效探索高质量解空间。最后，通过消融实验与对比实验验证了所提算法在求解异构运输资源柔性作业车间调度问题中的有效性与稳定性。

关键词: 柔性作业车间, 异构运输资源, 强化学习增强NSGA-Ⅱ算法, 邻域结构

CLC Number:

TH165

ZHANG Guohui, WANG Wendi, YU Nana, WU Changjun, KOU Xiaofei. Integrated Scheduling for Flexible Job Shops with Heterogeneous Transport Resources[J]. China Mechanical Engineering, 2026, 37(7): 1695-1707.

张国辉, 王文迪, 余娜娜, 邬昌军, 寇晓菲. 考虑异构运输资源的柔性作业车间集成调度问题[J]. 中国机械工程, 2026, 37(7): 1695-1707.

Figures/Tables 21

Fig.1 3D job shop layout

Tab.1 Notation and definitions

变量	定义	变量	定义
n	工件总数	$T u p e m p t y (τ i, j)$ ， $T u p l o a d (τ i, j)$	天车执行运输任务τ_i，j 时，空载与负载的上升时间
$I = 1,2, ⋯, n$	工件索引集合	$T d o w n e m p t y (τ i, j)$ ， $T d o w n l o a d (τ i, j)$	天车执行运输任务τ_i，j 时，空载与负载的下降时间
i	工件索引	$T x e m p t y (τ i, j)$ ， $T x l o a d (τ i, j)$	天车执行运输任务τ_i，j 时，小车空载和负载状态下的水平移动时间
n_i	工件i的工序总数	$T y e m p t y (τ i, j)$ ， $T y l o a d (τ i, j)$	天车执行运输任务τ_i，j 时，龙门架空载和负载状态下的水平移动时间
$J i = 1,2, ⋯, n i$	工件i的工序索引集合	$T i, j, k r u n$	O_i，j 在机器k上的加工时间
j	工序索引	$T k i d l e$	机器k的空闲时间
O_i，j	工件i的第j道工序	$P v e m p t y$ ， $P v l o a d$	AGV的空载功率、负载功率
O_i，j_-1	工件i的第j道工序的紧前工序	$P u p e m p t y$ ， $P u p l o a d$	起重机构上升过程中的空载功率和负载功率
τ_i，j	工件i在进入工序O_i，j 前对应的运输任务	$P d o w n e m p t y$ ， $P d o w n l o a d$	起重机构下降过程中的空载功率和负载功率
m	机器总数	$P x e m p t y$ ， $P x l o a d$	小车移动过程中的空载功率和负载功率
$M = 1,2, ⋯, m$	机器索引集合	$P y e m p t y$ ， $P y l o a d$	龙门架移动过程中的空载功率和负载功率
k	机器索引	$P i, j, k r u n$ ， $P k i d l e$	机器k的加工功率、空闲功率
M_i，j	可加工工序O_i，j 的候选机器集合	x_i，j，k	若工序O_i，j 分配在机器k上，则x_i，j，k 为1，否则为0
β	运输设备总数	y_i，j，j_-1_，k	若工序O_i，j 和工序O_i，j_-1都安排在机器k上，则y_i，j，j_-1_，k 为1，否则为0
$S = 1,2, ⋯, β$	运输设备索引集合	W_i，j，v	若运输任务 $τ i, j$ 由运输设备v执行，则W_i，j，v 为1；否则为0
v	运输设备索引	$E i, j p$	工序O_i，j 的加工能耗
ω_i，j	工件i在执行运输任务τ_i，j 时的质量	$E k i$	机器k空闲能耗
Q_v	运输设备v的最大载重	$E x, y e m p t y (τ i, j)$ ， $E x, y l o a d (τ i, j)$	天车执行运输任务τ_i，j 时的空载/负载水平移动的能耗
V	运输设备的速度	$E u p e m p t y (τ i, j)$ ， $E u p l o a d (τ i, j)$	天车执行运输任务τ_i，j 时上升的空载能耗和负载能耗
q	天车水平方向索引， $q ∈ x, y$	$E d o w n e m p t y (τ i, j)$ ， $E d o w n l o a d (τ i, j)$	天车执行运输任务τ_i，j 时下降的空载能耗和负载能耗
M_max	足够大的常数	B_i，j，C_i，j	工序O_i，j 的开始时间和完成时间
C_i	工件i的完工时间	$d i, j a$	运输任务τ_i，j 由AGV执行时的运输距离
C_max	最大完工时间	$d i, j (x)$ ， $d i, j (y)$	运输任务τ_i，j 由天车执行的X向和Y向的移动距离
E_p	加工总能耗	f（ω_i，j ）	载重影响函数
E_c	天车运输总能耗	TS_k，TE_k	机器k某一空闲时间段的开始时刻和结束时刻
E_a	AGV运输总能耗	ST_i_，_j_，_v （τ_i，j ），ET_i_，_j_，_v （τ_i，j ）	运输任务τ_i，j 由运输设备v执行时的开始时间和结束时间
E	总能耗	T^empty（τ_i，j ）， T^laod（τ_i，j ）	运输任务τ_i，j 由AGV执行时的空载移动时间和负载移动时间

Tab.1 Notation and definitions

变量	定义	变量	定义
n	工件总数	$T u p e m p t y (τ i, j)$ ， $T u p l o a d (τ i, j)$	天车执行运输任务τ_i，j 时，空载与负载的上升时间
$I = 1,2, ⋯, n$	工件索引集合	$T d o w n e m p t y (τ i, j)$ ， $T d o w n l o a d (τ i, j)$	天车执行运输任务τ_i，j 时，空载与负载的下降时间
i	工件索引	$T x e m p t y (τ i, j)$ ， $T x l o a d (τ i, j)$	天车执行运输任务τ_i，j 时，小车空载和负载状态下的水平移动时间
n_i	工件i的工序总数	$T y e m p t y (τ i, j)$ ， $T y l o a d (τ i, j)$	天车执行运输任务τ_i，j 时，龙门架空载和负载状态下的水平移动时间
$J i = 1,2, ⋯, n i$	工件i的工序索引集合	$T i, j, k r u n$	O_i，j 在机器k上的加工时间
j	工序索引	$T k i d l e$	机器k的空闲时间
O_i，j	工件i的第j道工序	$P v e m p t y$ ， $P v l o a d$	AGV的空载功率、负载功率
O_i，j_-1	工件i的第j道工序的紧前工序	$P u p e m p t y$ ， $P u p l o a d$	起重机构上升过程中的空载功率和负载功率
τ_i，j	工件i在进入工序O_i，j 前对应的运输任务	$P d o w n e m p t y$ ， $P d o w n l o a d$	起重机构下降过程中的空载功率和负载功率
m	机器总数	$P x e m p t y$ ， $P x l o a d$	小车移动过程中的空载功率和负载功率
$M = 1,2, ⋯, m$	机器索引集合	$P y e m p t y$ ， $P y l o a d$	龙门架移动过程中的空载功率和负载功率
k	机器索引	$P i, j, k r u n$ ， $P k i d l e$	机器k的加工功率、空闲功率
M_i，j	可加工工序O_i，j 的候选机器集合	x_i，j，k	若工序O_i，j 分配在机器k上，则x_i，j，k 为1，否则为0
β	运输设备总数	y_i，j，j_-1_，k	若工序O_i，j 和工序O_i，j_-1都安排在机器k上，则y_i，j，j_-1_，k 为1，否则为0
$S = 1,2, ⋯, β$	运输设备索引集合	W_i，j，v	若运输任务 $τ i, j$ 由运输设备v执行，则W_i，j，v 为1；否则为0
v	运输设备索引	$E i, j p$	工序O_i，j 的加工能耗
ω_i，j	工件i在执行运输任务τ_i，j 时的质量	$E k i$	机器k空闲能耗
Q_v	运输设备v的最大载重	$E x, y e m p t y (τ i, j)$ ， $E x, y l o a d (τ i, j)$	天车执行运输任务τ_i，j 时的空载/负载水平移动的能耗
V	运输设备的速度	$E u p e m p t y (τ i, j)$ ， $E u p l o a d (τ i, j)$	天车执行运输任务τ_i，j 时上升的空载能耗和负载能耗
q	天车水平方向索引， $q ∈ x, y$	$E d o w n e m p t y (τ i, j)$ ， $E d o w n l o a d (τ i, j)$	天车执行运输任务τ_i，j 时下降的空载能耗和负载能耗
M_max	足够大的常数	B_i，j，C_i，j	工序O_i，j 的开始时间和完成时间
C_i	工件i的完工时间	$d i, j a$	运输任务τ_i，j 由AGV执行时的运输距离
C_max	最大完工时间	$d i, j (x)$ ， $d i, j (y)$	运输任务τ_i，j 由天车执行的X向和Y向的移动距离
E_p	加工总能耗	f（ω_i，j ）	载重影响函数
E_c	天车运输总能耗	TS_k，TE_k	机器k某一空闲时间段的开始时刻和结束时刻
E_a	AGV运输总能耗	ST_i_，_j_，_v （τ_i，j ），ET_i_，_j_，_v （τ_i，j ）	运输任务τ_i，j 由运输设备v执行时的开始时间和结束时间
E	总能耗	T^empty（τ_i，j ）， T^laod（τ_i，j ）	运输任务τ_i，j 由AGV执行时的空载移动时间和负载移动时间

Fig.2 Overhead crane system

Fig.3 Overhead Crane transportation operations

Fig.4 Three-segment encoding

Fig.5 Left insertion decoding

Fig.6 Crossover operator

Fig.7 Mutation operator

Fig.8 Critical path and critical block

Fig.9 Algorithm flowchart

Tab.2 Action definition

动作D	P_c	P_m
a₁	0.50~0.55	0.01~0.02
a₂	0.55~0.60	0.02~0.03
		
a₁₀	0.95~1.00	0.10~0.11

Tab.3 Parameter combination experiment table

实验次数	α	γ	ε	G_th	IGD
1	0.6	0.6	0.80	50	0.3068
2	0.6	0.7	0.85	60	0.3229
3	0.6	0.8	0.90	70	0.2558
4	0.6	0.9	0.95	80	0.3015
5	0.7	0.6	0.85	70	0.3297
6	0.7	0.7	0.80	80	0.4177
7	0.7	0.8	0.95	50	0.3352
8	0.7	0.9	0.90	60	0.3408
9	0.8	0.6	0.90	80	0.3090
10	0.8	0.7	0.95	70	0.3645
11	0.8	0.8	0.80	60	0.3373
12	0.8	0.9	0.85	50	0.4598
13	0.9	0.6	0.95	60	0.2605
14	0.9	0.7	0.90	50	0.2202
15	0.9	0.8	0.85	80	0.4455
16	0.9	0.9	0.80	70	0.2237

Fig.10 Mean main effects plot

Tab.4 IGD of 3 strategies

算例	RLNSGA-Ⅱ	ARLNSGA-Ⅱ	BRLNSGA-Ⅱ
HMK01	0.3366	0.3678	0.5167
HMK02	0.2425	0.2598	0.6389
HMK03	0.2273	0.2471	0.5161
HMK04	0.3474	0.3783	0.4034
HMK05	0.3630	0.3759	0.6896
HMK06	0.3685	0.3706	0.6734
HMK07	0.2935	0.3202	0.4413
HMK08	0.3608	0.3940	0.4093
HMK09	0.3026	0.3537	0.6774
HMK10	0.2902	0.2746	0.6802

Fig. 11 Box plot of IGD values for the three strategies

Tab.5 SC of the 3 algorithms

算例	RLNSGA-Ⅱ vs ARLNSGA-Ⅱ		RLNSGA-Ⅱ vs BRLNSGA-Ⅱ
算例	SC（R，A）	SC（A，R）	SC（R，B）	SC（B，R）
HMK01	1.0000	0.0000	1.0000	0.0000
HMK02	1.0000	0.0000	0.6667	0.0000
HMK03	0.6000	0.0000	0.6667	0.0000
HMK04	0.7500	0.0000	0.8889	0.0000
HMK05	1.0000	0.0000	0.8000	0.0000
HMK06	1.0000	0.0000	1.0000	0.0000
HMK07	0.6000	0.0000	0.0000	0.4000
HMK08	0.0000	0.8000	0.4000	0.0000
HMK09	1.0000	0.0000	0.6777	0.0000
HMK10	1.0000	0.0000	1.0000	0.0000

Tab.6 IGD of various algorithms

算例	RLNSGA-Ⅱ	DQNSGA	MOEA	NSGA-Ⅱ
MK01	0.1922	0.3541	0.603	0.3460
MK02	0.1722	0.2884	0.603	0.3909
MK03	0.2041	0.2687	0.6070	0.2909
MK04	0.1846	0.2393	0.4990	0.2908
MK05	0.2905	0.4044	0.5971	0.4639
MK06	0.3313	0.3522	0.6813	0.3314
MK07	0.2763	0.3486	0.5691	0.3217
MK08	0.4339	0.4087	0.6448	0.4089
MK09	0.2120	0.3737	0.7595	0.430
MK10	0.2883	0.3264	0.6881	0.3821

Fig.12 Boxplot of IGD for different algorithms

Tab.7 Pairwise comparison results of algorithms based on SC

算例	RLNSGA-Ⅱ vs DQNSGA		RLNSGA-Ⅱ vs MOEA		RLNSGA-Ⅱ vs NSGA-Ⅱ
算例	SC （R，D）	SC （D，R）	SC （R，M）	SC（M，R）	SC （R，N）	SC （N，R）
HMK01	1.0000	0.0000	1.0000	0.0000	0.5000	0.0000
HMK02	0.6667	0.0000	1.0000	0.0000	0.5000	0.0000
HMK03	0.5000	0.0000	1.0000	0.0000	1.0000	0.0000
HMK04	0.7500	0.0000	1.0000	0.0000	0.0000	0.3333
HMK05	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
HMK06	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
HMK07	0.3077	0.2000	0.6667	0.3333	0.1111	0.1667
HMK08	1.0000	0.0000	1.0000	0.0000	0.0000	0.3333
HMK09	0.6667	0.0000	1.0000	0.0000	1.0000	0.0000
HMK10	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000

Fig.13 Makespan and machine energy consumption convergence curves for HMK01 instance

Fig.14 HMK01 Case Gantt Chart

References 24

[1]	祝正宇，郭具涛，吕佑龙，等. 面向柔性作业车间生产调度的深度强化学习方法［J］. 中国机械工程， 2024， 35（11）： 2007-2014.
	ZHU Zhengyu， GUO Jutao， YoulongLYU， et al. Deep Reinforcement Learning Method for Flexible Job Shop Scheduling［J］. China Mechanical Engineering， 2024， 35（11）： 2007-2014.
[2]	DU Yu， LI Junqing， LI Chengdong， et al. A Reinforcement Learning Approach for Flexible Job Shop Scheduling Problem with Crane Transportation and Setup Times［J］. IEEE Transactions on Neural Networks and Learning Systems， 2024， 35（4）： 5695-5709.
[3]	李西兴，杨道明，李鑫，等. 基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法［J］. 中国机械工程， 2021， 32（8）： 938-950.
	LI Xixing， YANG Daoming， LI Xin， et al. Flexible Job Shop AGV Fusion Scheduling Method Based on HGWOA［J］. China Mechanical Engineering， 2021， 32（8）： 938-950.
[4]	张国辉，蔡翌豪，李志霄，等. 考虑有限AGV运输资源的柔性作业车间调度研究［J］. 中国机械工程， 2025， 36（8）： 1811-1823.
	ZHANG Guohui， CAI Yihao， LI Zhixiao， et al. Research on Flexible Job Shop Scheduling Problems Considering Limited AGV Transportation Resources［J］. China Mechanical Engineering， 2025， 36（8）： 1811-1823.
[5]	LIU Chao， HAN Yuyan， WANG Yuting， et al. Multi-population Coevolutionary Algorithm for a Green Multi-objective Flexible Job Shop Scheduling Problem with Automated Guided Vehicles and Variable Processing Speed Constraints［J］. Swarm and Evolutionary Computation， 2024， 91： 101774.
[6]	李文贵，姚友杰，李新宇. 考虑异构AGV的柔性作业车间集成调度［J］. 计算机集成制造系统， 2025， 31（5）： 1539-1554.
	LI Wengui， YAO Youjie， LI Xinyu. Integration Scheduling of Flexible Job Shop with Heterogeneous AGVs［J］. Computer Integrated Manufacturing Systems， 2025， 31（5）： 1539-1554.
[7]	朱光宇，贾唯鸿，李德彪. 机器与AGV联合利用再生能源的混合流水车间调度问题［J］. 北京航空航天大学学报， 2025， 51（2）： 368-379.
	ZHU Guangyu， JIA Weihong， LI Debiao. Hybrid Flow-shop Scheduling Problem Considering Joint of Machine and AGV with Renewable Energy［J］. Journal of Beijing University of Aeronautics and Astronautics， 2025， 51（2）： 368-379.
[8]	王亚昆，刘应波，吴永明，等. 改进NSGA-Ⅱ算法求解考虑运输约束的柔性作业车间节能调度问题［J］. 计算机集成制造系统， 2023， 29（9）： 3028-3040.
	WANG Yakun， LIU Yingbo， WU Yongming， et al. Improved NSGA-Ⅱ Algorithm to Solve Energy-saving Scheduling Problem of Flexible Job Shop Considering Transportation Constraints［J］. Computer Integrated Manufacturing Systems， 2023， 29（9）： 3028-3040.
[9]	CHEN Rensheng， WU Bin， WANG Hua， et al. A Q-learning Based NSGA-II for Dynamic Flexible Job Shop Scheduling with Limited Transportation Resources［J］. Swarm and Evolutionary Computation， 2024， 90： 101658.
[10]	王赟，马荣，唐思源. 基于改进鲸鱼优化算法的AGV柔性作业车间多目标优化调度［J］. 现代制造工程， 2024（7）： 17-25.
	WANG Yun， MA Rong， TANG Siyuan. An IWOA for Multi-objective Optimization Scheduling of AGV Flexible Job Shop［J］. Modern Manufacturing Engineering， 2024（7）： 17-25.
[11]	刘超，韩玉艳，王玉亭，等. 可变邻域搜索算法优化多目标变加速FJSP-AGVs［J/OL］.控制工程，2024： 1-12. （2024-09-09）［2025-06-04］. .
	LIU Chao， HAN Yuyan， WANG Yuting， et al. Optimizing Multi-objective FISP-AGVs with Variable Processing Speed Using Variable Neighborhood Search Algorithm［J/OL］. Control Engineering of China， 2024： 1-12. （2024-09-09）［2025-06-04］. .
[12]	李俊青，杜宇，田杰，等. 带运输资源约束柔性作业车间调度问题的人工蜂群算法［J］. 电子学报， 2021， 49（2）： 324-330.
	LI Junqing， DU Yu， TIAN Jie， et al. An Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling with Transportation Resource Constraints［J］. Acta Electronica Sinica， 2021， 49（2）： 324-330.
[13]	刘璐，宋海草，姜天华，等. 基于改进生物迁徙算法的双资源柔性作业车间节能调度问题［J］. 计算机集成制造系统， 2024， 30（9）： 3125-3141.
	LIU Lu， SONG Haicao， JIANG Tianhua， et al. Modified Biology Migration Algorithm for Dual-resource Energy-saving Flexible Job Shop Scheduling Problem［J］. Computer Integrated Manufacturing Systems， 2024， 30（9）： 3125-3141.
[14]	ZHANG Fayong， LI Rui， GONG Wenyin. Deep Reinforcement Learning-based Memetic Algorithm for Energy-aware Flexible Job Shop Scheduling with Multi-AGV［J］. Computers & Industrial Engineering， 2024， 189： 109917.
[15]	王玉芳，华晓麟，章殿清，等. 基于混合Jaya算法的多时间约束柔性作业车间节能调度［J］. 控制工程， 2025， 32（6）： 1074-1085.
	WANG Yufang， HUA Xiaolin， ZHANG Dianqing， et al. Energy-efficient Scheduling of Flexible Job-shop with Multiple Temporal Constraints Based on Hybrid Jaya Algorithm［J］. Control Engineering of China， 2025， 32（6）： 1074-1085.
[16]	YAO Youjie， WANG Qingzheng， WANG Cuiyu， et al. Knowledge-based Multi-objective Evolutionary Algorithm for Energy-efficient Flexible Job Shop Scheduling with Mobile Robot Transportation［J］. Advanced Engineering Informatics， 2024， 62： 102647.
[17]	张洪亮，徐公杰，鲍蔷，等. 考虑运输时间的分布式柔性作业车间绿色调度［J］. 中国机械工程， 2022， 33（21）： 2554-2563.
	ZHANG Hongliang， XU Gongjie， BAO Qiang， et al. Distributed Flexible Job Shop Green Scheduling with Transportation Time［J］. China Mechanical Engineering， 2022， 33（21）： 2554-2563.
[18]	张国辉，张得雨，闫少峰，等. 考虑工人协作与学习效应的柔性作业车间调度［J］. 计算机集成制造系统， 2024， 30（12）： 4369-4385.
	ZHANG Guohui， ZHANG Deyu， YAN Shaofeng， et al. Flexible Job Shop Scheduling with Worker Collaboration and Learning Effect［J］. Computer Integrated Manufacturing Systems， 2024， 30（12）： 4369-4385.
[19]	ZHANG Guohui， YAN Shaofeng， SONG Xiaohui， et al. Evolutionary Algorithm Incorporating Reinforcement Learning for Energy-conscious Flexible Job-shop Scheduling Problem with Transportation and Setup Times［J］. Engineering Applications of Artificial Intelligence， 2024， 133： 107974.
[20]	周豪，张超勇，刘辉，等. 改进Jaya算法求解混合流水车间调度问题［J］. 中国机械工程， 2024， 35（8）： 1462-1471.
	ZHOU Hao， ZHANG Chaoyong， LIU Hui， et al. Improved Jaya Algorithm for Solving HFSPS［J］. China Mechanical Engineering， 2024， 35（8）： 1462-1471
[21]	张国辉，李志霄，张利平，等. 基于强化学习协同进化算法求解柔性作业车间节能调度问题［J］. 计算机应用研究， 2025， 42（7）： 2039-2047.
	ZHANG Guohui， LI Zhixiao， ZHANG Liping， et al. Reinforcement Learning Based Co-evolutionary Algorithm for Solving Flexible Job Shop Energy Efficient Scheduling Problem［J］. Application Research of Computers， 2025， 42（7）： 2039-2047.
[22]	TANG Hongtao， XIAO Yu， ZHANG Wei， et al. A DQL-NSGA-III Algorithm for Solving the Flexible Job Shop Dynamic Scheduling Problem［J］. Expert Systems with Applications， 2024， 237： 121723.
[23]	ZHANG Qingfu， LI Hui. MOEA/D： a Multiobjective Evolutionary Algorithm Based on Decomposition［J］. IEEE Transactions on Evolutionary Computation， 2007， 11（6）： 712-731.
[24]	DEB K， PRATAP A， AGARWAL S， et al. A Fast and Elitist Multiobjective Genetic Algorithm： NSGA-II［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.