基于群体免疫算法的绿色车间调度研究

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

摘要/Abstract

摘要：

针对机器具有多转速的绿色柔性作业车间调度问题，以最大完工时间最小化和不同转速下的总能耗最小化为优化目标，构建了多转速下的绿色柔性车间调度模型，提出了一种离散的冠状病毒群体免疫算法（discrete coronavirus herd immunity optimizer，DCHIO）进行求解。针对多转速问题解空间较为庞大的特点，引入了离散化的个体更新方式，提出了一种多尺度联合搜索的种群更新机制以快速、均匀地搜索解空间；设计了动态变异操作以增强算法的种群多样性同时实现自适应调整；通过挖掘当前调度方案的经验知识，提出了基于知识驱动的邻域搜索策略，以同时减小最大完工时间和能源消耗。实验结果表明：所提算法可以有效解决多转速绿色柔性调度问题。

关键词: 绿色调度, 柔性作业车间, 离散冠状病毒群体免疫算法, 多转速机器, 知识驱动邻域搜索

Abstract:

In view of the green flexible job shop scheduling problem where machines have multiple speeds, a green flexible job shop scheduling model under multiple speeds was constructed to minimize the makespan and total energy consumption under different speeds. A discrete coronavirus herd immunity optimizer (DCHIO) was proposed for a solution. A discrete individual updating method was introduced for the relatively large solution space of the multi-speed problem, based on which a population updating mechanism with multi-scale joint search was proposed to search the solution space quickly and uniformly. A dynamic mutation operation was designed to enhance the population diversity of the algorithm while realizing the adaptive tuning. By mining the empirical knowledge of the current scheduling scheme, a knowledge-driven neighborhood search strategy was proposed to simultaneously reduce the makespan and energy consumption. The^{experimental results show that the algorithm proposed in this paper can effectively solve the green flexible scheduling problem under multiple speeds.}

Key words: green scheduling, flexible job shop, discrete coronavirus herd immunity optimizer, multi-speed machines, knowledge-driven neighborhood search

中图分类号:

TP391.9

马训德,毕利,王俊杰 . 基于群体免疫算法的绿色车间调度研究[J]. 系统仿真学报, 2024, 36(11): 2578-2591.

Ma Xunde,Bi Li,Wang Junjie . Research on Green Job Shop Scheduling Based on Herd Immunity Optimizer[J]. Journal of System Simulation, 2024, 36(11): 2578-2591.

图/表 11

表1

模型符号定义

符号	定义
m	机器总数目
n	工件总数目
i,g	工件索引， $i, g ∈ 1,2, ⋯, n$
n_i	工件i包含的工序总数目
j, h	工件i和g的工序索引， $j ∈ 1,2, ⋯, n i$ ， $h ∈ 1,2, ⋯, n g$
k, p	机器的索引， $k, p ∈ 1,2, ⋯, m$
O_ij	工件i的第j道工序
M_ij	工序O_ij的可选机器集合， $M i j ⊆ 1,2, ⋯, m$
O_ijk	工序O_ij的可选机器集合中的机器k， $M i j k ∈ M i j$
T_ijk	工序O_ij在机器k上的标准加工时间
JRt_i	工件i的第一道工序的释放时间
ST_ijk	工序O_ij在机器k上的开始加工时间
FT_ijk	工序 $O i j$ 在机器k上的完工时间
S_ij	O_ij的机器加工档位
$α S i j$	O_ij的机器加工档位所对应的加工时间转化系数
SEE_k	机器k的开机能耗和关机能耗
E_k	机器k的待机能耗
$U P E k S i j$	机器k在转速S_ij下的单位时间加工能耗
$U I E k S i j$	机器k在转速S_ij下的单位时间空载能耗

表1

图1

图2

图3

图4

表2

表3

表4

表5

图5

图6

参考文献 26

