基于改进狼群算法与仿真的单元调度优化

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

摘要/Abstract

摘要：

单元制造是现代生产系统的重要组织形式。对制造单元的调度过程中，机器故障与中断是很常见的问题，机器空转造成的能源浪费也不可忽视，相关研究具有重要现实意义。考虑单元调度中的机器中断和能耗，建立了一个最小化所有工件完工时间及机器闲置能源消耗和中断成本的整数规划模型，并提出了一种基于改进狼群算法和离散事件仿真的混合优化

方法

加以求解，有效提高了算法的寻优能力。数值实验表明，提出的算法具有良好的收敛性，可以在合理的迭代次数内找到问题的满意解。

关键词: 单元制造系统, 单元调度, 改进狼群算法, 离散事件仿真, 机器中断, 机器耗能

Abstract:

Cell manufacturing is an important organizational form of modern production systems. In scheduling of cell manufacturing systems, machine failures or interruptions are very common in practice, meanwhile the waste due to energy consumption during machine idle time cannot be ignored. Hence the relevant research is with strong significance. This paper considers the problems of machine interruption and energy consumption in cell scheduling, and developed an integer programming model to minimize the makespan as well as the cost of energy consumption during machine idling and the interruption cost. A mixed optimization method is proposed based on improved wolf pack algorithm and discrete event simulation to solve the problem, which can effectively improve the optimization performance of the algorithm. Numerical experiments demonstrate that the proposed hybrid algorithm shows a good convergence, and a satisfactory solution to the problem can be reached within a reasonable number of iterations.

Key words: cellular manufacturing systems, cell scheduling, improved wolf pack algorithm, discrete event simulation, machine interruption, energy consumption

中图分类号:

TP391.9

赵梓安, 周泓, 雷颖健. 基于改进狼群算法与仿真的单元调度优化[J]. 系统仿真学报, 2022, 34(2): 201-211.

Zi'an Zhao, Hong Zhou, Yingjian Lei. Modeling and Optimization for Manufacturing Cell Scheduling Based on Improved Wolf Pack Algorithm and Simulation[J]. Journal of System Simulation, 2022, 34(2): 201-211.

图/表 11

图1

图2

图3

表1

表2

WPA-BFO-SIM参数设置

WPA-BFO-SIM参数

值

狼群数量

最大迭代次数

最大游走次数

探狼比例因子

距离判定因子

步长因子

淘汰因子

搜寻方式上界

搜寻方式下界

柯西变异概率 $P c$

高斯扰动概率 $P g a$

100

800

1000

0.5

表2

图4

表3

图5

图6

表4

表5

5种优化算法在不同数据规模下的优化比较 (%)

算例	GA			ACO			WPA			HWPA			WPA-BFO-SIM
算例	$Δ R ˉ$	$Δ W$	$Δ E$	$Δ R ˉ$	$Δ W$	$Δ E$	$Δ R ˉ$	$Δ W$	$Δ E$	$Δ R ˉ$	$Δ W$	$Δ E$	$Δ R ˉ$	$Δ W$	$Δ E$
1	4.8	4.4	41.2	4.8	4.4	41.2	4.8	4.4	41.2	4.8	4.4	41.2	4.8	4.4	41.2
2	2.8	17.1	25	2.8	17.1	25	2.8	17.1	25	2.8	17.1	25	2.8	17.1	25
3	6.2	10.4	23.1	6.2	10.4	23.1	5.2	10.4	20.9	8	10.4	26.7	8	10.4	26.7
4	3.3	7.1	13.5	3.3	7.1	13.5	5.3	7.1	17.4	5.8	9.8	20.6	7	9.8	23
5	0.5	6.4	5.5	0.7	7.6	6.2	1.5	9.6	12.6	2	11.5	15.4	2.8	11.5	17
6	0.3	2	2.8	0.6	5.9	4.7	1	3.9	6.3	1.3	13	21.6	4.9	14.8	24.8
7	1.7	9.1	13.6	3.8	15.2	24.8	3.1	9.8	18.1	3.5	23.3	31.2	3.1	24.8	32.1
8	0.8	9.1	11.6	5.1	10.2	25.5	6.7	24.6	3	5.3	16	30	5.6	24.6	33.2
9	0.6	7	4.7	4.3	9.2	24	1.4	6.7	9.7	5	10.7	29	5.1	13.5	31.5
10	3	4.2	17.3	4.5	6.3	19.9	1.2	8.3	13.9	6	10.2	34.6	6.5	16.2	41.7

