考虑有限AGV运输资源的柔性作业车间调度研究

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

摘要/Abstract

摘要：

针对智能制造环境中有限自动导引车（AGV）运输资源的柔性作业车间调度问题，以最小化最长完工时间、总能耗和工件的交货期惩罚值为目标，建立有限AGV运输资源的集成调度模型。提出一种改进的非支配排序遗传算法（NSGA-Ⅱ），针对集成调度模型构建三段式编码方案，设计三种初始化规则提高初始种群的质量和多样性。结合关键路径，提出一种改进的变邻域搜索以增强算法的局部搜索能力。实验部分采用多种评价指标与其他算法进行对比，实验结果表明：在不同规模标准测试算例和航空企业实际生产案例下，所提算法均能有效求解有限AGV运输资源的集成调度问题。同时分析不同AGV数量下集成调度模型的有效性，得出柔性作业车间中AGV数量符合边际效应递减规律的结论，为实际制造车间配置AGV提供了参考。

关键词: 有限运输资源, 改进的非支配排序遗传算法, 柔性作业车间调度问题, 自动导引车

Abstract:

Aiming at the flexible job shop scheduling problems of limited AGV transportation resources in the intelligent manufacturing environments， an integrated scheduling model for limited AGV transportation resources was established with the objective of minimizing the maximum completion time， total energy consumption and the delivery penalty value of workpieces. An improved NSGA -II solution algorithm was proposed to construct a three-stage coding scheme for the integrated scheduling model， and three initialization rules were designed to improve the quality and diversity of the initial population. Combined with the critical path， an improved variable neighborhood search was proposed to enhance the local search capability of the algorithm. In the experimental part， the algorithm was compared with other algorithms using various evaluation indexes， and the experimental results show that the algorithm may effectively solve the integrated scheduling problems of limited AGV transportation resources under different sizes of standard test cases and actual production cases of aviation enterprises. Meanwhile， the effectiveness of the integrated scheduling model was analyzed under different numbers of AGVs， and it is concluded that the number of AGVs in the flexible operation workshop conforms to the law of diminishing marginal effectiveness， so as to provide a reference for the configuration of AGVs in the actual manufacturing workshop.

Key words: limited transportation resource, improved non-dominated sorted genetic algorithm-II （improved NSGA-II）, flexible job shop scheduling problem （FJSP）, automatic guided vehicle（AGV）

中图分类号:

TH165

张国辉, 蔡翌豪, 李志霄, 郭胜会, 张海军. 考虑有限AGV运输资源的柔性作业车间调度研究[J]. 中国机械工程, 2025, 36(8): 1811-1823.

Guohui ZHANG, Yihao CAI, Zhixiao LI, Shenghui GUO, Haijun ZHANG. Research on Flexible Job Shop Scheduling Problems Considering Limited AGV Transportation Resources[J]. China Mechanical Engineering, 2025, 36(8): 1811-1823.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://www.cmemo.org.cn/CN/10.3969/j.issn.1004-132X.2025.08.016

https://www.cmemo.org.cn/CN/Y2025/V36/I8/1811

图/表 25

参考文献 24

[1]	张国辉，张得雨，闫少峰，等. 考虑工人协作与学习效应的柔性作业车间调度［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.
[2]	王玉芳，章殿清，华晓麟，等. 面向航空结构件的双资源分布式柔性调度研究［J］. 系统仿真学报， 2024， 36（11）： 2722-2740.
	WANG Yufang， ZHANG Dianqing， HUA Xiaolin， et al. Dual-resource Constrained Distributed Flexible Scheduling for Aerospace Structural Components［J］. Journal of System Simulation， 2024， 36（11）： 2722-2740.