1	Gao Kaizhou, Ponnuthurai Nagaratnam Suganthan, Tay Jin Chua, et al. A Two-stage Artificial Bee Colony Algorithm Scheduling Flexible Job-shop Scheduling Problem with New Job Insertion[J]. Expert Systems with Applications, 2015, 42(21): 7652-7663.
2	Ding Haojie, Gu Xingsheng. Improved Particle Swarm Optimization Algorithm Based Novel Encoding and Decoding Schemes for Flexible Job Shop Scheduling Problem[J]. Computers & Operations Research, 2020, 121: 104951.
3	Chen Nanlei, Xie Naiming, Wang Yuquan. An Elite Genetic Algorithm for Flexible Job Shop Scheduling Problem with Extracted Grey Processing Time[J]. Applied Soft Computing, 2022, 131: 109783.
4	Luo Qiang, Deng Qianwang, Gong Guiliang, et al. A Distributed Flexible Job Shop Scheduling Problem Considering Worker Arrangement Using an Improved Memetic Algorithm[J]. Expert Systems with Applications, 2022, 207: 117984.
5	Li Rui, Gong Wenyin, Wang Ling, et al. Two-stage Knowledge-driven Evolutionary Algorithm for Distributed Green Flexible Job Shop Scheduling with Type-2 Fuzzy Processing Time[J]. Swarm and Evolutionary Computation, 2022, 74: 101139.
6	Vali Masoumeh, Salimifard Khodakaram, Gandomi Amir H, et al. Application of Job Shop Scheduling Approach in Green Patient Flow Optimization Using a Hybrid Swarm Intelligence[J]. Computers & Industrial Engineering, 2022, 172, Part A: 108603.
7	Afsar Sezin, Juan José Palacios, Puente Jorge, et al. Multi-objective Enhanced Memetic Algorithm for Green Job Shop Scheduling with Uncertain Times[J]. Swarm and Evolutionary Computation, 2022, 68: 101016.
8	Liu Zhengchao, Guo Shunsheng, Wang Lei. Integrated Green Scheduling Optimization of Flexible Job Shop and Crane Transportation Considering Comprehensive Energy Consumption[J]. Journal of Cleaner Production, 2019, 211: 765-786.
9	吴秀丽, 孙阳君. 机器多转速的柔性作业车间绿色调度问题[J]. 计算机集成制造系统, 2018, 24(4): 862-875.
	Wu Xiuli, Sun Yangjun. Flexible Job Shop Green Scheduling Problem with Multi-speed Machine[J]. Computer Integrated Manufacturing Systems, 2018, 24(4): 862-875.
10	Mohammed Azmi Al-Betar, Zaid Abdi Alkareem Alyasseri, Awadallah Mohammed A, et al. Coronavirus Herd Immunity Optimizer (CHIO)[J]. Neural Computing and Applications, 2021, 33(10): 5011-5042.
11	Hosny Khalid M, Khalid Asmaa M, Hamza Hanaa M, et al. Multilevel Segmentation of 2D and Volumetric Medical Images Using Hybrid Coronavirus Optimization Algorithm[J]. Computers in Biology and Medicine, 2022, 150: 106003.
12	Rani Nibha, Malakar Tanmoy. Maximization of Reactive Power Reserve in Wind Integrated Power System Using CHIO Approach[J]. IFAC-PapersOnLine, 2022, 55(1): 150-155.
13	杨佩, 亓祥波, 原宇轩, 等. PFSP问题的混和CHIO算法优化[J]. 计算机系统应用, 2022, 31(8): 380-387.
	Yang Pei, Qi Xiangbo, Yuan Yuxuan, et al. Optimization of Hybrid CHIO Algorithm for PFSP[J]. Computer Systems & Applications, 2022, 31(8): 380-387.
14	Chen Ronghua, Yang Bo, Li Shi, et al. An Effective Multi-population Grey Wolf Optimizer Based on Reinforcement Learning for Flow Shop Scheduling Problem with Multi-machine Collaboration[J]. Computers & Industrial Engineering, 2021, 162: 107738.
15	顾九春, 姜天华, 朱惠琦. 多目标离散灰狼优化算法求解作业车间节能调度问题[J]. 计算机集成制造系统, 2021, 27(8): 2295-2306.
	Gu Jiuchun, Jiang Tianhua, Zhu Huiqi. Energy-saving Job Shop Scheduling Problem with Multi-objective Discrete Grey Wolf Optimization Algorithm[J]. Computer Integrated Manufacturing Systems, 2021, 27(8): 2295-2306.
