基于改进狼群算法的柔性作业车间调度研究

doi:10.16182/j.issn1004731x.joss.21-1019

摘要/Abstract

摘要：

将一种改进的狼群算法用于解决柔性作业车间多目标调度优化的难题。以工件的最大完工时间和机器能耗为优化目标建立了多目标柔性作业车间调度模型；针对传统狼群算法容易陷入局部最优的缺点提出了一种改进的狼群算法，通过对狼群算法智能行为的改进，从工序和机器2个层面设计个体编码，引入POX (precedence operation crossover)交叉操作，保证解的合法性，提高算法的全局搜索能力；通过对2个车间实例的对比实验来验证改进狼群算法的有效性。实验结果表明，提出的改进狼群算法不仅具有良好的全局搜索能力，寻优能力较其他算法也有所提升，能够为制造业提高生产效率提供新的解决思路。

关键词: 改进狼群算法, 车间调度, 能耗, 多目标优化

Abstract:

An improved wolf pack algorithm is proposed for solving multi-objective scheduling optimization for flexible job shop problems. A multi-objective flexible job shop scheduling model is developed with the maximum completion time of the workpiece and the energy consumption of the machine as the optimization goals. An improved wolf pack algorithm is proposed for solving the shortcomings that traditional wolf pack algorithm is easy to fall into the local optimization. Through improving the intelligent behavior of the wolf pack algorithm, individual codes are designed from the two levels of job's process and machine, and POX(precedence operation crossover) cross operation is introduced to ensure the legality of the solution and improve the search ability of the algorithm. The effectiveness of the improved wolf pack algorithm is verified through comparative experiments on two workshop examples. Experimental results show, the improved wolf pack algorithm not only has good global search ability, but also has an improved optimization ability compared with other algorithms. It can provide new solutions for the manufacturing industry to improve production efficiency.

Key words: improved wolf pack algorithm, job shop scheduling, energy consuming, multi-objective optimization

中图分类号:

TP278

张朝阳, 徐莉萍, 李健, 赵义豪, 何奎. 基于改进狼群算法的柔性作业车间调度研究[J]. 系统仿真学报, 2023, 35(3): 534-543.

Chaoyang Zhang, Liping Xu, Jian Li, Yihao Zhao, Kui He. Flexible Job-Shop Scheduling Problem Based on Improved Wolf Pack Algorithm[J]. Journal of System Simulation, 2023, 35(3): 534-543.

图/表 18

表1

符号说明

符号	定义
$N = {1, 2, ⋯, i, ⋯, n}$	工件
$J = {1, 2, ⋯, j, ⋯, q}$	工序
$M = {1, 2, ⋯, k, ⋯, m}$	机器
$O i, j$	工件 $i$ 的第 $j$ 道工序
$S i, j, k$	$O i, j$ 的开始加工时间
$F i, j, k$	$O i, j$ 的结束加工时间
$C i$	工件 $i$ 的完工时间
$T i, j, k$	$O i, j$ 在机器 $k$ 上的加工时间
$U i, j, k$	整数变量，取0或者1，如果 $O i, j$ 在机器 $k$ 上加工，则为1；否则为0
$P c k$	机器 $k$ 的加工功率
$P i d l e k$	机器 $k$ 的待机功率
$T c k$	机器 $k$ 的加工时间
$T i d l e k$	机器 $k$ 的待机时间
$E k$	机器 $k$ 的总能耗
$E c k$	机器 $k$ 的加工能耗
$E i d l e k$	机器 $k$ 的待机能耗

表1

表2

图1

图2

图3

表3

表4

5个工件在5台机器上的加工工艺

工件	工序	机器
工件	工序	$M 1$	$M 2$	$M 3$	$M 4$	$M 5$
J₁	O₁₁	5	4	7	4	10
	O₁₂	4	4	10	3	9
	O₁₃	5	8	3	6	10
J₂	O₂₁	8	9	9	9	4
	O₂₂	3	2	2	1	7
	O₂₃	8	2	4	7	8
