计算机工程与应用2017，Vol.53Issue(9)：236-239,257,5.DOI:10.3778/j.issn.1002-8331.1511-0061
二维剪切排样的束搜索启发式算法
Beam search heuristics for two-dimensional guillotine cutting problem
摘要
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分类
信息技术与安全科学引用本文复制引用
陈秋莲,王成栋..二维剪切排样的束搜索启发式算法[J].计算机工程与应用,2017,53(9):236-239,257,5.基金项目
国家自然科学基金(No.61363026,No.71371058). （No.61363026,No.71371058）