[3]	LI Yinghe， CHEN Xiaohui， AN Youjun， et al. Integrating Machine Layout， Transporter Allocation and Worker Assignment into Job-shop Scheduling Solved by an Improved Non-dominated Sorting Genetic Algorithm［J］. Computers & Industrial Engineering， 2023， 179： 109169.
[4]	LI Wenlong， LI Huan， WANG Yuting， et al. Optimizing Flexible Job Shop Scheduling with Automated Guided Vehicles Using a Multi-strategy-driven Genetic Algorithm［J］. Egyptian Informatics Journal， 2024， 25： 100437.
[5]	YAO Youjie， GUI Lin， LI Xinyu， et al. Tabu Search Based on Novel Neighborhood Structures for Solving Job Shop Scheduling Problem Integrating Finite Transportation Resources［J］. Robotics and Computer-Integrated Manufacturing， 2024， 89： 102782.
[6]	REN Weibo， YAN Yan， HU Yaoguang， et al. Joint Optimisation for Dynamic Flexible Job-shop Scheduling Problem with Transportation Time and Resource Constraints［J］. International Journal of Production Research， 2022， 60（18）： 5675-5696.
[7]	LIU Jiaojiao， SUN Baofeng， LI Gendao， et al. Multi-objective Adaptive Large Neighbourhood Search Algorithm for Dynamic Flexible Job Shop Schedule Problem with Transportation Resource［J］. Engineering Applications of Artificial Intelligence， 2024， 132： 107917.
[8]	YAO Youjie， LIU Qihao， FU Ling， et al. A Novel Mathematical Model for the Flexible Job-shop Scheduling Problem with Limited Automated Guided Vehicles［J］. IEEE Transactions on Automation Science and Engineering， 2024， 22： 7449-7462.
[9]	张国辉，闫少峰，陆熙熙，等. 改进混合多目标蚁群算法求解带运输时间和调整时间的柔性作业车间调度问题［J］. 计算机应用研究， 2023， 40（12）： 3690-3695.
	ZHANG Guohui， YAN Shaofeng， LU Xixi， et al. Improved Hybrid Multi-objective Ant Colony Optimization for Flexible Job-shop Scheduling Problem with Transportation Time and Setup Time［J］. Application Research of Computers， 2023， 40（12）： 3690-3695.
[10]	JIANG Xingyu， TIAN Zhiqiang， LIU Weijun， et al. Energy-efficient Scheduling of Flexible Job Shops with Complex Processes： a Case Study for the Aerospace Industry Complex Components in China［J］. Journal of Industrial Information Integration， 2022， 27： 100293.
[11]	XU Gongjie， BAO Qiang， ZHANG Hongliang. Multi-objective Green Scheduling of Integrated Flexible Job Shop and Automated Guided Vehicles［J］. Engineering Applications of Artificial Intelligence， 2023， 126： 106864.
[12]	张洪亮，徐公杰，鲍蔷，等. 考虑运输时间的分布式柔性作业车间绿色调度［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.
[13]	YUAN Minghai， ZHENG Liang， HUANG Hanyu， et al. Research on Flexible Job Shop Scheduling Problem with AGV Using Double DQN［J］. Journal of Intelligent Manufacturing， 2025， 36（1）： 509-535.
[14]	ZHANG Min， WANG Liang， QIU Fusheng， et al. Dynamic Scheduling for Flexible Job Shop with Insufficient Transportation Resources via Graph Neural Network and Deep Reinforcement Learning［J］. Computers & Industrial Engineering， 2023， 186： 109718.
[15]	YAO Youjie， LI Xinyu， GAO Liang. A DQN-based Memetic Algorithm for Energy-efficient Job Shop Scheduling Problem with Integrated Limited AGVs［J］. Swarm and Evolutionary Computation， 2024， 87： 101544.
[16]	WANG Jingjing， HAN Honggui， WANG Ling. A Feedback Learning-based Memetic Algorithm for Energy-aware Distributed Flexible Job-shop Scheduling with Transportation Constraints［J］. IEEE Transactions on Evolutionary Computation， 2024， PP（99）： 1.
[17]	祝正宇，郭具涛，吕佑龙，等. 面向柔性作业车间生产调度的深度强化学习方法［J］. 中国机械工程， 2024， 35（11）： 2007-2014.
	ZHU Zhengyu， GUO Jutao， Youlong LYU， et al. Deep Reinforcement Learning Method for Flexible Job Shop Scheduling［J］. China Mechanical Engineering， 2024， 35（11）： 2007-2014.
[18]	PAN Zixiao， WANG Ling， ZHENG Jie， et al. A Learning-based Multipopulation Evolutionary Optimization for Flexible Job Shop Scheduling Problem with Finite Transportation Resources［J］. IEEE Transactions on Evolutionary Computation， 2023， 27（6）： 1590-1603.
[19]	ZHANG Guohui， HU Yifan， SUN Jinghe， et al. An Improved Genetic Algorithm for the Flexible Job Shop Scheduling Problem with Multiple Time Constraints［J］. Swarm and Evolutionary Computation， 2020， 54： 100664.
[20]	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.
[21]	周亚勤，杨长祺，吕佑龙，等. 双资源约束的航天结构件车间生产调度方法［J］. 机械工程学报， 2018， 54（9）： 55-63.
	ZHOU Yaqin， YANG Changqi， Youlong LYU， et al. Scheduling the Production of Aerospace Structural Parts with Dual Resource Constraints［J］. Journal of Mechanical Engineering， 2018， 54（9）： 55-63.