16	尚玉叶, 袁家斌. 深空环境中基于云边端协同的任务卸载方法[J]. 计算机科学, 2023, 50(2): 80-88.
	Shang Yuye, Yuan Jiabin. Task Offloading Method Based on Cloud-edge-end Cooperation in Deep Space Environment[J]. Computer Science, 2023, 50(2): 80-88.
17	曹梦龙, 赵文彬, 陈志强. 融合粒子群算法与改进灰狼算法的机器人路径规划[J]. 系统仿真学报, 2023, 35(8): 1768-1775.
	Cao Menglong, Zhao Wenbin, Chen Zhiqiang. Robot Path Planning by Fusing Particle Swarm Algorithm and Improved Grey Wolf Algorithm[J]. Journal of System Simulation, 2023, 35(8): 1768-1775.
18	Wu Xiuli, Wu Shaomin. An Elitist Quantum-inspired Evolutionary Algorithm for the Flexible Job-shop Scheduling Problem[J]. Journal of Intelligent Manufacturing, 2017, 28(6): 1441-1457.
19	成金海, 徐华, 杨金峰. 改进灰狼优化算法求解模糊车间调度问题[J]. 计算机应用研究, 2023, 40(7): 2060-2067, 2074.
	Cheng Jinhai, Xu Hua, Yang Jinfeng. Improved Grey Wolf Optimization Algorithm for Fuzzy Job-shop Scheduling Problem[J]. Application Research of Computers, 2023, 40(7): 2060-2067, 2074.
20	Ma Xunde, Bi Li, Jiao Xiaogang, et al. An Efficient and Improved Coronavirus Herd Immunity Algorithm Using Knowledge-driven Variable Neighborhood Search for Flexible Job-shop Scheduling Problems[J]. Processes, 2023, 11(6): 1826.
21	张超勇, 饶运清, 刘向军, 等. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程, 2004, 15(23): 2149-2153.
	Zhang Chaoyong, Rao Yunqing, Liu Xiangjun, et al. An Improved Genetic Algorithm for the Job Shop Scheduling Problem[J]. China Mechanical Engineering, 2004, 15(23): 2149-2153.
22	陈魁, 毕利. 考虑运输时间的多目标柔性作业车间调度研究[J]. 小型微型计算机系统, 2021, 42(5): 946-952.
	Chen Kui, Bi Li. Research on Multi-objective Flexible Job Shop Scheduling Considering Transport Time[J]. Journal of Chinese Computer Systems, 2021, 42(5): 946-952.
23	孙爱红, 宋豫川, 杨云帆, 等. 考虑关键件加工质量的双资源约束车间调度算法[J]. 中国机械工程, 2022, 33(21): 2590-2600.
	Sun Aihong, Song Yuchuan, Yang Yunfan, et al. Dual Resource-constrained Flexible Job Shop Scheduling Algorithm Considering Machining Quality of Key Jobs[J]. China Mechanical Engineering, 2022, 33(21): 2590-2600.
24	刘琼, 张超勇, 饶运清, 等. 改进遗传算法解决柔性作业车间调度问题[J]. 工业工程与管理, 2009, 14(2): 59-66.
	Liu Qiong, Zhang Chaoyong, Rao Yunqing, et al. Flexible Job-shop Scheduling Problem with Improved Genetic Algorithm[J]. Industrial Engineering and Management, 2009, 14(2): 59-66.
25	Sun Kexin, Zheng Debin, Song Haohao, et al. Hybrid Genetic Algorithm with Variable Neighborhood Search for Flexible Job Shop Scheduling Problem in a Machining System[J]. Expert Systems with Applications, 2023, 215: 119359.
26	Brandimarte Paolo. Routing and Scheduling in a Flexible Job Shop by Tabu Search[J]. Annals of Operations Research, 1993, 41(3): 157-183.

