锻压技术

基于同质段矩形优化排样问题求解

英文标题：Solution on rectangular optimal layout based on the homogeneous segments

作者：姜永亮

单位：海南师范大学

分类号：TP391.7

出版年,卷(期):页码：2017,42(5):159-163

摘要：

为有效解决企业实际生产中的矩形优化排样问题,对矩形优化排样算法进行研究，给出基于同质段矩形优化排样问题的求解算法，该算法可同时有效解决企业实际生产中矩形优化排样的单一排样和套裁排样问题。算法首先基于隐式枚举法求出所有同质条带的最优排样及备选同质段，对备选同质段进行规范化处理求出所有的候选同质段，使用候选同质段将板材分成若干个子段，并将矩形优化排样问题转化为完全背包问题，最后基于动态规划算法进行求解。两组应用实例验证了本文算法的有效性。

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.

基金项目：

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

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

参考文献：

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

服务与反馈：

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