锻压技术

基于匀质块排样方式的多尺寸板材下料算法

英文标题：Blanking algorithm for multiple-size sheets based on homogeneous block layout

作者：向文欣王宏旭潘立武

分类号：TP391

出版年,卷(期):页码：2019,44(7):41-46

摘要：

讨论了矩形件多尺寸板材下料问题：用多种不同规格的板材切割出若干种不同规格的矩形件，在满足每种矩形件的需求量的前提下，使得所用板材总面积最小。提出一种基于匀质块排样方式的下料算法。矩形件在板材上按照匀质块方式排样，每刀都从当前板材上切下一根仅含同种矩形件的条带，连续切下的两根条带的方向互相平行或垂直。首先构造匀质块排样方式的动态规划生成算法，然后构造下料算法调用上述排样算法逐个生成排样方式，直到矩形件的所有需求量均得到满足为止，其中每个排样方式满足矩形件的部分需求量。采用2组文献例题，将本文算法与4种文献算法进行比较，数值实验结果表明：本文算法下料方案板材利用率比文献算法分别提高0.87%，0.57%，0.66%和0.64%。

The rectangular sheet blanking problem with multiple sizes was discussed, and several kinds of rectangular pieces with different specifications were cut from various kinds of sheets. Then, the total area of sheet used was minimized on the premise of meeting the demand of each rectangular piece, and a sheet blanking algorithm based on homogeneous block layout was proposed. The rectangular pieces were laid out on the sheet by the homogeneous block layout method, and each knife cut a strip containing only the same kind of rectangular pieces from the current sheet. Furthermore, the directions of the two strips cut continuously were parallel or vertical to each other. Firstly, the dynamic programming generation algorithm of homogeneous block layout was constructed, and then the sheet blanking algorithm was constructed to generate the layout one by one until all the requirements of rectangular pieces were met, in which each layout met the partial requirements of rectangular pieces. The proposed algorithm and four literature algorithms were compared by two sets of literature instances. The numerical experiment results show that, comparing with the literature algorithms, the sheet utilization ratio of blanking scheme generated by the proposed algorithm is increased by 0.87%, 0.57%, 0.66% and 0.64%, respectively.

基金项目：

全国高等院校计算机基础教育研究会课题（2019-AFCEC-023）；教育部教育管理信息中心十三五教育信息化课题（EMIC201620-110）

向文欣（1986-），女，硕士，讲师，E-mail：wxsc205@163.com；通讯作者：潘立武（1971-），男，博士，副教授，E-mail:panlw71@163.com

参考文献：

[1]扈少华, 潘立武. 矩形件五级剪切排样方式的一种生成算法[J]. 锻压技术, 2018 ,43(10): 190-194.

Hu S H, Pan L W. A generating algorithm for five-level cutting layout pattern of rectangular part[J]. Forging & Stamping Technology, 2018 ,43(10): 190-194.

[2]Melega G M, Araujo D S A, Jans R. Classification and literature review of integrated lot-sizing and cutting stock problems[J]. European Journal of Operational Research, 2018, 271(1): 1-19.

[3]Wscher G, Hauβner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3): 1109-1130.

[4]罗强, 李世红, 袁跃兰, 等. 基于复合评价因子的改进遗传算法求解矩形件排样问题[J]. 锻压技术, 2018, 43(2): 172-181.

Luo Q, Li S H, Yuan Y L, et al. Rectangular workpiece nesting based on an improved genetic algorithm of composite evaluation factor[J]. Forging & Stamping Technology, 2018, 43(2): 172-181.

[5]罗丹. 应用匀质块方式求解两维下料问题的算法研究[D]. 南宁：广西大学, 2013.

Luo D. Solving the Two-dimensional Cutting Stock Problem with Uniform Block Patterns[D]. Nanning: Guangxi University, 2013.

[6]李荣科, 王佳. 基于顺序价值修正算法的矩形件二维优化下料[J]. 锻压技术, 2018, 43(2): 186-190.

Li R K, Wang J. Two-dimensional optimum blanking of rectangular parts based on sequential value correction algorithm[J]. Forging & Stamping Technology, 2018, 43(2): 186-190.

[7]扈少华, 武书彦, 潘立武. 基于两段排样方式的矩形件优化下料算法[J]. 图学学报, 2018, 39(1): 91-96.

Hu S H, Wu S Y, Pan L W. An optimization algorithm for rectangular items cutting stock problem based on two-segment patterns[J]. Journal of Graphics, 2018, 39(1):91-96.

[8]Cintra G F, Miyazawa F K, Wakabayashi Y, et al. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation[J]. European Journal of Operational Research, 2008, 191(1): 61-85.

[9]Malaguti E, Medina Duran R, Toth P. Approaches to Real Wold Two-dimensional Cutting Stock[R]. Bologna, Italy: DEIS-University of Bologna, 2012.

[10]Furini F, Malaguti E, Durán R M, et al. A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size[J]. European Journal of Operational Research, 2012, 218(1): 251-260.

[11]Kellerer H, Pferschy U, Pisinger D. Knapsack Problems [M]. Berlin: Springer, 2004.

[12]Cui Y, Liu Z. C-sets-based sequential heuristic procedure for the one-dimensional cutting stock problem with pattern reduction[J]. Optimization Methods & Software, 2011, 26(1): 155-167.

[13]Cui Y. Generating optimal T-shape cutting patterns for rectangular blanks[J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2004, 218(8): 857-866.

[14]Beasley J E . An exact two-dimensional non-guillotine cutting tree search procedure[J]. Operations Research, 1985, 33(1):49-64.

服务与反馈：

【文章下载】【加入收藏】