锻压技术

基于束搜索的三阶段约束排样算法

英文标题：An algorithm of three-stage constraint nesting based on beam search

作者：李立平陈秋莲宋仁坤

单位：广西大学

关键词：束搜索三阶段约束排样算法余料

分类号：TG386

出版年,卷(期):页码：2016,41(5):142-145

摘要：

基于矩形件三阶段约束排样问题（CTDC），提出基于束搜索的启发式算法优化排样方式、以快速生成同质块三阶段排样方式。采用动态规划确定段的价值。束搜索是一种剪枝的分支定界算法，节点用局部排样方式和余料来表示，对节点的分支，即填充余料。在每一层上选择高潜力的节点作为精英节点做进一步分支，其他节点直接删除不再回溯，这有利于提高算法效率。实验结果表明：算法生成的三阶段排样方式，排样价值高，切割工艺相对简单，且时间相对合理。

Based on three-stage constraint nesting problem of rectangular part, the optimization nesting type of heuristic algorithm based on beam search was set up and the homogeneous three-stage nesting pattern was produced quickly. Then, the stage value was determined by dynamic programming. Beam search was a kind of pruned branch and bound algorithm. The branch node was presented by the partial nesting pattern and the unused leftover. For branch nodes, namely the leftover was filled. On each level, only the elite nodes were allowed to branch further, and other nodes were directly deleted, which were helpful to improve the efficiency of algorithm. The experimental results show that the beam search algorithm provides a nesting of high value, simple cutting processing and reasonable computational time.

基金项目：

国家自然科学基金资助项目（61363026，71371058）

李立平（1991-），女，硕士研究生陈秋莲（1974-），女，博士，副教授

参考文献：

［1］Cui Y D. Heuristic for two-dimensional homogenous two-segment cutting patterns [J]. Engineering Optimization，2013，45：89-105.
［2］Andrade R，Birgin E G，Morabito R. Two-stage two-dimensional guillotine cutting stock problem with usable leftover[J]. International Federation of Operational Research Societies，2014，23(1)：1-25.
［3］Cui Y D. Heuristic and exact algorithms for generating homogenous constrained three-staged cutting patterns [J]. Computers & Operations Research，2008,35：212-225.
［4］Cui Y D. A new dynamic programming procedure for three-staged cutting patterns [J]. Journal of Global Optimization，2013，55：349-357.
［5］刘睿，严玄，崔耀东. 矩形件带三阶段带排样问题的遗传算法[J]. 计算机工程与应用，2010，46（33）：221-224.Liu R，Yan X，Cui Y D. Genetic algorithm for rectangular three-stage strip packing problem[J]. Computer Engineering and Applications，2010，46（33）：221-224.
［6］Jackob P，Gunther R. Models and algorithms for three-stage two-dimensional bin packing[J]. European Journal of Operational Research, 2007，183：1304-1327.
［7］Cherri， Marcos N，Yanasse，et al. The one-dimensional cutting stock problem with usable leftovers-A survey[J]. European Journal of Operational Research，2014，236：385-402.
［8］Gradisar M, Erjavec J, Tomat L. One-dimensional cutting stock optimization with usable leftover: a case of low stock-to-order ratio [J]. International Journal of Decision Support System Technology，2011，3(1)： 54-66.
［9］Adriana C，Marcos N A. The usable leftover one-dimensional cutting stock problema priority-in-use heuristic [J]. International Federation of Operational Research Societies，2013，20：189-199.
［10］戈鹏，邱厌庆，刘柱胜，等.一刀切问题的优化二叉树排样[J]. 计算机集成制造系统，2011，17（2）：229-337.Ge P，Qiu Y Q，Liu Z S，et al. Optimized binary tree packing of guillotine problem [J]. Computer Integrated Manufacturing Systems，2011，17（2）：229-337.
［11］Hifi M，Rym M，Toufik S. Algorithms for the constrained two-staged two-dimensional cutting problem[J]. Informs Journal on Computing，2008，2：212-221.
［12］Hakim A，Hifi M，Stephane N. An augmented beam search-based algorithm for the circular open dimension problem [J]. Computers & Industrial Engineering，2011，61：373-381.
［13］Mohamed A R，Talel L，Vincent T. Coupling genetic local search and recovering beam search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates [J]. Computers & Operations Research，2012，39：1257-1264.

服务与反馈：

【文章下载】【加入收藏】