Improving NSGA-III Algorithm for Solving High-dimensional Many-objective Green Flexible Job Shop Scheduling Problem

doi:10.16182/j.issn1004731x.joss.23-0694

Abstract

Abstract:

Aiming at the poor initial solution quality and low local search efficiency of NSGA-III in solving the many-objective flexible job shop scheduling model, an improved NSGA-III (NSGA-III-TV) is proposed. Based on MSOS encoding, the different mixed initialization strategies are adopted for OS and MS chromosomes to improve the quality of initial solutions. Based on the critical path, an improved N6 neighborhood structure is used for neighborhood search, which effectively reduce the completion time and reducing search randomness. Three effective mutation operators are employed to expand the search space and improve the convergence capability in the later stages. Test results show that NSGA-III-TV has good performance and practicality in solving the high-dimensional many-objective flexible job shop scheduling problems, which provides strong support for the intelligent green transformation and the upgrading of manufacturing workshops of enterprises

Key words: green flexible job shop scheduling, high-dimensional multi-objective optimization, critical path, variable neighborhood search

CLC Number:

TP18

Xu Yigang, Chen Yong, Wang Chen, Peng Yunxian. Improving NSGA-III Algorithm for Solving High-dimensional Many-objective Green Flexible Job Shop Scheduling Problem[J]. Journal of System Simulation, 2024, 36(10): 2314-2329.

Figures/Tables 18

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Table 1

Values of NSGA-III-TV's relevant parameters vary across different test cases

参数	MK01~MK10	实例1、2
r/ $α c i$ / $α m i$ $α$ / $δ r$	4/0.18/0.11/0.01/0.05
$s 1$	[9, 9, 14, 14, 14, 20, 20, 22, 25, 25]	9、9
$c 1$	[0.7,0.7, 0.7,0.7, 0.7,0.7, 0.7,0.7,0.75,0.75]	0.7、0.7

Table 1

Fig. 8

Table 2

Comparison of Results for Test Cases MK01 to MK10

算例 (n×m)	目标函数	NSGA-III-TV	NSGA-II	NSGA-III	NIGA^[16]
MK01 (10×6)	$F 1$	132.84	165.23	162.77	—
	$F 2$	42	44	42	40
	$F 3$	156	159	164	165
	$F 4$	0	0	0	—
MK02 (10×6)	$F 1$	120.46	137.72	148.63	—
	$F 2$	28	31	29	28
	$F 3$	141	155	148	146
	$F 4$	0	0	0	—
MK03 (15×8)	$F 1$	519.86	580.60	581.57	—
	$F 2$	204	204	204	204
	$F 3$	817	909	882	861
	$F 4$	0	28	22	—
MK04 (15×8)	$F 1$	264.06	276.19	274.74	—
	$F 2$	70	78	74	65
	$F 3$	344	347	349	354
	$F 4$	0	5	0	—
MK05 (15×4)	$F 1$	441.54	446	446.87	—
	$F 2$	180	193	183	177
	$F 3$	672	676	678	682
	$F 4$	805	874	763	—
MK06 (10×15)	$F 1$	385.25	406.96	402.28	—
	$F 2$	75	85	80	72
	$F 3$	369	410	371	375
	$F 4$	0	0	0	—
MK07 (20×5)	$F 1$	403.88	420.68	419.04	—
	$F 2$	150	154	148	145
	$F 3$	645	686	662	683
	$F 4$	359	401	344	—
MK08 (20×10)	$F 1$	1 255.75	1 293.16	1 283	—
	$F 2$	523	551	524	523
	$F 3$	2 512	2 531	2 544	2 524
	$F 4$	2 775	3 133	2 898	—
MK09 (20×10)	$F 1$	1 157.22	1 150.7	1 127.6	—
	$F 2$	359	368	346	322
	$F 3$	2 264	2 352	2 352	2 275
	$F 4$	131	392	162	—
MK10 (20×15)	$F 1$	964.68	1 019.02	997.28	—
	$F 2$	286	296	276	232
	$F 3$	1 862	1 996	1 918	1 933
	$F 4$	0	0	0	—

Table 2

Table 3

Table 4

Fig. 9

Fig. 10

Table 5

Comparison of results for algorithm solutions on case study Ⅰ

算法	[N,g_en]	$F 1$ ( $k W · h$ )	$F 2$ /min	$F 3$ /min
NSGA-II	[100,100]	153.11	78	366
	[200,100]	149.75	71	365
	[100,200]	153.88	69	372
NSGA-III	[100,100]	152.63	74	363
	[200,100]	148.88	68	364
	[100,200]	148.53	68	366
NSGA-III-TV	[100,100]	137.58	67	363
	[200,100]	134.77	68	362
	[100,200]	136.99	68	363
