改进NSGA-II求解含工人负荷的双资源柔性作业车间调度

doi:10.16182/j.issn1004731x.joss.25-0607

摘要/Abstract

摘要：

针对考虑工人负荷的双资源约束柔性作业车间调度问题，提出一种融合强化学习的进化算法。设计符合问题特征的三段式编码，并结合3种初始化方式提高种群质量；设计基于工人工作负荷的左插入解码方式，保证工序的完成时间小于工人当日的最大可加工时间；构建2种基于关键路径的邻域结构，加强种群的局部探索能力；融合强化学习使算法的变异率与交叉率能够根据种群质量自适应改变。仿真实验验证了算法的优越性。

关键词: 柔性作业车间调度, 双资源约束, 强化学习, 工人负荷

Abstract:

For the dual-resource-constrained flexible job shop scheduling problem considering worker load, an evolutionary algorithm integrating reinforcement learning was proposed. A three-stage encoding conforming to the problem characteristics was designed, and three initialization methods were combined to improve the population quality; a left-insertion decoding method based on worker load was designed to ensure that the completion time of the operation is less than the maximum processable time of the worker on the current day; two neighborhood structures based on the critical path were constructed to enhance the local exploration ability of the population; reinforcement learning was integrated to enable the mutation rate and crossover rate of the algorithm to change adaptively according to the population quality. Simulation experiments verified the superiority of the algorithm.

Key words: flexible job shop scheduling, dual-resource constraint, reinforcement learning, worker load

中图分类号:

TP18

张国辉,任远,邬昌军等 . 改进NSGA-II求解含工人负荷的双资源柔性作业车间调度[J]. 系统仿真学报, 2026, 38(6): 1598-1612.

Zhang Guohui,Ren Yuan,Wu Changjun,et al . Improved NSGA-II for Dual-resource Flexible Job Shop Scheduling Considering Worker Load[J]. Journal of System Simulation, 2026, 38(6): 1598-1612.

图/表 23

图1

图2

图3

图4

图5

表1

表2

表3

DOE实验

实验次数	$∂$	$γ$	$ε$	IGD
1	0.5	0.5	0.5	0.310 6
2	0.5	0.6	0.6	0.327 1
3	0.5	0.7	0.7	0.288 5
4	0.5	0.8	0.8	0.320 6
5	0.6	0.5	0.6	0.332 2
6	0.6	0.6	0.5	0.300 5
7	0.6	0.7	0.8	0.332 4
8	0.6	0.8	0.7	0.266 7
9	0.7	0.5	0.7	0.265 1
10	0.7	0.6	0.8	0.314 3
11	0.7	0.7	0.5	0.327 3
12	0.7	0.8	0.6	0.313 0
13	0.8	0.5	0.8	0.309 8
14	0.8	0.6	0.7	0.330 7
15	0.8	0.7	0.6	0.308 9
16	0.8	0.8	0.5	0.335 4

表3

图6

表4

表5

表6

表7

表8

表9

图7

图8

图9

图10

图11

图12

图13

图14

参考文献 25

