考虑动态预维护与绿色调度的协同优化问题

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

摘要/Abstract

摘要：

针对传统柔性作业车间调度问题，将机器动态预维护与绿色调度进行联合优化，以最小化最大完工时间、总碳排放量、总成本为优化目标建立集成优化模型。提出了一种改进的NSGA-II算法用于求解该模型，采用基于工序、机器和预维护的三层编码方式，设计了考虑工序分配、机器选择以及机器预维护策略的同步解码方案；改进了精英保留策略，设计了随着代数变化的自适应交叉变异函数以及基于邻域搜索的变异算子。实验验证了改进算法在求解不同规模调度问题的有效性，所提的动态预维护策略较其他维护策略能更有效地求解预维护与柔性作业车间绿色调度协同优化问题。

关键词: 预维护, 绿色调度, INSGA-II, 协同优化, 柔性作业车间

Abstract:

For the traditional flexible job shop scheduling problem, a joint optimization of machine dynamic pre-maintenance and green scheduling is considered to establish an integrated optimization model with the optimization objectives of minimizing maximum completion time, total carbon emissions, and total cost. An improved NSGA-II algorithm is proposed to solve the model. A three-layer encoding method based on process, machine, and pre maintenance is adopted to design a one-step decoding scheme that considers process allocation, machine selection, and machine pre-maintenance strategies. The algorithm improves the elitist retention strategy, designs an adaptive crossover mutation function with algebraic changes, and a mutation operator based on neighborhood search. The experiment validates the effectiveness of the improved algorithm in solving scheduling problems of different scales, the proposed dynamic pre-maintenance strategy can more effectively solve the collaborative optimization problem of pre-maintenance and flexible job shop green scheduling compared to other maintenance strategies.

Key words: pre-maintenance, green scheduling, INSGA-II, collaborative optimization, flexible job shop

中图分类号:

TP391.9

江雨燕,马宁,李艳等 . 考虑动态预维护与绿色调度的协同优化问题[J]. 系统仿真学报, 2025, 37(2): 362-378.

Jiang Yuyan,Ma Ning,Li Yan,et al . Collaborative Optimization Problem of Dynamic Pre-maintenance and Green Scheduling[J]. Journal of System Simulation, 2025, 37(2): 362-378.

图/表 28

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

表1

Brandimarte算例结果对比

算例	N×M	HGWO		Heuristic		IDE		ALPS-GA		INSGA-Ⅱ
算例	N×M	Best	$R P D$	Best	$R P D$	Best	$R P D$	Best	$R P D$	Best	$R P D$
平均值			3.26		4.41		2.18		5.29		0.93
MK01	10×6	40	0	42	5	40	0	40	0	40	0
MK02	10×6	29	3.57	28	0	28	0	29	3.57	28	0
MK03	15×8	204	0	204	0	204	0	207	1.47	204	0
MK04	15×8	65	0	75	15.38	71	9.23	65	0	66	1.54
MK05	15×4	175	0	179	2.29	179	2.29	181	3.43	175	0
MK06	10×15	79	14.49	69	0	73	5.8	81	17.39	72	4.35
MK07	20×5	149	2.05	149	2.05	146	0	149	2.05	146	0
MK08	20×10	523	0	555	6.12	528	0.96	555	6.12	523	0
MK09	20×10	325	4.84	342	10.32	321	3.55	342	10.32	310	0
MK10	20×15	253	7.66	242	2.98	235	0	255	8.51	243	3.4

表1

图13

图14

表2

图15

表3

机器加工参数

机器	$p k e$ /kW	$i k e$ /kW	$C k r$ /(元/h)
$M 1$	15	2.35	18
$M 2$	20	3.75	22
$M 3$	5	0.65	7
$M 4$	13	1.63	9
$M 5$	10	1.31	8
$M 6$	8.5	0.93	11
$M 7$	6.5	0.82	5
$M 8$	11	1.36	13
$M 9$	20	3.45	16
$M 10$	15	2.82	12

表3

表4

拓展算例对比结果

