改进混合优化算法求解多目标IPPS问题

doi:10.16182/j.issn1004731x.joss.24-0031

摘要/Abstract

摘要：

针对多目标工艺规划与车间调度集成问题（multi-objective integrated process planning and scheduling，MOIPPS），以最小化完工时间和生产能耗最低为优化目标，提出了一种考虑全局和局部最优的改进混合优化算法。通过分析集成系统工艺设计和生产调度两个问题的区别与联系，搭建了多目标问题模型和解决框架。针对两阶段集成问题提出混合优化算法，对工艺阶段采用全局搜索算法，为集成系统提供多种工艺加工方案，保证集成算法的全局搜索性能；针对调度阶段设计一种改进禁忌搜索算法，通过交叉与随机抽样扩大解的分布范围，使用邻域禁忌搜索使得算法快速收敛，并采用Pareto非支配排序获得全局最优解。实验对比分析，验证了所提算法在求解多目标工艺规划与车间调度集成问题的高效性和稳定性。

关键词: 集成系统, 工艺规划与车间调度, 混合算法, 多目标优化, 节能减排

Abstract:

For the problem of multi-objective integrated process planning and scheduling (MOIPPS), an improved hybrid optimization algorithm considering global and local optimum is proposed to optimize two objectives about minimum makespan and energy consumption. A multi-objective problem model and solution framework are established by analyzing the difference and connection between process planning and scheduling in integrated system. A hybrid optimization algorithm is proposed for the two-stage integration problem. In the process planning stage, global search algorithm is employed to provide a variety of process schemes for the integrated system and to ensure the global search performance of the integrated algorithm. With regard to the scheduling stage, an improved tabu search algorithm is proposed, of which, crossover and random sampling operator is aimed at expanding the solution searching region and neighborhood tabu search is promoting the algorithm to converge instantly respectively. Pareto non-dominated sorting is employed to acquire the global optimal solution. Through contrastive analysis on diverse experiment results, the efficiency and consistency of the proposed algorithm is verified in solving multi-objective integrated process planning and scheduling problems.

Key words: integrated system, process planning and scheduling, hybrid algorithm, multi-objective optimal, energy conservation and emission reduction

中图分类号:

TP391.9

顾文斌,卿洁瑕,方杰等 . 改进混合优化算法求解多目标IPPS问题[J]. 系统仿真学报, 2025, 37(5): 1197-1209.

Gu Wenbin,Qing Jiexia,Fang Jie,et al . Improved Hybrid Optimization Algorithm for Multi-objective IPPS Problem[J]. Journal of System Simulation, 2025, 37(5): 1197-1209.

图/表 18

表1

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

表2

表3

表4

不同规模问题工件信息

问题	规模(工件数 $n$ ×机器数 $m$ )	工件序号
1	6×5	job1~6
2	6×5	job2~7
3	6×5	job3~8
4	6×5	job9~14
5	6×5	job10~15
6	6×5	job11~16
7	6×5	job1,3,6,8,10,15
8	6×5	job2,4,5,7,11,14
9	6×5	job2,6,9,12,13,16
10	10×5	job1~5,9~13
11	10×5	job4~8,12~16
12	10×5	job1,3,5,7~10,12,14,16
13	10×5	job1~9,13
14	10×5	job7~16
15	15×10	job1~15
16	15×10	job1~14,16
17	15×10	job1~11,13~16
18	16×10	job1~16

表4

图11

表5

表6

图12

参考文献 24

1	李磊, 韩洪伟, 蒋琪. 美决策中心战概念研究[J]. 战术导弹技术, 2021(1): 34-37, 120.
	Li Lei, Han Hongwei, Jiang Qi. Analysis of the Concept of U.S. Decision-centric Warfare[J]. Tactical Missile Technology, 2021(1): 34-37, 120.
2	李磊, 沈剑, 蒋琪. 美智库«马赛克战: 利用人工智能和自主系统实施决策中心战»解读[J]. 飞航导弹, 2020(11): 1-3.
3	邓连印, 侯宇葵, 申志强. 美军新型作战概念发展分析与启示[J]. 航天电子对抗, 2020, 36(5): 18-23.
	Deng Lianyin, Hou Yukui, Shen Zhiqiang. Analysis and Enlightenment on the Development of New Combat Concept in the US Army[J]. Aerospace Electronic Warfare, 2020, 36(5): 18-23.
4	左毅, 郑少秋, 袁翔, 等. 破解马赛克战之系统发展思考[J]. 指挥信息系统与技术, 2020, 11(6): 1-7.
	Zuo Yi, Zheng Shaoqiu, Yuan Xiang, et al. System Development Consideration for Cracking Mosaic Warfare[J]. Command Information System and Technology, 2020, 11(6): 1-7.