机器	档位1		档位2		档位3		开关机/(W/min)	待机/W
机器	UPE	UIE	UPE	UIE	UPE	UIE	开关机/(W/min)	待机/W
1	1 230	230	1 510	320	2 270	370	2 600	20
2	1 160	180	1 500	280	1 820	350	2 530	22
3	1 150	190	1 390	300	1 880	350	2 560	25
4	1 380	230	1 920	330	2 340	390	2 740	30
5	1 040	220	1 500	310	2 220	380	2 640	25
6	1 270	230	1 560	270	2 260	370	2 600	27
7	1 170	220	1 510	300	2 160	400	2 570	22
8	1 000	170	1 210	290	1 690	350	2 550	20
9	1 300	250	1 770	320	2 510	400	2 860	30
10	1 360	250	1 960	310	2 510	380	2 840	28
11	1 350	240	1 850	340	2 440	390	2 800	22
12	1 030	190	1 480	280	1 920	320	2 630	21
13	1 310	230	1 860	310	2 290	390	2 860	28
14	1 060	200	1 450	300	1 960	400	2 760	29
15	1 450	300	2 090	350	2 970	400	3 050	30

算例	CHIO1		CHIO2		CHIO3		DCHIO
算例	mean	std	mean	std	mean	std	mean	std
-/=/+	10/0/0		6/3/1		2/7/1
MK01	0.124 1-	0.008 3	0.167 6-	0.005 5	0.180 9=	0.004 9	0.181 6	0.002 5
MK02	0.159 9-	0.027 7	0.277 2-	0.009 7	0.290 8=	0.008 6	0.290 3	0.008 6
MK03	0.112 9-	0.009 3	0.219 6=	0.005 3	0.222 6-	0.0045	0.227 2	0.002 3
MK04	0.173 4-	0.009 9	0.247 9-	0.007 8	0.256 7-	0.008 8	0.263 1	0.006 6
MK05	0.103 6-	0.004 7	0.138 7=	0.002 8	0.140 3=	0.003 4	0.143 3	0.003 7
MK06	0.115 8-	0.023 7	0.315 0-	0.014 5	0.336 1=	0.014 5	0.342 1	0.012 2
MK07	0.115 0-	0.012 8	0.214 1-	0.004 2	0.220 4=	0.003 7	0.222 6	0.003 0
MK08	0.114 4-	0.003 6	0.156 5=	0.003 5	0.160 1=	0.001 9	0.162 8	0.001 4
MK09	0.135 2-	0.008 6	0.241 9+	0.006 0	0.241 8+	0.008 1	0.232 1	0.006 8
MK10	0.123 4-	0.013 2	0.252 5-	0.011 2	0.268 9=	0.007 9	0.271 4	0.005 6

算例	Pareto解个数			min(C_max)			min(E)			HV
算例	A	B	C	A	B	C	A	B	C	A	B	C
mean	6.9	7.4	21.4	286.8	283.8	187.0	44.56	42.89	35.00	0.438 0	0.442 2	0.777 0
MK01	5	6	11	59.2	67.2	42.0	6.67	6.66	5.26	0.654 6	0.559 6	0.869 7
MK02	5	7	16	56.0	57.9	29.2	6.76	7.03	4.76	0.579 0	0.552 1	0.964 6
MK03	5	8	5	312.5	315.1	204.0	49.51	43.54	30.94	0.450 4	0.450 2	0.773 0
MK04	10	9	30	99.7	97.6	68.2	14.05	13.34	11.13	0.423 9	0.445 3	0.717 0
MK05	7	6	32	248.0	244.0	179.0	24.14	23.50	21.97	0.393 0	0.409 0	0.658 3
MK06	6	7	14	158.2	145.5	70.8	26.28	23.48	14.57	0.318 4	0.399 2	0.888 3
MK07	7	7	41	251.3	254.3	154.0	30.79	29.56	21.99	0.486 1	0.478 5	0.829 6
MK08	7	11	34	689.7	675.9	523.0	101.30	98.97	89.92	0.296 4	0.316 9	0.540 6
MK09	8	7	20	540.2	549.1	337.7	96.47	95.02	79.32	0.440 1	0.428 1	0.792 7
MK10	9	6	11	453.6	431.1	261.7	89.73	87.79	70.08	0.337 9	0.383 2	0.735 7