INSGA-II	—	160.15	68	363

Table 5

Table 6

Comparison of results for algorithm solutions on case study Ⅱ

算法	$F 1 (W ⋅ s)$	$F 2 / s$	$F 3 / s$
MOMBO^[15]	364 681.82	53.42	178.5
NSGA-II	365 097.75	53.34	181.3
NSGA-III	371 005.84	53.42	176.8
NSGA-III-TV	356 152.68	53.42	177.8

Table 6

Fig. 11

Fig. 12

References 17

1	张朝阳, 徐莉萍, 李健, 等. 基于改进狼群算法的柔性作业车间调度研究[J]. 系统仿真学报, 2023, 35(3): 534-543.
	Zhang Chaoyang, Xu Liping, Li Jian, et al. Flexible Job-shop Scheduling Problem Based on Improved Wolf Pack Algorithm[J]. Journal of System Simulation, 2023, 35(3): 534-543.
2	张国辉, 高亮, 李培根, 等. 改进遗传算法求解柔性作业车间调度问题[J]. 机械工程学报, 2009, 45(7): 145-151.
	Zhang Guohui, Gao Liang, Li Peigen, et al. Improved Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2009, 45(7): 145-151.
3	陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853.
	Chen Kui, Bi Li. Research on FJSP of Improved Particle Swarm Optimization Algorithm Considering Transportation Time[J]. Journal of System Simulation, 2021, 33(4): 845-853.
4	陈广锋, 韩玮. 基于最小负荷初始化的改进遗传算法求解柔性作业车间调度问题[J]. 信息与控制, 2021, 50(3): 374-384.
	Chen Guangfeng, Han Wei. Improved Genetic Algorithm Based on Minimum-load Initialization to Solve Flexible Job-shop Scheduing Problem[J]. Information and Control, 2021, 50(3): 374-384.
5	乔东平, 柏文通, 文笑雨, 等. 基于关联规则的作业车间调度问题改进遗传算法研究[J]. 河南理工大学学报(自然科学版), 2022, 41(2): 138-148.
	Qiao Dongping, Bai Wentong, Wen Xiaoyu, et al. Research on Improved Genetic Algorithm for Job-shop Scheduling Problem Based on Association Rules[J]. Journal of Henan Polytechnic University(Natural Science), 2022, 41(2): 138-148.
6	姜一啸, 吉卫喜, 何鑫, 等. 基于改进非支配排序遗传算法的多目标柔性作业车间低碳调度[J]. 中国机械工程, 2022, 33(21): 2564-2577.
	Jiang Yixiao, Ji Weixi, He Xin, et al. Low-carbon Scheduling of Multi-objective Flexible Job-shop Based on Improved NSGA-Ⅱ[J]. China Mechanical Engineering, 2022, 33(21): 2564-2577.
7	王家海, 李营力, 刘铮玮, 等. 柔性作业车间调度的精确邻域结构混合进化算法[J]. 同济大学学报(自然科学版), 2021, 49(3): 440-448.
	Wang Jiahai, Li Yingli, Liu Zhengwei, et al. Evolutionary Algorithm with Precise Neighborhood Structure for Flexible Workshop Scheduling[J]. Journal of Tongji University(Natural Science), 2021, 49(3): 440-448.
8	赵诗奎. 求解柔性作业车间调度问题的两级邻域搜索混合算法[J]. 机械工程学报, 2015, 51(14): 175-184.
	Zhao Shikui. Bilevel Neighborhood Search Hybrid Algorithm for the Flexible Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2015, 51(14): 175-184.
9	张超勇. 基于自然启发式算法的作业车间调度问题理论与应用研究[D]. 武汉: 华中科技大学, 2006.
	Zhang Chaoyong. Research on the Shop Scheduling Problem with Naturally-inspired Heuristic Algorithms[D]. Wuhan: Huazhong University of Science and Technology, 2006.
10	黄学文, 陈绍芬, 周阗玉, 等. 求解柔性作业车间调度问题的一种新邻域结构[J]. 系统工程理论与实践, 2021, 41(9): 2367-2378.
	Huang Xuewen, Chen Shaofen, Zhou Tianyu, et al. A New Neighborhood Structure for Solving the Flexible Job-shop Scheduling Problem[J]. Systems Engineering-Theory & Practice, 2021, 41(9): 2367-2378.
