Transactions of Materials and Heat Treatment

Title：A heuristic algorithm for two dimensional cutting stock problem based on uniform strip pattern

Authors： Wang Qi Zhang Chunli Gong Ji

Unit： Hebei Finance University Nanning University

KeyWords： two dimensional cutting stock problem constrained packing algorithm column generation uniform strip four-block pattern

ClassificationCode：TP391

year,vol(issue):pagenumber：2017,42(4):63-67

Abstract：

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.

Funds：

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

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

Reference：

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

Service：

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