J₃	O₃₁	7	2	1	9	9
	O₃₂	8	7	7	8	2
	O₃₃	4	6	1	7	1
J₄	O₄₁	1	8	7	9	8
	O₄₂	7	8	3	4	10
	O₄₃	8	3	1	6	6
J₅	O₅₁	3	7	7	10	6
	O₅₂	2	10	9	5	10
	O₅₃	2	2	5	9	5
加工功率P_c/kW		2	1.8	1.6	2.4	3.8
待机功率P_idle/kW		0.5	0.6	0.3	0.4	0.5

表4

图4

图5

图6

表5

表6

表7

6个工件在6台机器上的加工工艺

工件	工序	机器
工件	工序	M₁	M₂	M₃	M₄	M₅	M₆
J₁	O₁₁	10	15		14		14
	O₁₂		6	4	16	15
	O₁₃		5			16	8
	O₁₄	12		13	13
J₂	O₂₁	15		6	16.5	11
	O₂₂		15	10	7		12
	O₂₃	5		16	10	14
	O₂₄		10
J₃	O₃₁	14	15	6	5	4
	O₃₂		5	6		16
	O₃₃	5	8		11		15
	O₃₄		6	17	14	12
J₄	O₄₁	20		19	13	15
	O₄₂		10	7	14	7	15
	O₄₃	4	8				16
	O₄₄	9		6		6
J₅	O₅₁		6		7	12	8
	O₅₂	8		12	16		6
	O₅₃	13	12			16	8
	O₅₄		4	6	5	12
J₆	O₆₁		11			7	8
	O₆₂			8	12		6
	O₆₃	10	5		13	6
	O₆₄	16		8			12
加工功率 $P c / k W$		2.66	2.23	1.83	2.56	2.35	1.35
待机功率 $P i d l e / k W$		0.50	0.40	0.35	0.41	0.36	0.25

表7

表8

表9

图7

图8

表10

大规模实例对比结果

目标参数	50×5		60×6
目标参数	IWPA	GA	IWPA	GA
$f 1$ 完工时间	77	87	346	358
$f 2$ 能耗值	818.1	832.9	3 606.2	3 746.4
$f$ 归一化值	0.15	0.24	0.25	0.28

表10

参考文献 20

1	Johnson S M. Optimal Two-and Three-Stage Production Schedules with Setup Times Included[J]. Naval Research Logistics Quarterly (S0894-069X), 1954, 12(1): 336-353.
2	Chaudhry, Imran, Ali, et al. A Research Survey: Review of Flexible Job Shop Scheduling Techniques[J]. International Transactions in Operational Research (S0969-6016), 2005, 23(3): 551-591.
3	Pezzella F, Morganti G, Ciaschetti G. A Genetic Algorithm for the Flexible Job-Shop Scheduling Problem[J]. Computers & Operations Research (S0305-0548), 2008, 35(10): 3202-3212.
4	Yuan Y, Xu H. Flexible Job Shop Scheduling Using Hybrid Differential Evolution Algorithms[J]. Computers & Industrial Engineerin (S0360-8352), 2013, 65(2): 246-260.
5	Ham A, Park M J, Kim K M, et al. Energy-Aware Flexible Job Shop Scheduling Using Mixed Integer Programming and Constraint Programming[J]. Mathematical Problems in Engineering (S1024-123X), 2021: 1-12.
6	Gao K Z, Suganthan P N, Chua T J, et al. A Two-stage Artificial Bee Colony Algorithm Scheduling Flexible Job-Shop Scheduling Problem with New Job Insertion[J]. Expert Systems with Applications (S0957-4174), 2015, 42(21): 7652-7663.
7	Ishikawa S, Kubota R, Horio K. Effective Hierarchical Optimization by a Hierarchical Multi-space Competitive Genetic Algorithm for the Flexible Job-Shop Scheduling Problem[J]. Expert Systems with Applications (S0957-4174), 2015, 42(24): 9434-9440.
8	Jiang T, Deng G. Optimizing the Low-Carbon Flexible Job Shop Scheduling Problem Considering Energy Consumption[J]. IEEE Access (S2169-3536), 2018, 6: 99.
9	Lei D M, Li M, Wang L. A Two-Phase Meta-Heuristic for Multiobjective Flexible Job Shop Scheduling Problem with Total Energy Consumption Threshold[J]. IEEE Transactions on Cybernetics (S2168-2267), 2018, 49(3): 1097-1109.
10	王雷, 蔡劲草, 石鑫. 基于改进遗传算法的多目标柔性作业车间节能调度问题[J]. 南京理工大学学报(自然科学版), 2017, 41(4): 494-502.
	Wang Lei, Cai Jincao, Shi Xin. Multi-objective Flexible Job Shop Energy-saving Scheduling Problem Based on Improved Genetic Algorithm[J]. Journal of Nanjing University of Science and Technology(Natural Science Edition), 2017, 41(4): 494-502.
