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]	Hongliang Zhang, Renman Ding, Gongjie Xu. Energy-Efficient Scheduling of Multi-objective Flexible Job Shop Considering Interval Processing Time [J]. Journal of System Simulation, 2022, 34(9): 1976-1987.
[2]	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.
[3]	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.
[4]	Yanqin Long, Guifang Qiao, Guangming Song, Ying Zhang, Linlin Cheng. Motion Simulation and Performance Analysis of 2D Variable Stiffness Snake-like Robot [J]. Journal of System Simulation, 2022, 34(4): 759-767.
[5]	Yan Bai, Lulu Wu, Yin'e He, Yuying Wang. Energy Consumption Prediction for Air-conditioning System Based on Dynamic Temperature Control [J]. Journal of System Simulation, 2022, 34(2): 366-375.
[6]	Hu Rong, Dong Yuming, Qian Bin. Pathfinder Algorithm for Green Pipeline Scheduling with Limited Buffers [J]. Journal of System Simulation, 2021, 33(6): 1384-1396.
[7]	Sun Weiqing, Song He, Han Dong, Tian Kunpeng. Deep Peak-shaving Transformation Planning of Thermal Power Units Based on Approximate Dynamic Programming [J]. Journal of System Simulation, 2021, 33(6): 1415-1426.
[8]	Li Fei, Su Zhong. Intelligent Control of Wastewater Treatment Processes Based on Adaptive Immune Optimization [J]. Journal of System Simulation, 2021, 33(12): 3012-3020.
[9]	Meng Qinglong, Zhang Zhibo, Xiong Cheng. Simulation Research on Operation Effect of VAV Air-conditioning System with Variable Water Temperature Strategy [J]. Journal of System Simulation, 2019, 31(8): 1617-1626.
[10]	Yu Shaozheng, Sun Dongshi, Chen Jing, Li Yongchao. Research on Mechanical Configuration of Automatic Container Terminals Based on Simulation Optimization Method [J]. Journal of System Simulation, 2019, 31(12): 2750-2757.
[11]	Wang Xiuyan, Liu Yanmin, Zhang Gewen, Li Zongshuai, Lin Jiaquan. Prediction of Aircraft Cabin Energy Consumption Based on PSO and CRO Algorithms [J]. Journal of System Simulation, 2018, 30(8): 3074-3081.
[12]	Wang Xiuyan, Liu Yanmin, Zhang Gewen, Li Zongshuai, Lin Jiaquan. Prediction of Aircraft Cabin Energy Consumption Based on Improved Cooperative PSO Neural Network [J]. Journal of System Simulation, 2018, 30(4): 1535-1541.
[13]	Li Jun, LinXuemei, ZhouJie. A Simulation Study of Appointment Rulesin CT Department [J]. Journal of System Simulation, 2018, 30(3): 976-986.
[14]	Hu Kezhen, Wu Jianping, Liu Mingyu. Modelling of EVs Energy Consumption from Perspective of Field Test Data and Driving Style Questionnaires [J]. Journal of System Simulation, 2018, 30(11): 4106-4114.
[15]	Yang Mei, Xu Xiao, Peng Yong, Ju Rusheng, Huang Kedi, Jiao Peng. Research of Partial Synchronization-based Movement Modeling [J]. Journal of System Simulation, 2017, 29(9): 1880-1885.