Modeling and Optimization for Manufacturing Cell Scheduling Based on Improved Wolf Pack Algorithm and Simulation

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

CLC Number:

TP391.9

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.

Figures/Tables 11

Fig. 1

Fig. 2

Fig. 3

Table 1

Table 2

Parameter values of WPA-BFO-SIM

WPA-BFO-SIM参数

值

狼群数量

最大迭代次数

最大游走次数

探狼比例因子

距离判定因子

步长因子

淘汰因子

搜寻方式上界

搜寻方式下界

柯西变异概率 $P c$

高斯扰动概率 $P g a$

100

800

1000

0.5

Table 2

Fig. 4

Table 3

Fig.5

Fig.6

Table 4

Table 5

Optimization comparison of 5 optimization algorithms under different data scales

算例	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

Table 5

References 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]	Li Min, Zhang Sen, Zeng Xiangguang, Wang Gang, Zhang Tongwei, Xie Dijie, Ren Wenzhe, Zhang Tao. Trajectory Planning of Quadruped Robot Over Obstacle with Single Leg Based on Deep Reinforcement Learning [J]. Journal of System Simulation, 2025, 37(4): 895-909.
[2]	Wen Tingxin, Guan Tingyu. Hybrid Flow Shop Scheduling with Limited Buffers Considering Energy Consumption and Transportation [J]. Journal of System Simulation, 2024, 36(6): 1344-1358.
[3]	Wei Sheng, Wang Yan, Ji Zhicheng. Just-in-time Learning Energy Consumption Predictive Modeling Method in Multi-condition Production Process [J]. Journal of System Simulation, 2024, 36(6): 1378-1391.
[4]	Jiang Changjian, Fan Hu, Luo Tao, Yuan Wen, He Zehao. Completion Time Simulation Prediction Method for Aircraft Assembly Process with Batch and Sortie [J]. Journal of System Simulation, 2024, 36(6): 1404-1413.
[5]	Zhao Yanlin, Tian Yunna. Hyper-heuristic Approach with K-means Clustering for Inter-cell Scheduling [J]. Journal of System Simulation, 2024, 36(4): 941-956.
[6]	Wang Cong, Yu Jiaying, Zhang Hongli. Multi-objective Energy-efficient No-wait Flow Shop Scheduling Based on Hybrid Discrete State Transition Algorithm [J]. Journal of System Simulation, 2024, 36(10): 2345-2358.
[7]	Xiangqian Wang, Puhao Guo, Xiangrui Meng. Simulation and Optimization of Integrated Production Logistics System of Underground Coal Mining, Dressing, and Backfilling [J]. Journal of System Simulation, 2023, 35(5): 907-919.
[8]	Chunmao Jiang, Zhenxing Yang. Partial Task Offloading Strategy of Cloud Robots Based on Game Theory under Cloud-Edge Coordination [J]. Journal of System Simulation, 2023, 35(5): 987-997.
[9]	Hongliang Zhang, Jingru Xu, Bo Tan, Gongjie Xu. Dual Resource Constrained Flexible Job Shop Energy-saving Scheduling Considering Delivery Time [J]. Journal of System Simulation, 2023, 35(4): 734-746.
[10]	Wei Chen, Yan Wang, Zhicheng Ji. Dynamics Modeling and Online Prediction of Energy Consumption of Discrete Manufacturing System [J]. Journal of System Simulation, 2023, 35(4): 760-772.
[11]	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.
[12]	Hongcai Ouyang, Dinghui Wu, Junyan Fan, Jing Wang. Multi-media Energy Planning Optimization of Steel Based on Improved MOEA/D [J]. Journal of System Simulation, 2023, 35(3): 568-578.
[13]	Ni Jing, Ma Mengke. Intercell Dynamic Scheduling Method Based on Deep Reinforcement Learning [J]. Journal of System Simulation, 2023, 35(11): 2345-2358.
[14]	Sen Zhang, Mengyan Zhang, Jingping Shao, Jiexin Pu. Multi-UAVs 3D Path Planning Method Based on Random Strategy Search [J]. Journal of System Simulation, 2022, 34(6): 1286-1295.
[15]	Jianlin Fu, Guofu Ding, Jian Zhang, Haifan Jiang, Peipei Guo. Multi-Objective Optimization Configuration of AGV System Based on Response Surface and NSGA-II [J]. Journal of System Simulation, 2022, 34(5): 994-1002.