11	张新, 李珂, 严大虎, 等. 改进入侵杂草算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2018, 30(11): 4469-4476.
	Zhang Xin, Li Ke, Yan Dahu, et al. Improved Intrusion Weed Algorithm for Solving Flexible Job Shop Scheduling Problem[J]. Journal of System Simulation, 2018, 30(11): 4469-4476.
12	吴秀丽, 张志强, 杜彦华, 等. 改进细菌觅食算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2015, 21(5): 1262-1270.
	Wu Xiuli, Zhang Zhiqiang, Du Yanhua, et al. Improved Bacteria Foraging Optimization Algorithm for Flexible Job Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2015, 21(5): 1262-1270.
13	吴虎胜, 张凤鸣, 吴庐山. 一种新的群体智能算法—狼群算法[J]. 系统工程与电子技术, 2013, 35(11): 2430-2438.
	Wu Husheng, Zhang Fengming, Wu Lushan. New Swarm Intelligence Algorithm-Wolf Pack Algorithm[J]. Systems Engineering and Electronics, 2013, 35(11): 2430-2438.
14	董亚科, 杜军, 李博, 等. 多选择背包问题离散狼群算法研究[J]. 传感器与微系统, 2015, 34(6): 21-23, 26.
	Dong Yake, Du Jun, Li Bo, et al. Research on Discrete Wolf Pack Algorithm of Multiple Choice Knapsack Problem[J]. Transducer and Microsystem Technologies, 2015, 34(6): 21-23, 26.
15	Wu H S, Zhang F M, Li H, et al. Discrete Wolf Pack Algorithm for Traveling Salesman Problem[J]. Control & Decision (S1001-0920), 2015, 30(10): 1861-1867.
16	李斌. 基于改进狼群算法的森林灭火资源调度研究[D]. 长沙: 中南林业科技大学, 2018.
	Li Bin. Research on Forest Fire-fighting Resource Scheduling Based on Improved Wolves Algorithm[D]. Changsha: Central South University of Forestry and Technology, 2018.
17	Wang F, Tian Y, Wang X. A Discrete Wolf Pack Algorithm for Job Shop Scheduling Problem[C]// 2019 5th International Conference on Control, Automation and Robotics (ICCAR). Beijing: IEEE, 2019.
18	谢锐强, 张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
	Xie Ruiqiang, Zhang Huizhen. Two-Vector Wolf Pack Algorithm for Flexible Job Shop Scheduling Problem[J]. Computer Engineering and Applications, 2021, 57(7): 251-256.
19	张超勇, 饶运清, 刘向军, 等. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程, 2004(23): 83-87.
	Zhang Chaoyong, Rao Yunqing, Liu Xiangjun, et al. An Improved Genetic Algorithm for the Job-Shop Scheduling Problem[J]. China Mechanical Engineering, 2004(23): 83-87.
20	解潇晗, 朱晓春, 周琦, 等. 低能耗柔性作业车间调度研究[J]. 机电工程,2020, 37(2): 132-137.
	Xie Xiaohan, Zhu Xiaochun, Zhou Qi, et al. Scheduling of Low Energy Consumption Flexible Job Shop[J]. Mechanical & Electrical Engineering Magazine, 2020, 37(2): 132-137.

