第41卷第12期 Vol. 41No. 12
爱压技术银
FORGING & STAMPING TECHNOLOGY
匀质条带五块布局方式及其生成算法
青巧，李静2，管卫利3
2016年12月 Dec.2016
（1.四川邮电职业技术学院计算机科学系，四川成都610067：2.郑州市电子信息工程学校，河南郑州450007：
3.南宁学院信息工程学院，广西南宁530200）
摘要：针对矩形毛坏无约束二维布局间题，提出一种勾质条带五块布局方式。这种布局方式将板材划分为5个矩形块，每个块由包含同种毛坏的匀质条带组成。构造五块布局方式的生成算法：首先采用动态规划方法生成所有可能尺寸的块中匀质条带的最优布局；然后采用隐式枚举和分支定界技术考察板材所有可能的五块划分方式，按照板材布局价值最大原则确定板材的最优五块划分，得到最终的五块布局方式图。数值实验结果表明，这种算法能有效地提高板材布局价值。
关键词：无约束二维布局；五块布局方式；动态规划；陷式枚举；勾质条带 DOI: 10. 13330/j. issn. 1000-3940. 2016. 12. 006
中图分类号：TP391
文献标识码：A
文章编号：1000-3940（2016）12-0037-05
An algorithm of generating five block layout on uniform strip
Qing Qiao', Li Jing, Guan Weili?
(1. Department of Computer Science, Sichuan Post and Telecommunications College, Chengdu 610067, China;
2. Zhengzhou Electronic and Information Engineering Sechool, Zhengzhou 450007 , China ; 3. Information Engineering College, Nanning University , Nanning 530200, China)
Abstract : For the problem of two-dimensional layout without constraint on the rectangular blank, the five block layout on the uniform strip was put fonward, and the blank was divided into five rectangular blocks, which were composed of uniform strips containing the same blanks respectively. Nest, generation algorithm of this layout was constructed. Firstly, the optimal layouts of uniform strips on all possible size blocks were generated by dynamic programming method. Then, all possible five block layouts were investigated by implicit enumera tion and branch and bound techniques. Furthermore, the optimal five block layout was oonfirmed and obtained based on the maximum principle of the blank layout value, Numerical experiment results show that this algorithm can effectively improve the value of the blank layout.
Key words : two dimensional layout without eonstraint; five block layout; dynamic progamming; implicit enumeration; uniform strip
钣金加工中主要有4种下料方式，分别是剪床下料、激光下料、冲床下料以及数控下料。数控下料由于具有节省工序、精度高、操作方便等优点，自前应用最为广泛。矩形毛坏环无约束二维布局( Rectangle Unconstrained Two Dimensional Layout,
问题是数控下料的核心子问题，在计算理
RUTDL）
论上属于NP难度组合优化间题范畴[1-3]
给定一张长为L、宽为W的板材和m种矩形毛收稿日期：20160922；修订日期：20161110
基金项目：广西科学研究与技术开发计划（佳科攻11107006-13；桂科攻1211801710A）
作者筒介：青巧（1972），女，额士，高级工程师 E-mail: qqiaose@ 163. com
通讯作者：管卫利（1979-），男，额士，副数授万方数据ail：gwlnn2001@126.com
坏，每种毛坏的长、宽、价值分别为}，"，c（i=1,2，"",m），RUTDL问题是指寻找矩形毛坏在板材上的优化布局方式，使得按照这个布局方式在板材上切割出的毛坏总价值最大。合理的布局方式必须满足：（1）板材上的任意两个毛坏不能相互重叠；（2）毛坏必须排放在板材内部，不能超出板材边界；（3）每个毛坏至少有一条边与板材的边平行。构造一个好的RUTDL问题求解算法，可以有效地提升板材布局价值，降低企业生产成本[4]。
目前，针对RUTDL问题主要存在两类求解方法：精确解法和启发式解法。文献【5］提出了基于0-1整数规划模型的树搜索算法，采用0=1变量表示毛坏在板材上的坐标位置，运用拉格朗日松弛技术和次梯度优化技术确定树搜索的界。文献[6］提出了基于0-1线性规划模型的分支定界算