[22]	陈魁，毕利，王文雅. 柔性作业车间AGV与机器双资源集成调度研究［J］. 系统仿真学报， 2022， 34（3）： 461-469.
	CHEN Kui， BI Li， WANG Wenya. Research on Integrated Scheduling of AGV and Machine in Flexible Job Shop［J］. Journal of System Simulation， 2022， 34（3）： 461-469.
[23]	徐云琴，叶春明，曹磊. 含有AGV的柔性车间调度优化研究［J］. 计算机应用研究， 2018， 35（11）： 3271-3275.
	XU Yunqin， YE Chunming， CAO Lei. Research on Flexible Job-shop Scheduling Problem with AGV Constraints［J］. Application Research of Computers， 2018， 35（11）： 3271-3275.
[24]	马千慧，梁晓磊，刘星雨，等. 多AGV和机器集成的多目标柔性作业车间调度研究［J］. 计算机工程与应用， 2023， 59（1）： 278-290.
	MA Qianhui， LIANG Xiaolei， LIU Xingyu， et al. Research on Multi-objective Flexible Job Shop Scheduling with Multiple AGVs and Machines Integration［J］. Computer Engineering and Applications， 2023， 59（1）： 278-290.

工件	工序	加工机器和加工时间
工件	工序	M₁	M₂	M₃	M₄
J₁	O₁₁	3	10	—	3
J₁	O₁₂	—	4	5	2
J₂	O₂₁	—	7	5	—
	O₂₂	6	2	—	8
	O₂₃	—	6	4	2
J₃	O₃₁	4	—	2	—
J₃	O₃₂	—	3	6	—
AGV编号		1、2、3

工件	工序	加工机器和加工时间
工件	工序	M₁	M₂	M₃	M₄
J₁	O₁₁	3	10	—	3
J₁	O₁₂	—	4	5	2
J₂	O₂₁	—	7	5	—
	O₂₂	6	2	—	8
	O₂₃	—	6	4	2
J₃	O₃₁	4	—	2	—
J₃	O₃₂	—	3	6	—
AGV编号		1、2、3

参数	L/U区	M₁	M₂	M₃	M₄
L/U区	0	2	3	2	4
M₁	2	0	4	3	2
M₂	3	4	0	3	4
M₃	2	3	3	0	4
M₄	4	2	4	4	0

参数	L/U区	M₁	M₂	M₃	M₄
L/U区	0	2	3	2	4
M₁	2	0	4	3	2
M₂	3	4	0	3	4
M₃	2	3	3	0	4
M₄	4	2	4	4	0

参数	定义
i	工件号； i=1，2，…，n
j	工序号； j=1，2，…，l_i
k	机器号； k=1，2，…，m
v	AGV号； v=1，2，…，s
l_i	工件i的工序总数
O_ij	工件i的第j道工序
C_i	工件i的完工时间
t_s_ij	工件i的第j道工序的开工时间
t_c_ij	工件i的第j道工序的完工时间
T_ijk	工件i的第j道工序在机器k上的加工时间
S_ijks	工件i的第j道工序在机器k上的开始加工时间
E_ijks	工件i的第j道工序在机器k上的开始终止时间
TSE（i，j，v）	v运输O_i，j-₁时空载行程开始时间
ETE（i，j，v）	v运输O_i，j-₁时空载行程结束时间
TLB（i，j，v）	v运输O_i，j-₁时负载行程开始时间
ETL（i，j，v）	v运输O_i，j-₁时负载行程结束时间
P_ML_ijk	工件i的第j道工序在机器k上的负载功率
P_MN_ijk	工件i的第j道工序在机器k上的空载功率
P_AL_ijv	v的负载功率
P_AN_ijv	v的空载功率
E_P	加工能耗
E_I	空闲能耗
E_T	运输能耗
D_E_i	最早交货期
D_L_i	最晚交货期
X_ijkp	0-1决策变量，工件i的第j道工序在机器k上加工为1，否则为0
R_ijkv	0-1决策变量，当工件i的第j道工序在机器k上加工选择AGVs完成运输任务为1，否则为0