参数名	数值
种群规模	100
迭代次数	200
探狼比例因子	0.4
最大游走次数	10
工序游走步长	4
机器游走步长	2
更新比例因子	0.3

实验序号	α₁	α₂	最大完工时间	能耗值	适应度值
1	1	0	10	80.0	12.300
2	0.9	0.1	10	76.3	12.410
3	0.8	0.2	11	86.0	13.834
4	0.7	0.3	10	79.8	12.800
5	0.6	0.4	10	76.3	12.720
6	0.5	0.5	11	78.3	13.620
7	0.4	0.6	10	76.3	12.931
8	0.3	0.7	10	76.3	13.037
9	0.2	0.8	11	74.4	13.120
10	0.1	0.9	11	74.4	13.071
11	0	1	12	74.0	12.950

实验序号	α₁	α₂	最大完工时间	能耗值
1	1	0	37	424.8
2	0.9	0.1	39	420.3
3	0.8	0.2	40	382.1
4	0.5	0.5	44	375.5
5	0.2	0.8	41	386.8
6	0.1	0.9	44	375.3
7	0	1	54	370.7

[1]	胡蓉, 丁帅, 钱斌, 张长胜. 超启发式三维EDA求解绿色双边装配线平衡问题[J]. 系统仿真学报, 2023, 35(3): 454-469.
[2]	王旭, 季伟东, 周国辉, 杨佳慧. 基于多指标精英个体博弈机制的多目标优化算法[J]. 系统仿真学报, 2023, 35(3): 494-514.
[3]	欧阳洪才, 吴定会, 范俊岩, 汪晶. 基于改进MOEA/D的钢铁多介质能源计划优化[J]. 系统仿真学报, 2023, 35(3): 568-578.
[4]	季伟东, 岳玉麒, 王旭, 林平. 基于降维和聚类的大规模多目标自然计算方法[J]. 系统仿真学报, 2023, 35(1): 41-56.
[5]	赵也践, 王艳红, 张俊, 于洪霞, 田中大. 改进Q学习算法在作业车间调度问题中的应用[J]. 系统仿真学报, 2022, 34(6): 1247-1258.
[6]	张森, 张孟炎, 邵敬平, 普杰信. 基于随机策略搜索的多机三维路径规划方法[J]. 系统仿真学报, 2022, 34(6): 1286-1295.
[7]	张其文, 张斌. 基于教学优化算法求解置换流水车间调度问题[J]. 系统仿真学报, 2022, 34(5): 1054-1063.
[8]	龙艳琴, 乔贵方, 宋光明, 张颖, 程琳琳. 二维变刚度蛇形机器人的运动仿真与性能分析[J]. 系统仿真学报, 2022, 34(4): 759-767.
[9]	冯开团, 袁杰. 基于改进注水算法的离散车间任务分配问题研究[J]. 系统仿真学报, 2022, 34(4): 768-776.
[10]	陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.
[11]	赵梓安, 周泓, 雷颖健. 基于改进狼群算法与仿真的单元调度优化[J]. 系统仿真学报, 2022, 34(2): 201-211.
[12]	白燕, 武璐璐, 贺引娥, 王玉英. 基于动态温度调控的空调系统能耗预测[J]. 系统仿真学报, 2022, 34(2): 366-375.
[13]	孙宁可, 王艳, 纪志成. 基于深度自编码器的电力能耗异常检测方法[J]. 系统仿真学报, 2022, 34(12): 2557-2565.
[14]	闫秀英, 党苗苗. 基于改进多目标粒子群算法的家庭用电时段优化[J]. 系统仿真学报, 2022, 34(1): 70-78.
[15]	张洪亮, 丁仁曼, 徐公杰. 考虑区间工时的多目标柔性作业车间节能调度[J]. 系统仿真学报, 2022, 34(09): 1976-1987.