Transactions of Materials and Heat Treatment

Title：Blanking algorithm for multiple-size sheets based on homogeneous block layout

Authors： Xiang Wenxin Wang Hongxu Pan Liwu

Unit： Sichuan Vocational College of Information Techology Henan University of Animal Husbandry & Economy

KeyWords： blanking problem for multiple-size sheets homogeneous block layout blanking algorithm strip rectangular piece

ClassificationCode：TP391

year,vol(issue):pagenumber：2019,44(7):41-46

Abstract：

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.

Funds：

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

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

Reference：

[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.

Service：

【This site has not yet opened Download Service】【Add Favorite】