11	李瑞, 王凌, 龚文引. 知识驱动的模因算法求解分布式绿色柔性调度[J]. 华中科技大学学报(自然科学版), 2022, 50(6): 55-60.
	Li Rui, Wang Ling, Gong Wenyin. Knowledge-driven Memetic Algorithm for Distributed Green Flexible Job Shop Scheduling Problem[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2022, 50(6): 55-60.
12	赵诗奎. 柔性作业车间调度的改进邻域结构混合算法[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.
13	Jiang Huimin, Kwong C K, Park W Y, et al. A Multi-Objective PSO Approach of Mining Association Rules for Affective Design Based on Online Customer Reviews[J]. Journal of Engineering Design, 2018, 29(7): 381-403.
14	Tian Ye, Xiang Xiaoshu, Zhang Xingyi, et al. Sampling Reference Points on the Pareto Fronts of Benchmark Multi-objective Optimization Problems[C]//2018 IEEE Congress on Evolutionary Computation (CEC). Piscataway: IEEE, 2018: 1-6.
15	王秋莲, 段星皓. 基于高维多目标候鸟优化算法的柔性作业车间调度[J]. 中国机械工程, 2022, 33(21): 2601-2612.
	Wang Qiulian, Duan Xinghao. Scheduling of Flexible Job Shop Based on High-dimension and Multi-objective Migrating Bird Optimization Algorithm[J]. China Mechanical Engineering, 2022, 33(21): 2601-2612.
16	王玉芳, 葛嘉荣, 缪昇, 等. 一种求解柔性作业车间的改进遗传算法[J]. 重庆理工大学学报(自然科学), 2021, 35(9): 152-159.
	Wang Yufang, Ge Jiarong, Miao Sheng, et al. An Improve Genetic Algorithm for Solving Flexible Job Shop Scheduling Problem[J]. Journal of Chongqing University of Technology(Natural Science), 2021, 35(9): 152-159.
17	李丹, 向凤红, 毛剑琳. 基于INSGA-Ⅱ高维目标柔性作业车间调度的优化[J]. 重庆邮电大学学报(自然科学版), 2022, 34(2): 341-348.
	Li Dan, Xiang Fenghong, Mao Jianlin. Many-objective Flexible Job Shop Scheduling Optimization Based on INSGA-Ⅱ[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2022, 34(2): 341-348.

算例	NSGA-III-TV	NSGA-II	NSGA-III
MK01	0.004 714 3	0.001 221 0	0.003 376 7
MK02	0.005 628 3	0.001 593 5	0.006 716 0
MK03	0.004 730 7	0.000 941 3	0.004 175 5
MK04	0.007 508 0	0.002 501 3	0.006 389 0
MK05	0.002 045 0	0.000 214 0	0.001 228 0
MK06	0.010 528 0	0.001 351 0	0.005 678 0
MK07	0.003 179 0	0.000 604 3	0.003 127 8
MK08	0.001 012 3	0.000 255 3	0.000 414 5
MK09	0.006 197 7	0.000 203 0	0.003 002 5
MK10	0.007 706 3	0.001 218 7	0.002 040 0

算例	NSGA-III-TV	NSGA-III-TA	NSGA-III-VNS
MK01	0.004 714 3	0.003 210 6	0.003 749 6
MK02	0.005 628 3	0.004 322 4	0.004 741 8
MK03	0.004 730 7	0.004 465 0	0.004 476 0
MK04	0.007 508 0	0.007 572 7	0.007 658 7
MK05	0.002 045 0	0.001 659 3	0.002 624 0
MK06	0.010 528 0	0.010 428 0	0.008 692 0
MK07	0.003 179 0	0.003 229 0	0.003 962 7
MK08	0.001 012 3	0.001 001 6	0.001 004 0
MK09	0.006 197 7	0.006 727 8	0.006 270 3
MK10	0.007 706 3	0.004 154 3	0.005 553 7

[1]	Tengfei Zhang, Rong Hu, Bin Qian, Lü Yang. Learning Variable Neighborhood Search Algorithm for Transportation-assembly Collaborative Optimization Problem [J]. Journal of System Simulation, 2023, 35(6): 1260-1277.
[2]	Jiaying Yu, Hongli Zhang, Yingchao Dong. Research on No-Wait Flow Shop Scheduling Based on Discrete State Transition Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1034-1045.
[3]	Kaiqing Zhang, Qichun Ji. Research on Multi-depot Half-open Vehicle Routing Problem with Time-varying Speed [J]. Journal of System Simulation, 2022, 34(4): 836-846.
[4]	Weiquan Wang, Ding Ding, Shuyan Cao. Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem [J]. Journal of System Simulation, 2022, 34(4): 910-919.
[5]	Mao Liheng, Deng Qing, Liu Rouni, Kong Xianglong. CPM-GA for Multi-satellite and Multi-task Simulation Scheduling [J]. Journal of System Simulation, 2021, 33(1): 205-214.
[6]	Tian Na, Ji Zhicheng. Improved Quantum-behaved Particle Swarm Optimization for Solving Multi-objective Flexible Job-Shop Scheduling Problems [J]. Journal of System Simulation, 2015, 27(12): 2948-2957.