表5

参考文献 22

1	Wu X, Chu C H, Wang Y, et al. A Genetic Algorithm for Cellular Manufacturing Design and Layout[J]. European Journal of Operational Research, 2007, 181:156-167.
2	Feng Y, Li G, Sethi S P S. A Three-layer Chromosome Genetic Algorithm for Multi-cell Scheduling with Flexible Routes and Machine Sharing[J]. International Journal of Production Economics, 2018, 196:269-283.
3	Sinaki R Y, Sadeghi A, Suer G, et al. A Weighted Multi-Objective Mathematical Model for Cell Scheduling and Environmentally Sustainable Supply Chain Network[J]. Procedia Manufacturing, 2019, 39:1559-1566.
4	International Energy Agency (IEA), International Energy Outlook 2017[R]. [2017-09-14](2021-03-21) https://www.eia.gov/pressroom/presentations/mead_91417. pdf.
5	Iqbal N, Aziz M H, Jahanzaib M, et al. Integration of Cell Formation and Job Sequencing to Minimize Energy Consumption with Minimum Make-span[J]. Proceedings of the Institution of Mechanical Engineers Part B Journal of Engineering Manufacture(S0954-4054), 2016, 231(14): 2636-2651.
6	Liu Y, Dong H, Lohse N, et al. A multi-objective Genetic Algorithm for Optimization of Energy Consumption and Shop Floor Production Performance[J]. International Journal of Production Economics(S0925-5273), 2016, 179: 259-272.
7	Gahm C, Denz F, Dirr M, et al. Energy-efficient Scheduling in Manufacturing Companies: A Review and Research Framework[J]. European Journal of Operational Research(S0377-2217), 2016, 248(3): 744-757.
8	Yang Y, Huang M, Wang Z Y, et al. Robust Scheduling based on Extreme Learning Machine for Bi-objective Flexible Job-shop Problems with Machine Breakdowns[J]. Expert Systems with Applications(S0957-4174), 2020, 158: 113545.
9	Tadayonirad S, Seidgar H, Fazlollahtabar H, et al. Robust Scheduling in Two-stage Assembly Flow Shop Problem with Random Machine Breakdowns: Integrated Meta-heuristic Algorithms and Simulation Approach[J]. Assembly Automation(S0144-5154), 2019, 39(5): 944-962.
10	Li Y, He Y, Wang Y, et al. An Optimization Method for Energy-conscious Production in Flexible Machining Job Shops with Dynamic Job Arrivals and Machine Breakdowns[J]. Journal of Cleaner Production(S0959-6526), 2020, 254:120009.
11	Sarker R, Omar M, Hasan K S M, et al. Hybrid Evolutionary Algorithm for Job Scheduling under Machine Maintenance[J]. Applied Soft Computing(S1568-4946), 2013, 13(3):1440-1447.
12	吴虎胜, 张凤鸣, 吴庐山.一种新的群体智能算法—狼群算法[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.
13	Wu H S, Xue J J, Xiao R B, et al. Uncertain Bilevel Knapsack Problem based on an Improved Binary Wolf Pack Algorithm[J]. Frontiers of Information Technology & Electronic Engineering(S2095-9184), 2020, 21(9): 1356-1368.
14	Xiu-Wu Y U, Hao Y U, Yong L, et al. A Clustering Routing Algorithm based on Wolf Pack Algorithm for Heterogeneous Wireless Sensor Networks[J]. Computer networks(S1389-1286), 2020, 167(Feb.11): 106994.1-106994.10.
15	Hu J, Wu H, Zhan R, et al. Hybrid Integer-coded Wolf Pack Algorithm for Multiple-Type Flatcars Loading Problem[J]. Journal of Rail Transport Planning & Management(S2210-9706), 2020: 100201.
16	Chen Y, Jia Z, Ai X, et al. A Modified Two-part Wolf Pack Search Algorithm for the Multiple Traveling Salesmen Problem[J]. Applied Soft Computing(S1568-4946), 2017, 61:714-725.
17	Chen X Y, Tang C J, Wang J, et al. Improved Wolf Pack Algorithm Based on Differential Evolution Elite Set[J]. IEICE Transactions on Information and Systems(S1745-1361), 2018, E101D (7): 1946-1949.
18	Passino K M. Biomimicry of Bacterial Foraging for Distributed Optimization and Control[J]. IEEE Control Systems Magazine(S1066-033X), 2002, 22(3): 52-67.
19	李堂金. 基于狼群算法的模糊时间序列预测模型研究[D]. 重庆: 重庆邮电大学, 2020.
	Li Tangjin. Research on the Fuzzy Time Series Forecasting Model Based on Wolf Pack Algorithm[D]. Chongqing: Chongqing University of Posts and Telecommunications, 2020.
20	郭立婷. 基于自适应和变游走方向的改进狼群算法[J].浙江大学学报(理学版), 2018, 45(3): 284-293.
	Guo Liting. Improved Wolf Pack Algorithm based on Adaptive Step Length and Adjustable Scouting Direction[J]. Journal of Zhejiang University (Science Edition), 2018, 45(3): 284-293.
21	Mirjalili S, Lewis A2016. The Whale Optimization Algorithm[J]. Advances in Engineering Software(S0965-9978), 95(5), 51-67.
22	谢锐强, 张惠珍.求解柔性作业车间调度问题的两段式狼群算法[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.

方案	优化算法
1	基因遗传算法
2	蚁群算法
3	标准狼群算法
4	两段式狼群算法(TWPA)
5	改进的狼群算法(WPA-BFO-SIM)

算例	GA		ACO		WPA		TWPA		WPA-BFO-SIM
算例	时间/s	目标函数值	时间/s	目标函数值	时间/s	目标函数值	时间/s	目标函数值	时间/s	目标函数值
1	2.746	51.5	2.348	51.5	1.447	51.5	1.041	51.5	0.665	51.5
2	4.272	95.1	3.363	95.1	3.623	95.1	1.847	95.1	1.164	95.1
3	5.167	129.2	4.396	129.2	4.818	129.2	3.071	127.4	2.598	127.4
4	5.824	173.3	4.527	173.3	5.157	170.3	8.626	171.5	4.735	170.3
5	15.154	287.2	14.259	289.5	11.654	287	13.966	277	9.829	276.7
6	19.496	436.2	20.692	437.5	21.556	469.2	30.182	418.4	19.410	401.2
7	35.777	989.7	66.013	962.8	28.063	924.4	39.110	824.8	26.906	776.4
8	77.822	1 502	75.199	1 529.1	78.671	1 579.2	73.521	1 474.8	76.098	1 378.9
9	113.453	2 335	130.412	2 440	96.107	2 390.4	85.419	2 031.7	77.202	2 020.6
10	215.747	2 977.8	250.231	3 891.1	269.663	2 951.1	353.439	2 460.1	204.960	2 301.7

[1]	付建林, 丁国富, 张剑, 江海凡, 郭沛佩. 基于响应面和NSGA-II的AGV系统多目标优化配置[J]. 系统仿真学报, 2022, 34(5): 994-1002.
[2]	刘闽东, 吴龙军, 汤明超, 孟梅. 项目型制造过程信息流集成建模仿真研究[J]. 系统仿真学报, 2022, 34(3): 555-563.
[3]	于绍政, 孙冬石, 陈靖, 李勇超. 自动化集装箱码头机械配置仿真优化研究[J]. 系统仿真学报, 2019, 31(12): 2750-2757.
[4]	李军, 林雪梅, 周杰. CT检查预约规则的仿真模拟研究[J]. 系统仿真学报, 2018, 30(3): 976-986.
[5]	鞠儒生, 朱正秋, 曾云秀, 王瑞贤, 邱晓刚. 基于AHP和熵值模型的军事竞赛研究与仿真[J]. 系统仿真学报, 2018, 30(2): 679-690.
[6]	杨妹, 许霄, 彭勇, 鞠儒生, 黄柯棣, 焦鹏. 一种基于部分重同步机制的运动建模研究[J]. 系统仿真学报, 2017, 29(9): 1880-1885.
[7]	卢绍文, 罗小川. “起重机+过跨车”铁水物流多场景仿真[J]. 系统仿真学报, 2017, 29(10): 2549-2555.
[8]	唐建, 艾芙莉, 邵发明, 张蕉蕉. 基于SimEvents仿真获取网络不交化最小路集[J]. 系统仿真学报, 2016, 28(4): 842-850.
[9]	郑为, 邹启明, 倪文玺. 水下无人潜航器避障与导航仿真系统设计与应用[J]. 系统仿真学报, 2016, 28(1): 91-98.
[10]	荣冈, 肖俊, 胡云苹, 冯毅萍. 一种基于本体的DEVS建模方法[J]. 系统仿真学报, 2015, 27(12): 2878-2890.