Transactions of Materials and Heat Treatment

Title：Solution on rectangular optimal layout based on the homogeneous segments

Authors： Jiang Yongliang

Unit： Hainan Normal University

KeyWords： rectangular optimal layout standardized treatment candidate homogeneous segments dynamic programming algorithm

ClassificationCode：TP391.7

year,vol(issue):pagenumber：2017,42(5):159-163

Abstract：

In order to solve the problems of rectangular optimal layout effectively in practical production, the rectangular optimal layout algorithms were studied, and the solution algorithm was given based on the homogeneous segments. The above algorithm could effectively solve the single rectangular layout problem and suit cut layout in practical production. Firstly, based on the implicit enumeration method, the optimal layout of all homogeneous strips and the alternative homogeneous segments were calculated. Secondly, all the alternative homogeneous segments were normalized for the candidate homogeneous segments. After the sheet was divided into several subsections with the candidate homogeneous segments, the rectangular optimal layout problem was converted to the complete knapsack problem. Finally, a solution was obtained based on the dynamic programming algorithm. Furthermore, two sets of application examples validated the effectiveness of the algorithm.

Funds：

国家自然科学基金资助项目(71361008)；海南省重点科技项目（ZDXM20130080）

姜永亮（1980-）,男，硕士，副教授

Reference：

［1］Gilmore P C, Gomory R E. Multistage cutting stock problem of two and more dimensions [J].Operations Research,1965,13: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］ Hifi M. Exact algorithms for large scale unconstrained two and three staged cutting problems [J].Computational Optimization and Applications，2001，18:63-88.
［4］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.
［5］梁秋月，崔耀东，游凌伟.应用三块排样方式求解二维下料问题[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，2012，32(3):41-45.
［6］杨玉丽,崔耀东,许道云.矩形毛坯四块排样方式及其算法[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.
［7］Cui Y D，Wang Z，Li J. Exact and heuristic algorithms for stage cutting problems [J].Journal of Engineering Manufacture: Part B, 2005, 219: 201-208.
［8］易向阳，仝青山，潘卫平.矩形件二维下料问题的一种求解方法[J].锻压技术,2015,40(6):149-153.Yi X Y, Tong Q S, Pan W P. A solving method of two-dimensional cutting for the rectangular blank [J]. Forging ＆ Stamping Technology,2015,40(6):149-153.
［9］Agrawal P K. Minimizing trim loss in cutting rectangular blanks of a single size form a rectangular sheet using orthogonal guillotine cuts [J]. European Journal of Operational Research,1993, 64(3):410-422.
［10］崔耀东,张春玲,赵谊.同尺寸矩形毛坯排样的连分数分支定界算法[J].计算机辅助设计与图形学学报,2004,16(2):252-256.Cui Y D, Zhang C L, Zhao Y. A continued fractions and branch-and-bound algorithm for generating cutting patterns with equal rectangles [J].Journal of Computer-Aided Design & Computer Graphics, 2004, 16(2):252-256.
［11］封宇,郑仕勇,易向阳,等. 单一尺寸矩形毛坯下料问题的一种确定性算法[J]. 锻压技术,2016,41(6):156-160.Feng Y, Zheng S Y, Yi X Y, et al. A deterministic algorithm of single-sized rectangular blank cutting [J]. Forging ＆ Stamping Technology, 2016,41(6):156-160.
［12］潘卫平,陈秋莲,崔耀东,等.多板材单一矩形件下料问题的一种求解算法[J]. 锻压技术，2014,39(11):6-10.Pan W P, Chen Q L, Cui Y D, et al. An algorithm for solving problem of multiple plate single rectangle cutting stock [J]. Forging ＆ Stamping Technology,2014,39(11):6-10.

Service：

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