锻压技术

基于均匀条带排样方式的二维下料启发式算法

英文标题：A heuristic algorithm for two dimensional cutting stock problem based on uniform strip pattern

作者：王祺张春利龚击

单位：河北金融学院南宁学院

分类号：TP391

出版年,卷(期):页码：2017,42(4):63-67

摘要：

条带结构排样方式在机械制造业下料领域有广泛的应用。针对矩形件二维下料问题，提出一种基于均匀条带排样方式的启发式下料算法。下料方案包含多个排样方式，每个排样方式满足部分矩形件的需求量。首先构造均匀条带四块排样方式的约束排样算法；然后采用列生成法反复调用上述约束排样算法生成各个排样方式，直到所有矩形件需求量得到满足为止。采用文献中的基准例题，将本文下料算法和文献中下料算法进行比较，数值实验结果表明本文下料算法能有效地提高板材利用率，且计算时间能满足实际应用要求。

Strip structure pattern was widely used in the field of machinery manufacturing industry. For the problem of two dimensional cutting stock for rectangles, a heuristic algorithm was proposed based on uniform strip pattern. However, the cutting plan included a number of patterns, each of which met the demands of some rectangles. Firstly, the constrained packing algorithm for generated uniform strip four-block pattern was constructed, and then every pattern was generated by applying column generation method to call the constrained packing algorithm repeatedly until all demands of rectangles were met. At last, the literature benchmark instance was applied, and this algorithm was compared with the cutting stock algorithm in literature. The numerical results show that this algorithm can effectively improve the utilization ratio of plates, and the calculation time can meet the requirements of practical application.

基金项目：

广西科学研究与技术开发计划(桂科攻12118017-10A)

王祺（1983-），男，硕士，工程师 E-mail：wqjr96@126.com 通讯作者：龚击（1981-），男，硕士，讲师 E-mail：gxgjxy@163.com

参考文献：

[1]Wscher G, Hauner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3):1109-1130.

[2]Silva E, Alvelos F, Carvalho J M V D. An integer programming model for two- and three-stage two-dimensional cutting stock problems[J]. European Journal of Operational Research, 2010, 205(3):699-708.

[3]Macedo R, Alves C, Carvalho J M V D. Arc-flow model for the two-dimensional guillotine cutting stock problem[J]. Computers & Operations Research, 2010, 37(6):991-1001.

[4]黄少丽, 杨剑, 侯桂玉,等. 解决二维下料问题的顺序启发式算法[J]. 计算机工程与应用, 2011, 47(13):234-237.

Huang S L,Yang J,Hou G Y,et al. Sequential heuristic algorithm for two-dimensional cutting stock problem[J]. Computer Engineering and Applications, 2011, 47(13):234-237.

[5]梁秋月, 崔耀东, 游凌伟. 应用三块排样方式求解二维下料问题[J]. 广西师范大学学报：自然科学版, 2014, 32(3):41-45.

Liang Q Y, Cui Y D, You L W. Solving two-dimensional cutting stock problem with three-block patterns[J].Journal of Guangxi Normal University: Natural Science Edition, 2014, 32 (3): 41-45.

[6]Cui Y, Huang B. Reducing the number of cuts in generating three-staged cutting patterns[J]. European Journal of Operational Research, 2012, 218(2):358-365.

[7]Gramani M C N, Frana P M, Arenales M N. A Lagrangian relaxation approach to a coupled lot-sizing and cutting stock problem[J]. International Journal of Production Economics, 2009, 119(2): 219-227.

[8]Cui Y. Generating optimal T-shape cutting patterns for circular blanks[J]. Computers & Operations Research, 2005, 32(1): 143-152.

[9]Cui Y. Heuristic for the cutting and purchasing decisions of multiple metal coils[J]. Omega, 2014, 46: 117-125.

[10]朱强, 薛峰, 郑仕勇,等. 约束二维排样问题的一种求解算法[J]. 锻压技术, 2016, 41(9):148-152.

Zhu Q, Xue F, Zhen S Y, et al. An algorithm of the constrained two-dimensional nesting [J].Forging & Stamping Technology, 2016, 41 (9):148-152.

[11]Hu T C, Kahng A B. The Knapsack Problem[M]. Berlin: Springer International Publishing, 2016.

[12]王桂兰, 成亚云, 朱龙彪,等. 满足“一刀切”要求的木工板排样优化研究[J]. 工程设计学报, 2014, 21(3):212-216.

Wang G L, Cheng Y Y, Zhu L B, et al. Research on optimum “guillotine cutting ” layout of carpentry board[J]. Chinese Journal of Engineering Design, 2014, 21(3):212-216.

服务与反馈：

【本网站尚未开通全文下载服务】【加入收藏】