锻压技术

基于两阶段分块式长板矩形优化排样

英文标题：Optimal nesting of rectangles based on two stage sub-block long board

作者：姜永亮1 张亚敏2

单位：1.海南师范大学校园网络中心海南海口 571158 2. 漯河医学高等专科学校计算机教研室河南漯河 462002

分类号：

出版年,卷(期):页码：2016,41(1):150-154

摘要：

为了有效解决企业实际生产中的长板矩形优化排样问题，对矩形优化排样算法进行了研究，给出了一个基于两阶分块式长板矩形优化排样算法，该算法在第一阶段完成长板的最佳分段，第二阶段完成矩形在子段上的最优排样。对于两个阶段分别通过问题转化，将二维矩形优化排样问题转化为背包问题，并建立相应的数学模型。根据所建立的数学模型并基于分支定界的动态规划算法开发的应用系统，解决了企业实际生产中的长板矩形优化排样问题。企业实际应用表明，该算法为求解长板矩形优化排样问题的有效方法。

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.

基金项目：

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

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

参考文献：

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

服务与反馈：

【文章下载】【加入收藏】