算例	Pareto解个数		min(C_max)		min(E)		HV
算例	LCSA	DCHIO	LCSA	DCHIO	LCSA	DCHIO	LCSA	DCHIO
mean	8.8	18.7	182.5	187.0	42.09	35.00	0.088 9	0.135 0
MK01	6	11	42	42.0	6.20	5.26	0.109 2	0.166 9
MK02	7	13	28	29.2	5.56	4.76	0.125 3	0.178 4
MK03	7	4	204	204.0	37.65	30.94	0.057 6	0.103 5
MK04	7	24	68	68.2	13.88	11.13	0.098 4	0.167 1
MK05	12	31	181	179.0	27.57	21.97	0.079 6	0.151 4
MK06	11	8	67	70.8	14.83	14.57	0.101 3	0.099 2
MK07	5	48	146	154.0	27.78	21.99	0.078 9	0.129 4
MK08	3	30	523	523.0	109.93	89.92	0.059 1	0.110 4
MK09	21	11	326	337.7	93.11	79.32	0.103 0	0.147 3
MK10	9	7	240	261.7	84.37	70.08	0.076 3	0.096 8

[1]	蒋权, 魏静萱. 用于动态柔性作业车间调度的实时调度方法[J]. 系统仿真学报, 2024, 36(7): 1609-1620.
[2]	徐宜刚, 陈勇, 王宸, 彭运贤. 改进NSGA-III求解高维多目标绿色柔性作业车间调度问题[J]. 系统仿真学报, 2024, 36(10): 2314-2329.
[3]	胥远兴, 张孟健, 王德光. 面向柔性作业车间调度问题的混沌编码量子粒子群优化算法[J]. 系统仿真学报, 2024, 36(10): 2371-2382.
[4]	张洪亮, 徐静茹, 谈波, 徐公杰. 考虑交货期的双资源柔性作业车间节能调度[J]. 系统仿真学报, 2023, 35(4): 734-746.
[5]	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
[6]	张洪亮, 丁仁曼, 徐公杰. 考虑区间工时的多目标柔性作业车间节能调度[J]. 系统仿真学报, 2022, 34(09): 1976-1987.
[7]	陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853.
[8]	尤一琛, 王艳, 纪志成. 基于博弈论的柔性作业车间动态调度研究[J]. 系统仿真学报, 2021, 33(11): 2579-2588.
[9]	丁宇, 王艳, 纪志成. 柔性作业车间生产与能耗协同优化决策方法[J]. 系统仿真学报, 2020, 32(12): 2426-2437.
[10]	王艳, 丁宇. 动态柔性作业车间优化调度与决策方法[J]. 系统仿真学报, 2020, 32(11): 2073-2083.
[11]	张祥, 王艳, 纪志成. 基于动态交互层的柔性作业车间动态调度问题研究[J]. 系统仿真学报, 2020, 32(11): 2129-2137.
[12]	李俊萱, 王艳, 纪志成. 基于混合QPSO的模糊柔性作业车间调度问题研究[J]. 系统仿真学报, 2020, 32(10): 2010-2021.
[13]	李珂, 王艳, 纪志成. 基于混合策略的入侵杂草算法的FJSP问题研究[J]. 系统仿真学报, 2018, 30(5): 1918-1926.
[14]	徐文豪, 王艳, 严大虎, 纪志成. 花授粉算法求解多目标模糊柔性作业车间调度[J]. 系统仿真学报, 2018, 30(11): 4403-4412.
[15]	张新, 李珂, 严大虎, 纪志成. 改进入侵杂草算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2018, 30(11): 4469-4476.