改进NSGA-III求解高维多目标绿色柔性作业车间调度问题

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

系统仿真学报 ›› 2024, Vol. 36 ›› Issue (10): 2314-2329.doi: 10.16182/j.issn1004731x.joss.23-0694

• 论文 • 上一篇

改进NSGA-III求解高维多目标绿色柔性作业车间调度问题

徐宜刚¹, 陈勇¹^,², 王宸¹^,²^,³, 彭运贤⁴

^1.湖北汽车工业学院机械工程学院, 湖北十堰 442000
^2.中国工程科技十堰产业技术研究院, 湖北十堰 442000
^3.上海大学上海市智能制造与机器人重点实验室, 上海 200072
^4.东风专用汽车有限公司, 湖北十堰 442000

收稿日期:2023-06-06 修回日期:2023-08-28 出版日期:2024-10-15 发布日期:2024-10-18
通讯作者: 陈勇
第一作者简介:徐宜刚(2000-)，男，硕士生，研究方向为智能调度。
基金资助:
国家自然科学基金(51475150);湖北省高等学校中青年科技创新团队计划(T20200018)

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

Xu Yigang¹, Chen Yong¹^,², Wang Chen¹^,²^,³, Peng Yunxian⁴

^1.College of Mechanical Engineering, Hubei Institute of Automotive Technology, Shiyan 442000, China
^2.Shiyan Industrial Technology Research Institute of China Engineering Science and Technology, Shiyan 442000, China
^3.Shanghai Key Laboratory of Intelligent Manufacturing and Robotics, Shanghai University, Shanghai 200072, China
^4.Dongfeng Special Purpose Vehicle Co. , Ltd, Shiyan 442000, China

Received:2023-06-06 Revised:2023-08-28 Online:2024-10-15 Published:2024-10-18
Contact: Chen Yong

摘要/Abstract

摘要：

为解决NSGA-III在求解上述模型存在初始解质量差与局部搜索效率低的问题，提出一种改进的NSGA-III(NSGA-III-TV)。基于MSOS编码，分别对OS和MS染色体采取不同混合初始化策略以提高初始解质量；基于关键路径，采用改进N6邻域结构进行邻域搜索，有效缩短完工时间并降低搜索盲目性，同时采用3种有效变异算子扩大算法搜索空间，提高后期收敛能力。结果表明：NSGA-III-TV在求解高维多目标柔性作业车间调度问题上具有较好的性能以及实用性，为企业生产制造车间的智能绿色转型升级提供了有力支持。

关键词: 绿色柔性作业车间调度, 高维多目标优化, 关键路径, 变邻域搜索

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

中图分类号:

TP18

徐宜刚,陈勇,王宸等 . 改进NSGA-III求解高维多目标绿色柔性作业车间调度问题[J]. 系统仿真学报, 2024, 36(10): 2314-2329.

Xu Yigang,Chen Yong,Wang Chen,et al . 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.

图/表 18

图1

图2

图3

图4

图5

图6

图7

表1

NSGA-III-TV相关参数在不同算例上取值

参数	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

表1

图8

表2

求解算例MK01~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	—

表2

表3

表4

图9

图10

表5

算法求解实例Ⅰ结果对比

算法	[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

表5

表6

算法求解实例Ⅱ结果对比

算法	$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

表6

图11

图12

参考文献 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]	张腾飞, 胡蓉, 钱斌, 吕阳. 学习型变邻域搜索算法求解运输-装配协同优化问题[J]. 系统仿真学报, 2023, 35(6): 1260-1277.
[2]	余佳英, 张宏立, 董颖超. 基于离散状态转移算法的无等待流水车间调度研究[J]. 系统仿真学报, 2023, 35(5): 1034-1045.
[3]	范厚明, 咸富山, 王怀奇. 动态需求下考虑订单聚类的外卖配送路径优化[J]. 系统仿真学报, 2023, 35(2): 396-407.
[4]	张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J]. 系统仿真学报, 2022, 34(4): 836-846.
[5]	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
[6]	毛李恒, 邓清, 刘柔妮, 孔祥龙. 针对多星多任务仿真调度的关键路径遗传算法[J]. 系统仿真学报, 2021, 33(1): 205-214.
[7]	田娜, 纪志成. 改进量子粒子群求解多目标柔性作业车间调度[J]. 系统仿真学报, 2015, 27(12): 2948-2957.

改进NSGA-III求解高维多目标绿色柔性作业车间调度问题

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 18

参考文献 17

相关文章 7

编辑推荐

Metrics

本文评价