Abstract: An algorithm based on beam search heuristics combined with recursions is presented for the constrained two-dimensional guillotine cutting problem, where three stages of orthogonal guillotine cuts are used. The stock plate is divided into segments that are cut into strips that are cut into exact items. Dynamic programming is used for determining the value of segments, simple recursions for the initial value of sub-plates, and the Beam Search（BS） for the cutting pattern. The nodes of the BS are represented by a pair of rectangles, one is the partial solution constructed by segments, and the other is the complementary sub-plate that remains to be filled. Elite nodes are chosen by an evaluation operator that is the sum value of partial solution and the complementary sub-plate. Elite nodes are branched out in the next level, while other nodes are abandoned. Computational results show that the algorithm provides good three-staged homogenous cutting patterns in a short computational time, and remainders are gathered into a large leftover which is easy to use in the next production cycle.

Key words: three-staged cutting pattern, beam search, recursion, leftover, guillotine

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

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