Transactions of Materials and Heat Treatment

Title：Sequential heuristic algorithm of two-dimensional cutting stock with reducing number of patterns

Authors：

Unit：

KeyWords：

ClassificationCode：TP391

year,vol(issue):pagenumber：2022,47(4):95-100

Abstract：

The two-dimensional cutting stock problem of rectangular parts was discussed, and taking the minimum cost of sheet as the main optimization objective, taking the minimum number of patterns as the secondary optimization objective, a cutting stock algorithm that could reduce the number of patterns was proposed. Then, based on the sequential heuristic framework, the algorithm generated pattern one by one in order to meet the part requirements of the remaining rectangular parts until all the requirements of the rectangular parts were met, and it used a grouping technique to select the rectangular parts that were used to generate the next pattern. Furthermore, after the next pattern was generated by the above rectangular parts, the value of rectangular parts was adjusted according to the sequential value correction method, and each pattern was generated by the dynamic programming program. Finally, the cutting stock algorithm in this paper was compared with the two literature algorithms. The experimental results show that the area of the sheet used by the cutting stock algorithm in this paper is 1.12% and 0.89% less than that of the literature algorithms respectively, and the number of patterns is reduced by 45.56% and 30.79% respectively. However, the calculation time is close to that of the literature algorithms.

Funds：

教育部新一代信息技术创新项目（2020ITA03027）

作者简介：谢东刚（1983-），男，硕士，讲师 E-mail：dgxgygx@163.com 通信作者：唐伟萍（1983-），女，学士，副教授 E-mail：hxnz2002@126.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]刘添乐, 马云龙, 黄嘉蕾, 等. 新型超高强铝锂合金厚板厚度方向组织及性能的不均匀性[J].稀有金属,2020,44(8):785-791.

Liu T L, Ma Y L, Huang J L, et al. Through-thickness inhomogeneity of structures and tensile property in a novel super-high strength Al-Li alloy thick plate[J]. Chinese Journal of Rare Metals, 2020,44(8):785-791.

[3]Erjavec J, Gradisar M, Trkman P. Assessment of stock size to minimize cutting stock production costs[J]. International Journal of Production Economics, 2012, 135(1):170-176.

[4]Cui Y, Zhao Z. Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns[J]. European Journal of Operational Research, 2013, 231(2):288-298.

[5]黎凤洁，崔耀东，陈秋莲. 面向可加工性的卷材优化下料方法 [J]. 锻压技术，2020,45(2):67-72.

Li F J，Cui Y D，Chen Q L. Optimized cutting method of coil for processability [J]. Forging & Stamping Technology，2020,45(2): 67-72.

[6]曾兆敏, 王继红, 管卫利. 二维板材切割下料问题的一种确定性算法[J].图学学报,2016,37(4):471-475.

Zeng Z M, Wang J H, Guan W L. A deterministic algorithm for solving the problem of two-dimensional sheet cutting stock an algorithm of the constrained two-dimensional nesting [J].Journal of Graphics, 2016, 37(4):471-475.

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

[8]Furini F, Malaguti E. Models for the two-dimensional two-stage cutting stock problem with multiple stock size[J]. Computers & Operations Research, 2013, 40(8): 1953-1962.

[9]Furini F, Malaguti E, Thomopulos D. Modeling two-dimensional guillotine cutting problems via integer programming [J]. Informs Journal on Computing, 2016, 28(4):736-751.

[10]黄少丽, 杨剑, 侯桂玉,等. 解决二维下料问题的顺序启发式算法[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.

[11]Chen Q, Cui Y, Chen Y. Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns[J]. Optimization Methods and Software, 2016, 31(1): 68-87.

[12]许雁杰，陈秋莲，陈燕，等. 二维下料问题的顺序按叠分组启发式算法 [J]. 锻压技术，2020,45(9):45-50.

Xu Y J，Chen Q L，Chen Y，et al. Sequential stacking grouping heuristic algorithms of two-dimensional cutting stock problem [J]. Forging & Stamping Technology，2020,45(9): 45-50.

[13]Cui Y, Liu Z. C-sets-based sequential heuristic procedure for the one-dimensional cutting stock problem with pattern reduction[J]. Optimization Methods & Software, 2011, 26(1):155-167.

[14]Imahori S, Yagiura M, Adachi S, et al. Local search algorithms for the two-dimensional cutting stock problem with a given number of different patterns[J]. Operations Research Computer Interfaces Series, 2005, 32(1): 181-202.

Service：

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