算例	NSGA-Ⅱ				MOEA/D				本文算法
算例	$f 1$	$f 2$	$f 3$	加权值	$f 1$	$f 2$	$f 3$	加权值	$f 1$	$f 2$	$f 3$	加权值
Date-1	26	23.26	16.23	21.98	16	17.36	13.67	15.84	15	16.03	13.38	14.93
Date-2	10	10.59	7.85	9.59	9	9.41	7.33	8.66	8	9.18	7.75	8.40
Date-3	15	18.85	17.33	17.24	18	20.35	17.22	18.70	14	18.29	17.32	16.71
Date-4	35	35.18	29.80	33.51	32	34.47	30.40	32.51	30	32.98	29.35	31.00
Date-5	208	202.59	158.72	191.05	206	203.92	154.97	189.86	204	197.59	155.57	186.91
Date-6	337	506.41	458.48	441.21	344	498.38	456.92	439.63	332	492.84	457.9	434.11

表4

图16

表5

图17

图18

表6

机器预维护相关参数

机器	$η$	$m$	$C k f$ /(元/h)	$周期 / m i n$	$T k v p m / m i n$
1	100	1.6	110	32	7
2	105	1.6	150	33	6
3	102	1.6	105	32	6
4	140	1.8	65	35	8
5	110	1.4	160	30	5
6	95	1.6	70	30	5
7	90	2.0	60	32	7
8	90	1.8	80	32	8

表6

表7

不同维护策略结果对比

维护策略	$f 1 / m i n$	$f 2 / k g$	$f 3 / 元$	PM次数	PM成本/元
动态维护	82	98.7	177.57	9	91.33
右移维护	94	102.57	188.83	10	104.67
周期维护	93	103.59	253.9	16	167.67

表7

图19

图20

图21

参考文献 28

1	Liu Ying, Dong Haibo, Lohse N, et al. An Investigation into Minimising Total Energy Consumption and Total Weighted Tardiness in Job Shops[J]. Journal of Cleaner Production, 2014, 65: 87-96.
2	刘彩洁, 徐志涛, 张钦, 等. 分时电价下基于NSGA-Ⅱ的柔性作业车间绿色调度[J]. 中国机械工程, 2020, 31(5): 576-585.
	Liu Caijie, Xu Zhitao, Zhang Qin, et al. Green Scheduling of Flexible Job Shops Based on NSGA-Ⅱ Under TOU Power Price[J]. China Mechanical Engineering, 2020, 31(5): 576-585.
3	张洪亮, 丁仁曼, 徐公杰. 考虑区间工时的多目标柔性作业车间节能调度[J]. 系统仿真学报, 2022, 34(9): 1976-1987.
	Zhang Hongliang, Ding Renman, Xu Gongjie. Energy-efficient Scheduling of Multi-objective Flexible Job Shop Considering Interval Processing Time[J]. Journal of System Simulation, 2022, 34(9): 1976-1987.
