Improved NSGA-II for Dual-resource Flexible Job Shop Scheduling Considering Worker Load

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

Abstract

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

CLC Number:

TP18

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

Figures/Tables 23

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 1

Table 2

Table 3

DOE experiment

实验次数	$∂$	$γ$	$ε$	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

Table 3

Fig. 6

Table 4

Table 5

Table 6

Table 7

Table 8

Table 9

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Fig. 13

Fig. 14

References 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