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

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