Transactions of Materials and Heat Treatment

Title：An algorithm of three-stage constraint nesting based on beam search

Authors： Li Liping Chen Qiulian Song Renkun

Unit： Guangxi University

KeyWords： beam search three-stage constrained pattern leftover

ClassificationCode：TG386

year,vol(issue):pagenumber：2016,41(5):142-145

Abstract：

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.

Funds：

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

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

Reference：

［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.

Service：

【This site has not yet opened Download Service】【Add Favorite】