Transactions of Materials and Heat Treatment

Title：A heuristic algorithm for twodimensional optimal nesting problem of stamping strips

Authors： Zeng Zhaomin Wang Qi Pan Liwu

Unit： Sichuan Institute of Information Technology Hebei Finance University Henan University of Animal Husbandry & Economy

KeyWords： stamping optimal nesting of strip dynamic programming heuristic algorithm metal plate

ClassificationCode：TP391

year,vol(issue):pagenumber：2018,43(7):204-208

Abstract：

For the optimal nesting problem of strips in plate, a heuristic algorithm was proposed. The basic idea of this heuristic algorithm was to cut a horizontal or vertical strip from the plate with each cut until the plate was cut out, and the direction and width of strip were determined in the process of each cutting by principle of the maximum value of plate nesting. First, the values of strips with all possible dimensions were calculated, and the optimal nesting of parts in the strip was determined by the principle of maximizing strip value. Then, the optimal nesting of strip in plate was generated in order from small to large by the principle of dynamic programming. Furthermore, the above algorithm was compared with multistage nesting algorithm, threeblock nesting algorithm and fourblock nesting algorithm by the benchmark questions in the literature. The results of numerical experiments show that the above algorithm has higher nesting value, and the computation time can meet the needs of practical applications.

Funds：

四川省教育厅科研项目（GZY15C45）

曾兆敏（1974-），女，学士，副教授，E-mail：zengzmsc@163.com；通讯作者：潘立武（1971-），男，博士，高级工程师，E-mail：panlw71@163.com

Reference：

[1]Cui Y. Recursive algorithm for the twodimensional cutting problem of punched strips[J]. Engineering Computations: Int. J. for Computeraided Engineering, 2013, 23(6):587-596.

[2]呼子宇, 杨景明, 侯新培，等. 基于离散差分进化算法的热连轧批量计划优化[J]. 塑性工程学报，2017，24 (3): 148-153．

Hu Z Y, Yang J M, Hou X P, et al. Optimization of hot rolling batch planning based on discrete differential evolution[J]. Journal of Plasticity Engineering, 2017, 24 (3): 148-153.

[3]王祺, 张春利, 龚击. 基于均匀条带排样方式的二维下料启发式算法[J]. 锻压技术, 2017, 42(4):63-67.

Wang Q, Zhang C L, Gong J. A heuristic algorithm for two dimensional cutting stock problem based on uniform strip pattern[J].Forging & Stamping Technology，2017, 42(4):63-67.

[4]姜永亮. 基于最优同质块的分段式矩形优化排样[J]. 锻压技术, 2017, 42(7):182-186.

Jiang Y L. Rectangular optimal layout based on segments filled with optimal homogeneous blocks[J]. Forging & Stamping Technology, 2017, 42(7):182-186.

[5]Cui Y. Exact algorithm for generating two-segment cutting patterns of punched strips[J]. Applied Mathematical Modelling, 2007,31(9): 1865-1873.

[6]李尚芳, 崔耀东, 王晓庆. 冲裁条带最优多段排样方式的动态规划算法[J]. 计算机工程与应用, 2011,47(34)：238-241.

Li S F, Cui Y D, Wang X Q. Dynamic programming algorithm for optimal multiple-segment patterns of punched strips[J].Computer Engineering and Applications, 2011, 47（34): 238-241.

[7]苏兰. 冲裁条带三块排样方式的动态规划算法[J]. 河南师范大学学报: 自然科学版, 2014, 42(6): 143-147.

Su L. Dynamic programming algorithm for three-block cutting patterns of punched strips[J]. Journal of Henan Normal University: Natural Science, 2014, 42(6): 143-147.

[8]潘卫平, 苏兰, 陈秋莲,等. 生成冲裁条带四块排样方式的最优算法[J]. 计算机应用与软件, 2015, 32(10): 253-255.

Pan W P, Su L, Chen Q L, et al. Optimal algorithm for generating four-block layout patterns of blanking strips[J]. Computer Applications and Software, 2015, 32(10): 253-255.

[9]Durak B, Aksu D T. Dynamic programming and mixed integer programming based algorithms for the online glass cutting problem with defects and production targets[J]. International Journal of Production Research, 2017, 55(24): 7398-7411.

[10]Dusberger F, Raidl G R. Solving the 3-staged 2-dimensional cutting stock problem by dynamic programming and variable neighborhood search[J]. Electronic Notes in Discrete Mathematics, 2015, 47: 133-140.

[11]Birgin E G, Lobato R D, Morabito R. Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm[J]. Journal of the Operational Research Society, 2012, 63(2): 183-200.

Service：

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