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.
[1] 崔耀东. 计算机排样技术及其应用[M]. 北京:机械工业出版社, 2004:7-9. (CUI Y D. Computer Layout Technology and Its Application[M]. Beijing:China Machine Press,2004:7-9.) [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. (YANG M. Research on proof transmit path about NP-hardness of cutting and packing problems[D]. Beijing:Beijing Jiaotong University,2016:3-5.) [4] 侯桂玉, 崔耀东, 黄少丽, 等. 一种求解圆形件下料问题的启发式算法[J]. 计算机工程, 2010, 36(13):227-229.(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.) [5] 陈燕, 谢琪琦, 刘咏, 等. 圆形件下料顺序分组启发式算法的设计与实现[J]. 图学学报, 2017, 38(1):5-9.(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) [6] 王婷婷, 崔耀东, 陈燕, 等. 考虑余料生成及利用的圆片下料算法[J]. 锻压技术, 2019, 44(4):40-47.(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.) [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. (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.) [9] 孙佳正, 郭骏. 改进的双种群遗传算法在矩形件排样中的应用[J]. 计算机工程与应用,2018,54(15):139-146. (SUN J Z, GUO J. Improved dual population genetic algorithm for rectangle packing[J]. Computer Engineering and Applications,2018,54(15):139-146.) [10] 孟子暄. 基于遗传算法的钣金件下料问题优化研究[J]. 现代工业经济和信息化,2018(15):24-25. (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.) [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. (LI X L. Analysis of the application of dynamic programming method[J]. Computer Era,2019(6):53-55.) [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.
2020, Vol. 40 
