Transactions of Materials and Heat Treatment

Title：Optimal nesting of rectangles based on two stage sub-block long board

Authors： Jiang Yongliang1 Zhang Yamin2

Unit： 1. Campus Network Center Hainan Normal University Haikou 571158 China 2. Department of Computer Luohe Medical College Luohe 462002 China

KeyWords： optimal nesting of rectangles dynamic programming algorithm knapsack problems

ClassificationCode：

year,vol(issue):pagenumber：2016,41(1):150-154

Abstract：

To solve the problem of rectangles optimal nesting of the long board in the actual production for enterprises, it was studied the rectangular optimal nesting algorithms, and the optimal nesting algorithm of rectangle based on two stage sub-block long board was put forward. In the first stage, the optimal segmentation of the long board was achieved. In the second stage, the optimal nesting of the rectangle was achieved in the above section. Through the conversion about two stages，the two-dimensional rectangular optimal nesting issues were transformed to the knapsack issues, and the mathematical models were established. The rectangles optimum nesting issues of the long board in the actual production were solved by the application system developed by the dynamic programming algorithm based on branch and bound technique. The application shows that the algorithm is an effective way to solve the rectangular optimal nesting of the long board.

Funds：

国家自然科学基金资助项目(71361008)；海南省重点科技基金资助项目（ZDXM20130080）；海南省自然科学基金资助项目（612136）；河南省基础与前沿技术研究计划资助项目(142300410105)

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

Reference：

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

[2]崔耀东.生成矩形毛坯最优T 形排样方式的递归算法[J].计算机辅助设计与图形学学报, 2006, 18(1):125- 127.

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

[3]季君,陆一平,查建中,等.生成矩形毛坯最优两段排样方式的确定型算法[J].计算机学报,2012, 35 (1):183-191.

Ji J,Lu Y P,Zha J Z,et al. A deterministic algorithm for optimal two-segement cutting patterns of rectangular blanks[J]. Chinese Journal of Computers, 2012, 35 (1):183-191.

[4]季君，邢斐斐,杜钧，等.生成最优同形块两阶段布局方式的确定型算法[J].计算机应用,2014,34(5):1511-1515.

Ji J,Xing F F,Du J,et al. Deterministic algorithm for optimal two-stage cutting layouts with same-shape block[J]. Journal of Computer Applications, 2014,34(5):1511-1515.

[5]潘卫平,陈秋莲，崔耀东，等. 基于匀质条带的矩形件最优三块布局算法[J].图学学报,2015,36(1):7-11.

Pan W P,Chen Q L,Cui Y D,et al. An algorithm for generating optimal homogeneous strips three block patterns of rectangular blanks[J]. Journal of Graphics, 2015,36(1):7-11.

[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]易向阳,仝青山,潘卫平.矩形件二维下料问题的一种求解方法[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.

[8]潘卫平,陈秋莲,崔耀东,等.多板材单一矩形件下料问题的一种求解算法[J]. 锻压技术，2014,39(11):7-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):7-10.

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

[10]Cui Y，Wang Z，Li J. Exact and heuristic algorithms for stage cutting problems[J].Journal of Engineering Manufacture,2005,219:Part B:201-208.

Service：

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