Design and implementation of parallel genetic algorithm for cutting stock of circular parts

doi:10.11772/j.issn.1001-9081.2019081397

Abstract

Abstract:

For the cutting stock problem of circular parts which is widely existed in many manufacturing industries， a new parallel genetic algorithm for cutting stock was proposed to maximize the material utilization within a reasonable computing time， namely Parallel Genetic Blanking Algorithm （PGBA）. In PGBA， the material utilization rate of cutting plan was used as the optimization objective function， and the multithread was used to perform the genetic manipulation on multiple subpopulations in parallel. Firstly， a specific individual coding method was designed based on the parallel genetic algorithm， and a heuristic method was used to generate the individuals of population to improve the search ability and efficiency of the algorithm and avoid the premature phenomena. Then， an approximate optimal cutting plan was searched out by adaptive genetic operations with better performance. Finally， the effectiveness of the algorithm was verified by various experiments. The results show that compared with the heuristic algorithm proposed in literature， PGBA takes longer computing time， but has the material utilization rate greatly improved， which can effectively improve the economic benefits of enterprises.

Key words: cutting stock of circular parts, genetic algorithm, parallel computing, heuristic method, dynamic programming method

摘要：

针对制造行业中的圆片下料问题，为了在合理的计算时间内使材料的利用率尽可能高，提出并行遗传下料算法（PGBA），以下料方案的材料利用率作为优化目标函数，将下料方案作为个体，采用多线程的方式对多个子种群并行进行遗传操作。首先，在并行遗传算法的基础上设计特定的个体编码方式，采用启发式方法生成种群的个体，以提高算法的搜索能力和效率，避免早熟现象的发生；然后，采用性能较好的遗传算子进行自适应的遗传操作，搜索出一种近似最优的下料方案；最后，通过多种实验验证算法的有效性。结果表明，与启发式算法相比，PGBA的计算时间有所增加，但材料利用率得到了较大的提高，能有效提高企业的经济效益。

关键词: 圆片下料, 遗传算法, 并行计算, 启发式方法, 动态规划方法

CLC Number:

TP391

Zhiyang ZENG, Yan CHEN, Ke WANG. Design and implementation of parallel genetic algorithm for cutting stock of circular parts[J]. Journal of Computer Applications, 2020, 40(2): 392-397.