5	杜燕波. 决胜无形空间: 美军在行动[J]. 军事文摘, 2021(1): 33-37.
6	高松, 孙媛, 段哲, 等. 基于马赛克战的电子对抗装备体系构建研究[J]. 舰船电子工程, 2021, 41(9): 78-82.
	Gao Song, Sun Yuan, Duan Zhe, et al. Research on Electronic Countermeasure Equipment System Construction Based on Mosaic Warfare[J]. Ship Electronic Engineering, 2021, 41(9): 78-82.
7	程翔. 人工智能时代马赛克战致胜机理研究[J]. 舰船电子对抗, 2020, 43(2): 12-15, 25.
	Cheng Xiang. Research into the Winning Mechanism of Mosaic Warfare in AI Era[J]. Shipboard Electronic Countermeasure, 2020, 43(2): 12-15, 25.
8	郭建国, 周敏, 郭宗易, 等. 马赛克战下的协同作战技术[J]. 航空兵器, 2021, 28(1): 1-5.
	Guo Jianguo, Zhou Min, Guo Zongyi, et al. Cooperative Combat Technology Under Mosaic Warfare[J]. Aero Weaponry, 2021, 28(1): 1-5.
9	姜福涛, 黄学军. "马赛克战"浅析[J]. 航天电子对抗, 2020, 36(2): 60-64.
	Jiang Futao, Huang Xuejun. Analysis of Mosaic Warfare[J]. Aerospace Electronic Warfare, 2020, 36(2): 60-64.
10	顾灏冰, 田少华, 周丹发, 等. 基于OODA环的马赛克战理念及关键技术分析[J]. 空天防御, 2021, 4(3): 65-69.
	Gu Haobing, Tian Shaohua, Zhou Danfa, et al. Analysis of Mosaic Warfare Concept and Key Technologies Based on OODA Loop[J]. Air & Space Defense, 2021, 4(3): 65-69.
11	郭渊斐, 徐文龙, 赵玉亮. 美军"马赛克战"的发展及对我军智能化建设的启示[J]. 海军工程大学学报(综合版), 2020, 17(1): 24-28.
	Guo Yuanfei, Xu Wenlong, Zhao Yuliang. Expectation of Development of US Army "Mosaic Warfare" and Its Enlightenment[J]. Journal of Naval University of Engineering(Comprehensive Edition), 2020, 17(1): 24-28.
12	李强, 王飞跃. 马赛克战概念分析和未来陆战场网信体系及其智能对抗研究[J]. 指挥与控制学报, 2020, 6(2): 87-93.
	Li Qiang, Wang Feiyue. Conceptual Analysis of Mosaic Warfare and Systems of Network-information Systems for Intelligent Countermeasures and Future Land Battles[J]. Journal of Command and Control, 2020, 6(2): 87-93.
13	王星宇, 王娜, 黎开颜, 等. "马赛克战"作战概念分析及其对未来战争形态的影响[J]. 国防科技, 2022, 43(4): 87-92.
	Wang Xingyu, Wang Na, Li Kaiyan, et al. An Analysis of the Mosaic Warfare Operational Concept and Its Influence on Future Warfare Forms[J]. National Defense Technology, 2022, 43(4): 87-92.
14	孙盛智, 刘玉, 盛碧琦, 等. "马赛克"战运行机制及制胜机理研究[J]. 指挥控制与仿真, 2023, 45(2): 150-154.
	Sun Shengzhi, Liu Yu, Sheng Biqi, et al. Research on the Operation Mechanism and Winning Mechanism of Mosaic Warfare[J]. Command Control & Simulation, 2023, 45(2): 150-154.
15	陈明德, 和欣. 马赛克战对指挥与通信领域的启示分析[J]. 通信技术, 2022, 55(10): 1284-1293.
	Chen Mingde, He Xin. Enlightenment Analysis of Mosaic Warfare for the Field of Command and Communications[J]. Communications Technology, 2022, 55(10): 1284-1293.
16	王芳, 饶运清, 唐秋华, 等. 多目标决策下Pareto非支配解的快速构造方法[J]. 系统工程理论与实践, 2016, 36(02): 454-463.
	Wang Fang, Rao Yunqing, Tang Qiuhuaet al. Fast Construction Method of Pareto Non-dominated Solution Under Multi-objective Decision[J]. Systems Engineering Theory & Practice, 2016, 36(02): 454-463.
17	Kim Y K, park K, Ko J. A Symbiotic Evolutionary Algorithm for the Integration of Process Planning and Job Shop Scheduling[J]. Computers＆Operations Research, 2003, 30 (8): 1151-1171.
18	李新宇. 工艺规划与车间调度集成问题的求解方法研究[D]. 武汉: 华中科技大学, 2009: 58.
	Li Xinyu. Research on Solving Method of Integrated Process Planning and Scheduling[D]. Wuhan: Huazhong University of Science and Technology, 2009: 58.
