Transactions of Materials and Heat Treatment

Title：Rectangular optimal layout based on segments filled with optimal homogeneous blocks

Authors： Jiang Yongliang

Unit： Hainan Normal University

KeyWords： rectangular optimal layout homogeneous block knapsack problem dynamic programming algorithm enumeration algorithm

ClassificationCode：TP391.7

year,vol(issue):pagenumber：2017,42(7):182-186

Abstract：

To solve the problems of rectangles optimal layout effectively in practical production, the rectangular optimal algorithms were studied, and a rectangular optimal layout algorithm based on segments filled with optimal homogeneous blocks was proposed. So the problem of shear layout in practical production was solved effectively. Firstly, the sheet was cut into different sub-segments by the shearing machine, and then the sub-segments were nested by the optimal homogeneous blocks. Then, both the segmentation problem and the problem of optimal layout of optimal homogeneous blocks on sub-segments were translated into knapsack problems by the algorithm. Based on dynamic programming algorithm, the optimal layout of optimal homogeneous blocks was solved by enumeration algorithm. Therefore, the problems of long board layout were solved by the algorithm dividing the sheet into sub-segments, and the optimization performances of the algorithm were improved by optimizing the sub-segments layout based on optimal homogeneous blocks. Finally, two sets of application examples show that this algorithm is superior to other algorithms in the literature.

Funds：

国家自然科学基金资助项目(71361008)

作者简介：姜永亮（1980-）,男，硕士，副教授，E-mail：yongliangjiang@126.com

Reference：

[1]Gilmore P C, Gomory R E. Multistage cutting stock problems of two and more dimentions[J]. Operations Research, 1965, 13(1): 94-120.

[2]何琨,黄文奇,金燕.基于动作空间求解二维矩形Packing问题的高效算法[J].软件学报,2012,23(5):1037-1044.

He K, Huang W Q, Jin Y. Efficient algorithm based on action space for solving the 2D rectangular packing problem[J]. Journal of Software, 2012, 23(5): 1037-1044.

[3]Cui Y D. Recursive algorithm for generating optimal T-shape cutting patterns of rectangular blanks[J]. Journal of Computer-Aided Design & Computer Graphics, 2006, 18(1):125-127.

[4]梁秋月,崔耀东,游凌伟. 应用三块排样方式求解二维下料问题[J].广西师范大学学报:自然科学版,2012,32(3):41-45.

Liang Q Y, Cui Y D, You L W. Solving two-dimensional cutting stock problem with three-block patterns[J]. Journal of Guangxi Normal University: Natural Science Edition, 2012,32(3):41-45.

[5]杨玉丽,崔耀东,许道云.矩形毛坯四块排样方式及其算法[J].微电子学与计算机,2009,26(4):156-158.

Yang Y L, Cui Y D, Xu D Y. An algorithm for generating four-block patterns of rectangular items[J]. Microelectronics & Computer, 2009,26(4):156-158.

[6]Hifi M. Exact algorithms for large scale unconstrained two and three staged cutting problems [J]. Computational Optimization and Applications, 2001,18(1):63-88.

[7]Cui Y. A new dynamic programming procedure for three-staged cutting patterns[J]. Journal of Global Optimization, 2013, 55(2):349-357.

[8]李立平，陈秋莲，宋仁坤. 基于束搜索的三阶段约束排样算法[J].锻压技术,2016,41(5):142-145.

Li L P, Chen Q L, Song R K. An algorithm of three-stage constraint nesting based on beam search[J]. Forging & Stamping Technology, 2016,41(5):142-145.

[9]扈少华,潘立武,管卫利.复合条带三阶段排样方式的生成算法[J]. 锻压技术,2016,41(11):149-152.

Hu S H, Pan L W, Guan W L. A generating algorithm of three-stage nesting patterns for composite strip[J]. Forging & Stamping Technology, 2016,41(11):149-152.

[10]姜永亮,张亚敏.基于两阶段分块式长板矩形优化排样[J]. 锻压技术,2016,41(1):150-154.

Jiang Y L, Zhang Y M. Optimal nesting of rectangles based on two stage sub-block long board [J]. Forging ＆ Stamping Technology, 2016,41(1):150-154.

[11]Cui Y. Dynamic programming algorithms for the optimal cutting of equal rectangles[J]. Applied Mathematical Modelling, 2005, 29(11):1040-1053.

[12]Cui Y D, He D L, Song X X. Generating optimal two-section cutting patterns for rectangular blanks[J]. Computers & Operations Research, 2006, 33(6):1505-1520.

Service：

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