曾志阳, 陈燕, 王珂. 圆片下料并行遗传算法的设计与实现[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 392-397.

Figures/Tables 11

Fig. 1 Layout diagrams of X and Y directions

Fig. 2 Crossover of two points and two directions

Fig. 3 Mutation of two points and two directions

Tab. 1 Relevant parameters for random examples

参数	范围	参数	范围	参数	范围
$d i$	100~500	$m$	3~6	$b i$	500~3 000

Tab. 1 Relevant parameters for random examples

参数	范围	参数	范围	参数	范围
$d i$	100~500	$m$	3~6	$b i$	500~3 000

Fig. 4 Average utilization rate of different evolutionary generations

Fig. 5 Average utilization rate of different population sizes

Tab. 2 Parameters setting for examples with different scales

算例	$d i$	$m$	$b i$
1	$100 ~ 500$	$3 ~ 6$	$500 ~ 3 000$
2	$100 ~ 500$	$6 ~ 8$	$1 000 ~ 3 000$
3	$100 ~ 500$	$8 ~ 10$	$3 000 ~ 5 000$
4	$100 ~ 500$	$10 ~ 12$	$5 000 ~ 7 000$

Tab. 2 Parameters setting for examples with different scales

算例	$d i$	$m$	$b i$
1	$100 ~ 500$	$3 ~ 6$	$500 ~ 3 000$
2	$100 ~ 500$	$6 ~ 8$	$1 000 ~ 3 000$
3	$100 ~ 500$	$8 ~ 10$	$3 000 ~ 5 000$
4	$100 ~ 500$	$10 ~ 12$	$5 000 ~ 7 000$

Tab. 3 Running results comparison of examples with different scales

算例	平均利用率/%		并行后平均利用率的变化/%	运行时间/s		并行后缩短的运行时间/s
算例	并行	串行	并行后平均利用率的变化/%	并行	串行	并行后缩短的运行时间/s
1	67.30	67.19	0.11	19.30	32.11	12.81
2	69.91	69.87	0.04	34.82	62.03	27.21
3	68.70	68.64	0.06	56.24	100.78	44.54
4	70.04	69.92	0.12	85.75	160.04	74.29

Tab. 4 Comparison of cutting results of two algorithms

算法	$S$ /m²	$U L$ /%	$T$ /s
$Δ$	1 738	+3.21	+30.43
本文算法	33 650	65.24	36.55
文献［6］算法	35 388	62.03	6.12

Tab. 4 Comparison of cutting results of two algorithms

算法	$S$ /m²	$U L$ /%	$T$ /s
$Δ$	1 738	+3.21	+30.43
本文算法	33 650	65.24	36.55
文献［6］算法	35 388	62.03	6.12

Tab. 5 Relevant parameters of random examples

参数	范围	参数	范围	参数	范围
$d i$	100~500	$m$	8~10	$b i$	3 000~5 000

Tab. 5 Relevant parameters of random examples

参数	范围	参数	范围	参数	范围
$d i$	100~500	$m$	8~10	$b i$	3 000~5 000

Tab. 6 Comparison of cutting results of two algorithms for large-scale examples

算法	$S$ /m²	$U L$ /%	$T$ /s
$Δ$	1 045	+1.25	+40.43
本文算法	56 313	69.04	57.55
文献［6］算法	57 358	67.79	14.50

Tab. 6 Comparison of cutting results of two algorithms for large-scale examples

算法	$S$ /m²	$U L$ /%	$T$ /s
$Δ$	1 045	+1.25	+40.43
本文算法	56 313	69.04	57.55
文献［6］算法	57 358	67.79	14.50

References 14

1	崔耀东.计算机排样技术及其应用［M］.北京：机械工业出版社，2004： 7-9. 10.7763/ijke.2015.v1.17
	CUI Y D. Computer Layout Technology and Its Application［M］. Beijing： China Machine Press， 2004： 7-9. 10.7763/ijke.2015.v1.17
2	秦旭辉.圆形件剪切下料的排样研究［D］.长春：吉林大学， 2014：1-3.
	QIN X H. Layout research of circular piece under the way of blanking［D］. Changchun： Jiling University， 2014： 1-3.
3	杨萌. 布局问题NP难性质的传递路线研究［D］.北京：北京交通大学， 2016： 3-5. 10.18552/2016/scmt4s312
	YANG M. Research on proof transmit path about NP-hardness of cutting and packing problems［D］. Beijing： Beijing Jiaotong University， 2016： 3-5. 10.18552/2016/scmt4s312
4	侯桂玉，崔耀东，黄少丽，等.一种求解圆形件下料问题的启发式算法［J］.计算机工程，2010，36（13）：227-229. 10.3969/j.issn.1000-3428.2010.13.081
	HOU G Y， CUI Y D， HUANG S L， et al. Heuristic algorithm for cutting stock problem of circular item［J］. Computer Engineering， 2010， 36（13）： 227-229. 10.3969/j.issn.1000-3428.2010.13.081
5	陈燕，谢琪琦，刘咏，等.圆形件下料顺序分组启发式算法的设计与实现［J］.图学学报，2017，38（1）：5-9. 10.11996/JG.j.2095-302X.2017010005
	CHEN Y， XIE Q Q， LIU Y， et al. The cutting stock problem of circular items based on sequential grouping heuristic algorithm［J］. Journal of Graphics， 2017， 38（1）： 5-9. 10.11996/JG.j.2095-302X.2017010005
6	王婷婷，崔耀东，陈燕，等.考虑余料生成及利用的圆片下料算法［J］.锻压技术，2019，44（4）：40-47. 10.13330/j.issn.1000-3940.2019.04.007
	WANG T T， CUI Y D， CHEN Y， et al. An algorithm of circular piece cutting stock considering generation and utilization of margin［J］. Forging and Stamping Technology， 2019， 44（4）： 40-47. 10.13330/j.issn.1000-3940.2019.04.007
7	吴阳. 并行遗传退火算法的圆形件下料问题求解［D］. 南宁：广西大学， 2018： 18-26， 30-35.
	WU Y. Parallel genetic annealing algorithm for solving circle piece blanking problems［D］. Nanning：Guangxi University，2018： 18-26， 30-35.
8	许华杰，檀洪森，胡小明.基于自适应遗传算法和多条带策略的排样方法研究［J］.计算机科学，2016，43（4）：274-278， 317. 10.11896/j.issn.1002-137X.2016.4.056
	XU H J， TAN H S， HU X M. Research of packing method based on adaptive genetic algorithm and multi-strip strategy［J］. Computer Science， 2016， 43（4）： 274-278， 317. 10.11896/j.issn.1002-137X.2016.4.056
9	孙佳正，郭骏. 改进的双种群遗传算法在矩形件排样中的应用［J］. 计算机工程与应用， 2018， 54（15）： 139-146. 10.3778/j.issn.1002-8331.1704-0360
	SUN J Z， GUO J. Improved dual population genetic algorithm for rectangle packing［J］. Computer Engineering and Applications， 2018， 54（15）： 139-146. 10.3778/j.issn.1002-8331.1704-0360
10	孟子暄. 基于遗传算法的钣金件下料问题优化研究［J］. 现代工业经济和信息化， 2018 （15）： 24-25. 10.16525/j.cnki.14-1362/n.2018.15.10
	MENG Z X. Research on optimization of sheet metal cutting problem based on genetic algorithm［J］. Modern Industrial Economy and Informationzation， 2018 （15）： 24-25. 10.16525/j.cnki.14-1362/n.2018.15.10
11	李岩，袁弘宇，于佳乔，等. 遗传算法在优化问题中的应用综述［J］. 山东工业技术， 2019（12）： 242-243， 180.
	LI Y， YUAN H Y， YU J Q， et al. Review of genetic algorithm on optimization problems［J］. Shandong Industrial Technology， 2019（12）： 242-243， 180.
12	张立，陈燕，陈秋莲，等. 条带上圆形件的优化排样［J］. 锻压技术， 2018， 43（10）：179-184.
	ZHANG L， CHEN Y， CHEN Q L， et al. Optimized layout of circular pieces on strip［J］. Forging and Stamping Technology， 2018， 43（10）： 179-184.
13	李小莲. 动态规划法的应用分析［J］. 计算机时代， 2019（6）： 53-55. 10.1016/j.comcom.2019.05.023
	LI X L. Analysis of the application of dynamic programming method［J］. Computer Era， 2019（6）： 53-55. 10.1016/j.comcom.2019.05.023
14	CUI Y， TANG T. Parallelized sequential value correction procedure for the one-dimensional cutting stock problem with multiple stock lengths［J］. Engineering Optimization， 2014， 46（10）：1352-1368. 10.1080/0305215x.2013.841903

[1]	ZHANG Wenqiang, XING Zheng, YANG Weidong. Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem [J]. Journal of Computer Applications, 2021, 41(8): 2249-2257.
[2]	ZHANG Meng, GUO Jianquan. Channel structure choice of closed-loop supply chain under uncertain demand and recovery [J]. Journal of Computer Applications, 2021, 41(7): 2100-2107.
[3]	YANG Zhen, MA Jianxiao, WANG Baojie. Signal timing optimization model of dual-ring phase under condition of setting waiting area [J]. Journal of Computer Applications, 2021, 41(7): 2108-2112.
[4]	LI Jin, WANG Feng, YANG Shenyu. Freight routing optimization model and algorithm of battery-swapping electric vehicle [J]. Journal of Computer Applications, 2021, 41(6): 1792-1798.
[5]	LI Shuyi, HAN Xiaolong. Collaborative scheduling of rail-mounted gantry crane and container truck in hybrid operation mode of rail-water intermodal terminal [J]. Journal of Computer Applications, 2021, 41(5): 1506-1513.
[6]	ZHOU Meiling, CHEN Huaili. Fuzzy multi-objective charging scheduling algorithm for electric vehicle based on load balance [J]. Journal of Computer Applications, 2021, 41(4): 1192-1198.
[7]	XIE Wenbo, WEI Yongzhuang, LIU Zhenghong. Parallel implementation and analysis of SKINNY encryption algorithm using CUDA [J]. Journal of Computer Applications, 2021, 41(4): 1136-1141.
[8]	MA Xiaomei, HE Fei. Label printing production scheduling technology based on improved genetic algorithm [J]. Journal of Computer Applications, 2021, 41(3): 860-866.
[9]	WANG Binrong, TAN Dailun, ZHENG Bochuan. Solving auto part spraying sequence by transforming to traveling salesman problem and genetic algorithm [J]. Journal of Computer Applications, 2021, 41(3): 881-886.
[10]	YANG Xianfeng, GUI Hongjun, FU Chunchang. F-X domain predictive filtering parallel algorithm based on compute unified device architecture [J]. Journal of Computer Applications, 2021, 41(2): 486-491.
[11]	HUANG Shuzhao, TIAN Junwei, QIAO Lu, WANG Qin, SU Yu. Unmanned aerial vehicle path planning based on improved genetic algorithm [J]. Journal of Computer Applications, 2021, 41(2): 390-397.
[12]	Yang ZHANG, Xiaoning WANG. Text feature selection method based on Word2Vec word embedding and genetic algorithm for biomarker selection in high-dimensional omics [J]. Journal of Computer Applications, 2021, 41(11): 3151-3155.
[13]	HUANG Xiaoxiang, HU Yongmei, WU Dan, REN Lijie. Early identification and prediction of abnormal carotid arteries based on variational autoencoder [J]. Journal of Computer Applications, 2021, 41(10): 3082-3088.
[14]	YANG Hualong, WANG Meiyu, XIN Yuchen. Inventory routing optimization model with heterogeneous vehicles based on horizontal collaboration strategy [J]. Journal of Computer Applications, 2021, 41(10): 3040-3048.
[15]	WANG Yonghang, ZHANG Tianyu, ZHENG Hongxing. Multi-stage rescheduling method of liner considering severe weather [J]. Journal of Computer Applications, 2021, 41(1): 286-294.