19	Li X, Shao X, Gao L, et al. An Effective Hybrid Algorithm for Integrated Process Planning and Scheduling[J]. International Journal of Production Economics, 2010, 126(2).
20	文笑雨, 罗国富, 李浩, 等. 两阶段混合算法求解集成工艺规划与调度问题[J]. 中国机械工程, 2018, 29(22): 2716-2724+2732.
	Wen Xiaoyu, Luo Guofu, Li Haoet al. Two-stage Hybrid Algorithm for Integrated Process Planning and Scheduling Problem[J]. China Mechanical Engineering, 2018, 29(22): 2716-2724+2732.
21	Wen X Y, Lian X N, Qian Y J, et al. Dynamic Scheduling Method for Integrated Process Planning and Scheduling Problem with Machine Fault[J], Robotics and Computer-Integrated Manufacturing, 2022, 77: 102334.
22	Zhang X., Liao Z., Ma L.et al. Hierarchical Multistrategy Genetic Algorithm for Integrated Process Planning and Scheduling[J]. Journal of Intelligent Manufacturing, 2022, 33(1): 223–246.
23	周辉仁, 唐万生, 魏颖辉. 柔性Flow-Shop调度的遗传算法优化[J]. 计算机工程与应用, 2009, 45(30): 224-226, 233.
	Zhou Huiren, Tang Wansheng, Wei Yinghui. Genetic Algorithm Optimization of Flexible Flow-Shop Scheduling[J]. Computer Engineering and Applications, 2009, 45(30): 224-226, 233.
24	顾文斌, 李育鑫, 钱煜晖, 等. 基于激素调节机制IPSO算法的相同并行机混合流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(10): 2858-2871.
	Gu Wenbin, Li Yuxin, Qian Yuhuiet al. Hybrid Flow Job Shop Scheduling Problem of Identical Parallel Machines Based on Hormone Regulation Mechanism IPSO Algorithm[J]. Computer Integrated Manufacturing System, 2021, 27(10): 2858-2871.

符号	描述
N	工件总数
M	机器总数
I	工件索引
J	待加工工序索引
K	机器索引
m_k	第k个机器
O_ij	工件i的第j个加工工序
H_i	工件i总加工工序数
f_i	工件i的加工特征数
p_ix	加工特征f_i 的可选工艺方案数(x = 1, 2, …, f_i )
q_ixy	工艺方案p_ix 所需加工的工序数(y = 1, 2, …, p_ix )
SH_i	工件i的加工工艺路线确认后待加工的工序数
M_ij	工序O_ij 的可加工机器合集
t_ijk	工序O_ij 在机器m_k 上的加工时间
P_ijk	工序O_ij 在机器m_k 上的加工功率
C_ij	工序O_ij 的完工时间
P_f^k	机器m_k 的待机功率
P_a	车间辅助功率
X_ijk	1，如果O_ij 被安排在机器m_k 上；否则，0
Y_ijpq	1，如果O_ij 是O_pq 的上一道工序；0，如果O_ij 是O_pq 的下一道工序

参数名称	取值
集成系统最大迭代次数I_bm	200
工艺阶段迭代次数I_ps	与I_bm同步
工艺阶段种群规模G_p	100
调度阶段最大迭代次数I_s	50
调度阶段种群规模G_s	50
新个体容量V_n	20
禁忌最大迭代次数I_ts	20
禁忌长度L_ts	randi(5,9)
邻域解个数Ca	10

问题	工件数	SEA	GATS	HA	ICA	THA	SMGAVNS	HMS-GA	IHOA
1	6	428	427	483	427	427	427	427	427
2	6	343	343	383	343	343	343	343	301
3	6	347	345	386	345	344	344	344	344
4	6	306	306	328	306	306	306	306	301
5	6	319	319	348	319	319	316	318	304
6	6	438	427	506	435	427	427	427	427
7	6	372	372	386	372	372	372	372	372
8	6	343	343	376	343	348	351	342	320
9	6	428	427	507	427	427	427	427	427
10	9	443	427	504	440	427	427	427	427
11	9	369	369	413	367	365	350	349	344
12	9	328	326	361	327	321	317	321	301
13	9	452	428	505	457	434	427	428	428
14	9	381	380	423	390	385	393	374	372
15	9	434	427	496	432	427	427	427	427
16	12	454	435	521	466	430	437	428	434
17	12	431	423	474	443	418	414	367	362
18	12	379	349	417	384	353	358	335	331
19	12	490	474	550	490	470	462	434	428
20	12	447	432	473	440	431	419	390	386
21	12	477	427	525	466	430	427	427	427
22	15	534	513	560	529	489	476	443	444
23	15	498	470	533	495	453	440	415	415
24	18	587	539	607	577	511	493	475	475

目标值	最大完工时间/min	能耗/kW
最高	358.00	68.73
最低	355.00	66.90
平均	355.97	67.65

优化目标		单目标值
优化目标		完工时间/min	能耗/kW
完工时间最小	最高	358	83.10
	最低	354	83.13
	平均	355.23	82.55
能耗最小	最高	366	69.44
	最低	362	67.72
	平均	365	68.53