二维剪切排样的束搜索启发式算法

来源：计算机工程与应用杂志2017年第9期北京时间：

作者：陈秋莲1，2，王成栋2

单位：1.华南理工大学 工商管理学院，广州 510640；2.广西大学 计算机与电子信息学院，南宁 530004

摘要：针对约束二维矩形剪切排样问题，提出了一种基于束搜索的三阶段剪切排样算法。其切割过程包括三个阶段：板材剪切成段，段剪切成条带，条带切割成准确尺寸毛坯。采用动态规划确定段的价值，复杂度低的拼接递推不同长度子板的初始价值和板材的初始可行解，束搜索优化板材的排样方式。束搜索的节点用矩形对表示，分别是段组合而成的局部方式和未填充的剩余子板。以局部方式价值与剩余子板的初始价值之和作为节点的估计值。按估计值选择精英节点继续分支，其他节点直接删除不再回溯。实验结果表明该算法可缩短三阶段同质排样的计算时间，且所获得的余料大，利于余料的回收管理和再利用。

关键词：三阶段排样方式,束搜索,递推,余料,剪切