4	张朝阳, 徐莉萍, 李健, 等. 基于改进狼群算法的柔性作业车间调度研究[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.
5	Wu Xiuli, Sun Yangjun. A Green Scheduling Algorithm for Flexible Job Shop with Energy-saving Measures[J]. Journal of Cleaner Production, 2018, 172: 3249-3264.
6	Caldeira Rylan H, Gnanavelbabu A, Vaidyanathan T. An Effective Backtracking Search Algorithm for Multi-objective Flexible Job Shop Scheduling Considering New Job Arrivals and Energy Consumption[J]. Computers & Industrial Engineering, 2020, 149: 106863.
7	Sheikhalishahi M, Eskandari N, Mashayekhi A, et al. Multi-objective Open Shop Scheduling by Considering Human Error and Preventive Maintenance[J]. Applied Mathematical Modelling, 2019, 67: 573-587.
8	吴秀丽, 张志强, 赵宁, 等. 超启发式文化基因算法优化生产与预维修集成调度问题[J]. 计算机集成制造系统, 2019, 25(8): 1885-1896.
	Wu Xiuli, Zhang Zhiqiang, Zhao Ning, et al. Production Scheduling and Preventive Maintenance Plan Optimization with Hyper-heuristics Memetic Algorithm[J]. Computer Integrated Manufacturing Systems, 2019, 25(8): 1885-1896.
9	宋文家, 张超勇, 尹勇, 等. 基于多目标混合殖民竞争算法的设备维护与车间调度集成优化[J]. 中国机械工程, 2015, 26(11): 1478-1487.
	Song Wenjia, Zhang Chaoyong, Yin Yong, et al. Integrated Optimization of Equipment Maintenance and Shop Scheduling Problem Based on Multi-objective Hybrid Imperialist Competitive Algorithm[J]. China Mechanical Engineering, 2015, 26(11): 1478-1487.
10	刘琼, 刘嘉豪, 刘佳良. 基于改进人工蜂群算法的预防性维修与柔性作业车间成组调度集成优化[J]. 机械工程学报, 2023, 59(12): 89-96.
	Liu Qiong, Liu Jiahao, Liu Jialiang. Integrated Optimization of Preventive Maintenance and Flexible Job Shop Group Scheduling Based on an ABC-AN Algorithm[J]. Journal of Mechanical Engineering, 2023, 59(12): 89-96.
11	Li Ruiqiu, Ma Huimin. Integrating Preventive Maintenance Planning and Production Scheduling Under Reentrant Job Shop[J]. Mathematical Problems in Engineering, 2017(575): 1-9.
12	Mao Jiayang, Pan Quanke, Miao Zhonghua, et al. An Effective Multi-start Iterated Greedy Algorithm to Minimize Makespan for the Distributed Permutation Flowshop Scheduling Problem with Preventive Maintenance[J]. Expert Systems with Applications, 2021, 169: 114495.
13	董君, 叶春明. 半导体晶圆节能分布式制造与预维护联合优化[J]. 系统仿真学报, 2022, 34(3): 584-602.
	Dong Jun, Ye Chunming. Research on Joint Optimization of Energy-saving Distributed Manufacturing and Preventive Maintenance for Semiconductor Wafers[J]. Journal of System Simulation, 2022, 34(3): 584-602.
14	Lu Zhiqiang, Zhang Yuejun, Han Xiaole. Integrating Run-based Preventive Maintenance into the Capacitated Lot Sizing Problem with Reliability Constraint[J]. International Journal of Production Research, 2013, 51(5): 1379-1391.
15	刘繁茂. 面向故障过程的多设备可靠性分析与维修决策[D]. 武汉: 华中科技大学, 2010.
	Liu Fanmao. Reliability Analysis and Maintenance Decision-making Method of Multi-machine for Failure Process[D]. Wuhan: Huazhong University of Science and Technology, 2010.
16	张国辉, 高亮, 李培根, 等. 改进遗传算法求解柔性作业车间调度问题[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.
17	姜天华. 混合灰狼优化算法求解柔性作业车间调度问题[J]. 控制与决策, 2018, 33(3): 503-508.
	Jiang Tianhua. Flexible Job Shop Scheduling Problem with Hybrid Grey Wolf Optimization Algorithm[J]. Control and Decision, 2018, 33(3): 503-508.
18	Ziaee Mohsen. A Heuristic Algorithm for Solving Flexible Job Shop Scheduling Problem[J]. The International Journal of Advanced Manufacturing Technology, 2014, 71(1): 519-528.
19	Sriboonchandr Prasert, Kriengkorakot Nuchsara, Kriengkorakot Preecha. Improved Differential Evolution Algorithm for Flexible Job Shop Scheduling Problems[J]. Mathematical and Computational Applications, 2019, 24(3): 80.
20	江厚民, 李少波, 王巾侠, 等. ALPS-GA求解柔性作业车间调度问题[J]. 计算机仿真, 2019, 36(5): 390-394.
	Jiang Houmin, Li Shaobo, Wang Jinxia, et al. Solving Flexible Job-shop Scheduling Problem Using ALPS-GA[J]. Computer Simulation, 2019, 36(5): 390-394.
21	Huang Xiabao, Guan Zailin, Yang Lixi. An Effective Hybrid Algorithm for Multi-objective Flexible Job-shop Scheduling Problem[J]. Advances in Mechanical Engineering, 2018, 10(9): 1687814018801442.
22	Alzahrani Jaber S. Multi-objective Job Shop Scheduling Using Pre-emptive Constraint Procedure[J]. American Journal of Modeling and Optimization, 2019, 7(1): 8-13.
23	曹磊, 叶春明, 黄霞. 基于员工学习行为的多目标柔性车间调度[J]. 计算机集成制造系统, 2018, 24(8): 2023-2034.
	Cao Lei, Ye Chunming, Huang Xia. Multi-objective Flexible Job-shop Scheduling Based on Learning Effect[J]. Computer Integrated Manufacturing Systems, 2018, 24(8): 2023-2034.
24	Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
25	Zhang Qingfu, Li Hui. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.
26	Czyzżak Piotr, Jaszkiewicz Adrezej. Pareto Simulated Annealing——A Metaheuristic Technique for Multiple-objective Combinatorial Optimization[J]. Journal of Multi-Criteria Decision Analysis, 1998, 7(1): 34-47.
27	Zheng Xiaolong, Wang Ling. A Collaborative Multiobjective Fruit Fly Optimization Algorithm for the Resource Constrained Unrelated Parallel Machine Green Scheduling Problem[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 48(5): 790-800.
28	张超勇, 董星, 王晓娟, 等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]. 机械工程学报, 2010, 46(11): 156-164.
	Zhang Chaoyong, Dong Xing, Wang Xiaojuan, et al. Improved NSGA-Ⅱ for the Multi-objective Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2010, 46(11): 156-164.

算例	SC(A,B)	SC(B,A)	SC(A,C)	SC(C,A)	IGD(A)	IGD(B)	IGD(C)
Date-1	0.25	0.067	0.667	0.067	0.138	1.532	1.010
Date-2	0.714	0	1	0	0.029	0.605	2.009
Date-3	0.8	0	0.429	0.231	0.298	1.284	1.069
Date-4	0.25	0	1	0	0.117	1.310	1.837
Date-5	1	0	0.714	0	0.607	2.669	1.081
Date-6	0.786	0	0.75	0	1.096	5.273	3.195

[1]	蒋权, 魏静萱. 用于动态柔性作业车间调度的实时调度方法[J]. 系统仿真学报, 2024, 36(7): 1609-1620.
[2]	肖鹏, 谢锋, 倪海鸿, 张敏, 汤志荔, 李霓. 多机任务分配与路径规划协同优化法研究[J]. 系统仿真学报, 2024, 36(5): 1141-1151.
[3]	马训德, 毕利, 王俊杰. 基于群体免疫算法的绿色车间调度研究[J]. 系统仿真学报, 2024, 36(11): 2578-2591.
[4]	李健, 李洹坤, 何鹏博, 王化北, 徐莉萍, 何奎. 协同智能体强化学习算法的柔性作业车间调度方法研究[J]. 系统仿真学报, 2024, 36(11): 2699-2711.
[5]	王玉芳, 章殿清, 华晓麟, 姚彬彬, 陈凡. 面向航空结构件的双资源分布式柔性调度研究[J]. 系统仿真学报, 2024, 36(11): 2722-2740.
[6]	徐宜刚, 陈勇, 王宸, 彭运贤. 改进NSGA-III求解高维多目标绿色柔性作业车间调度问题[J]. 系统仿真学报, 2024, 36(10): 2314-2329.
[7]	胥远兴, 张孟健, 王德光. 面向柔性作业车间调度问题的混沌编码量子粒子群优化算法[J]. 系统仿真学报, 2024, 36(10): 2371-2382.
[8]	张腾飞, 胡蓉, 钱斌, 吕阳. 学习型变邻域搜索算法求解运输-装配协同优化问题[J]. 系统仿真学报, 2023, 35(6): 1260-1277.
[9]	张洪亮, 徐静茹, 谈波, 徐公杰. 考虑交货期的双资源柔性作业车间节能调度[J]. 系统仿真学报, 2023, 35(4): 734-746.
[10]	古鹏飞, 张霖, 陈真, 叶俊杰. 基于X语言的起飞场景民机协同设计与仿真一体化方法[J]. 系统仿真学报, 2022, 34(5): 929-943.
[11]	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
[12]	董君, 叶春明. 半导体晶圆节能分布式制造与预维护联合优化[J]. 系统仿真学报, 2022, 34(3): 584-602.
[13]	张洪亮, 丁仁曼, 徐公杰. 考虑区间工时的多目标柔性作业车间节能调度[J]. 系统仿真学报, 2022, 34(09): 1976-1987.
[14]	陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853.
[15]	尤一琛, 王艳, 纪志成. 基于博弈论的柔性作业车间动态调度研究[J]. 系统仿真学报, 2021, 33(11): 2579-2588.