[1]	Lingling Lü, Zhang Chunjiang, Fan Jiaxin, et al. Deep Reinforcement Learning for Job Shop Scheduling Problems: A Comprehensive Literature Review[J]. Knowledge-Based Systems, 2025, 321: 113633.
[2]	张国辉, 李志霄, 张利平, 等. 基于强化学习协同进化算法求解柔性作业车间节能调度问题[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.
[3]	Zhang Hongliang, Chen Yi, Zhang Yuteng, et al. Energy-saving Distributed Flexible Job Shop Scheduling Optimization with Dual Resource Constraints Based on Integrated Q-learning Multi-objective Grey Wolf Optimizer[J]. CMES-Computer Modeling in Engineering and Sciences, 2024, 140(2): 1459-1483.
[4]	王凌, 李瑞, 陈靖方. 面向人机协同能效车间调度的群智能优化算法[J]. 中国科学(技术科学), 2024, 54(9): 1676-1692.
	Wang Ling, Li Rui, Chen Jingfang. A Swarm Intelligence Optimization Algorithm for Human-robot Collaborative Energy-efficient Shop Scheduling[J]. Scientia Sinica(Technologica), 2024, 54(9): 1676-1692.
[5]	Sanogo Kader, Abdelkader Mekhalef Benhafssa, Sahnoun M'hammed. A Multi-agent System Simulation of Job Shop Scheduling with Human Consideration: A Comparative Analysis of AGVs and AIVs[J]. Simulation Modelling Practice and Theory, 2025, 139: 103060.
[6]	张国辉, 张得雨, 闫少峰, 等. 考虑工人协作与学习效应的柔性作业车间调度[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.
[7]	Li Xixing, Guo Ao, Yin Xiyan, et al. A Q-learning Improved Differential Evolution Algorithm for Human-centric Dynamic Distributed Flexible Job Shop Scheduling Problem[J]. Journal of Manufacturing Systems, 2025, 80: 794-823.
[8]	Usman Shaban, Lu Cong. Job-shop Scheduling with Limited Flexible Workers Considering Ergonomic Factors Using an Improved Multi-objective Discrete Jaya Algorithm[J]. Computers & Operations Research, 2024, 162: 106456.
[9]	Li Hui, Peng Jianbiao, Wang Xi. An Efficient Two-stage Optimization Algorithm for a Flexible Job Shop Scheduling Problem with Worker Shift Arrangement[J]. Computers & Operations Research, 2024, 171: 106785.
[10]	王霄汉, 张霖, 任磊, 等. 基于强化学习的车间调度问题研究简述[J]. 系统仿真学报, 2021, 33(12): 2782-2791.
	Wang Xiaohan, Zhang Lin, Ren Lei, et al. Brief Review on Applying Reinforcement Learning to Job Shop Scheduling Problems[J]. Journal of System Simulation, 2021, 33(12): 2782-2791.
[11]	卢超, 肖洋, 张彪, 等. 柔性作业车间调度问题的课程强化学习算法[J]. 国防科技大学学报, 2025, 47(2): 49-59.
	Lu Chao, Xiao Yang, Zhang Biao, et al. Curriculum Reinforcement Learning Algorithm for Flexible Job Shop Scheduling Problems[J]. Journal of National University of Defense Technology, 2025, 47(2): 49-59.
[12]	Yang Zhijie, Hu Xinkai, Li Yibing, et al. A Q-learning-based Improved Multi-objective Genetic Algorithm for Solving Distributed Heterogeneous Assembly Flexible Job Shop Scheduling Problems with Transfers[J]. Journal of Manufacturing Systems, 2025, 79: 398-418.
[13]	Shi Zhiyuan, Si Jinghua, Zhang Jian, et al. A Deep Reinforcement Learning Method Based on Hindsight Experience Replay for Multi-objective Dynamic Job-shop Scheduling Problem[J]. Expert Systems with Applications, 2025, 284: 127989.
[14]	Liu Xi, Chen Xin, Chau Vincent, et al. Flexible Job Shop Scheduling Problem Using Graph Neural Networks and Reinforcement Learning[J]. Computers & Operations Research, 2025, 182: 107139.
[15]	李兴洲, 李艳武, 谢辉. 基于CNN的深度强化学习算法求解柔性作业车间调度问题[J]. 计算机工程与应用, 2024, 60(17): 312-320.
	Li Xingzhou, Li Yanwu, Xie Hui. Deep Reinforcement Learning Algorithm Based on CNN to Solve Flexible Job-shop Scheduling Problem[J]. Computer Engineering and Applications, 2024, 60(17): 312-320.
[16]	赵才, 吴亮红. 具有双资源约束的分布式装配混合流水车间调度[J/OL]. 中国机械工程. (2025-05-13) [2025-05-28]. .
	Zhao Cai, Wu Lianghong. Distributed Assembly Hybrid Flow Shop Scheduling with Dual Resource Constraints [J/OL]. China Mechanical Engineering. (2025-05-13)[2025-05-28]. .
[17]	李健, 李洹坤, 何鹏博, 等. 协同智能体强化学习算法的柔性作业车间调度方法研究[J]. 系统仿真学报, 2024, 36(11): 2699-2711.
	Li Jian, Li Huankun, He Pengbo, et al. Flexible Job Shop Scheduling Method Based on Collaborative Agent Reinforcement Learning Algorithm[J]. Journal of System Simulation, 2024, 36(11): 2699-2711.
[18]	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, Part A: 107974.
[19]	赵诗奎. 柔性作业车间调度的改进邻域结构混合算法[J]. 计算机集成制造系统, 2018, 24(12): 3060-3072.
	Zhao Shikui. Hybrid Algorithm Based on Improved Neighborhood Structure for Flexible Job Shop Scheduling[J]. Computer Integrated Manufacturing Systems, 2018, 24(12): 3060-3072.
[20]	张泽华, 杨波, 傅广, 等. 基于Sarsa的动态蜂群算法求解作业车间调度问题[J]. 组合机床与自动化加工技术, 2023(6): 188-192.
	Zhang Zehua, Yang Bo, Fu Guang, et al. A Dynamic Artificial Bee Colony Algorithm Based on Sarsa for Job-shop Scheduling Problem[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2023(6): 188-192.
[21]	郭羽, 唐敦兵, 张泽群. 基于深度强化学习的柔性作业车间调度方法[J]. 航空制造技术, 2024, 67(23): 114-120.
	Guo Yu, Tang Dunbing, Zhang Zequn. Flexible Job-shop Scheduling Method Based on Deep Reinforcement Learning[J]. Aeronautical Manufacturing Technology, 2024, 67(23): 114-120.
[22]	侯天天, 张守京. 基于改进离散蜉蝣算法的双资源柔性车间可持续调度方法[J]. 机电工程, 2023, 40(3): 407-414.
	Hou Tiantian, Zhang Shoujing. Dual Resource Flexible Job Shops Sustainable Scheduling Based on Improved Discrete Mayfly Algorithm[J]. Journal of Mechanical & Electrical Engineering, 2023, 40(3): 407-414.
[23]	Yuan Minghai, Li Yadong, Zhang Lizhi, et al. Research on Intelligent Workshop Resource Scheduling Method Based on Improved NSGA-II Algorithm[J]. Robotics and Computer-Integrated Manufacturing, 2021, 71: 102141.
[24]	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.
[25]	卫晨昊, 李敬敏, 李韵辰, 等. 改进的MOEA/D算法求解考虑机器恶化效应的柔性流水车间节能调度问题[J]. 计算机集成制造系统, 2026, 32(2): 585-598.
	Wei Chenhao, Li Jingmin, Li Yunchen, et al. Modified MOEA/D for Solving Energy-efficient Flexible Flow Shop Scheduling Problem with Machine Deterioration Effect[J]. Computer Integrated Manufacturing Systems, 2026, 32(2): 585-598.

动作	P_c	P_m
a₁	0.4< P_c≤0.45	0.01< P_m≤0.03
a₂	0.45< P_c≤0.5	0.03< P_m≤0.05
…
a₁₀	0.85< P_c≤0.9	0.19< P_m≤0.21

算例	QSNSGA	QSNSGA-QL
WA01	0.419 9	0.408 2
WA02	0.298 4	0.386 1
WA03	0.343 5	0.408 9
WA04	0.351 0	0.394 9
WA05	0.232 5	0.602 4
WA06	0.314 2	0.722 9
WA07	0.421 7	0.544 8
WA08	0.294 5	0.470 7
WA09	0.231 6	0.344 6
WA10	0.235 3	0.375 0

算例	QSNSGA	QSNSGA-LS
WA01	0.485 4	0.432 4
WA02	0.298 4	0.376 5
WA03	0.174 6	0.492 9
WA04	0.372 1	0.455 5
WA05	0.325 5	0.508 9
WA06	0.244 8	0.610 9
WA07	0.360 0	0.596 4
WA08	0.269 0	0.464 8
WA09	0.375 0	0.426 3
WA10	0.126 3	0.446 8

算例	QSNSGA vs QSNSGA-LS	QSNSGA vs QSNSGA-QL
WA01	1	0.25	0
WA02	1	0.4	0
WA03	1	1	0
WA04	1	1	0
WA05	1	0.750 0	0.133 3
WA06	1	0.333 3	0
WA07	0.5	0.5	0.25
WA08	0.5	1	0
WA09	1	1	0
WA10	1	0.5	0

算例	QSNSGA	MOEAD	IGA	DQNSGA
WA01	27.924 5	43.032 7	44.865 4	51.133 8
WA02	37.580 7	51.232 7	51.232 7	51.232 7
WA03	27.199 3	40.544 3	35.942 7	47.515 6
WA04	33.680 3	44.198 4	38.878 2	44.198 4
WA05	40.314 0	55.607 1	61.430 3	38.878 2
WA06	37.189 0	43.210 7	38.878 6	45.699 3
WA07	41.606 2	59.974 0	41.715 1	52.283 6
WA08	38.604 9	42.155 5	72.374 2	72.374 2
WA09	45.699 3	44.509 4	68.271 7	46.084 2
WA10	54.255 4	72.103 4	96.776 0	79.763 1