锻压技术

可减少排样方式数的二维下料顺序启发式算法

英文标题：Sequential heuristic algorithm of two-dimensional cutting stock with reducing number of patterns

分类号：TP391

出版年,卷(期):页码：2022,47(4):95-100

摘要：

讨论矩形件二维下料问题，将板材成本最小作为主要优化目标，将排样方式数最少作为辅助优化目标。提出一种可减少排样方式数的下料算法。该算法基于顺序启发式框架，按顺序逐个产生排样方式满足剩余矩形件的部分需求量，直到矩形件的所有需求量均得到满足为止。它采用一种分组技术选择可用来生成下一个排样方式的矩形件，用这些矩形件生成下一个排样方式后根据顺序价值校正方法调整矩形件的价值，其中每个排样方式均采用动态规划程序生成。将本文下料算法与两种文献算法进行对比，实验结果表明，本文下料算法使用的板材面积比文献算法分别节省了1.12%和0.89%，排样方式数比文献算法分别减少了45.56%和30.79%，且计算时间与文献算法接近。

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.

基金项目：

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

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

服务与反馈：

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