锻压技术

多线材变截面一维下料问题解法研究

英文标题：Study on the solution of one-dimensional cutting stock for multiple stock lengths with variable cross-section

作者：曹静静崔耀东李东兴

单位：广西大学

分类号：TG314

出版年,卷(期):页码：2017,42(1):161-164

摘要：

针对多线材变截面一维下料问题，提出顺序价值修正和动态规划算法求解。由于材料具有变截面的特征，同样重量的毛坯在线材不同位置切割时所需的长度是不同的，所以要进行重量与长度的转换，求出任意位置处对应的毛坯长度。然后根据上述方法顺序生成下料方案中的各个布局图，直到全部毛坯的需求得到满足。通过对毛坯的价值修正生成多个不同的下料方案，从中选择最好者作为解。通过与随机测试题比较，实验结果表明，所得解值非常接近最优，当用材料利用率度量时，最优解的材料利用率和所得解的平均利用率之差为0.51%；计算速度很快，通常在7 s以内，该算法更能快速生成布局图，提高材料利用率。

For the problem of one-dimensional cutting stock for multiple stock lengths with variable cross-section, the sequential value correction and dynamic programming algorithm were proposed. Because the material was of variable cross-section characteristics, the stock length of cutting was varied at different positions under the same weight. Therefore, the conversion of weight and length must be carried out, and the stock length in the corresponding position was obtained. Then, according to the above method, the cutting patterns were generated sequentially, until all demands were met. Furthermore, multiple cutting plans were generated by adjusting the item values, and the best was selected among them. Comparing with random test, the experimental results indicate that the obtained solution is very close to the optimal solution. When the material utilization is measured, the difference between the material utilization rate of the optimal solution and the average utilization rate of the obtained solution is 0.51%, and computing speed is usually quick within seven seconds. Thus, the proposed approach can generate cutting patterns quickly and improve material utilization.

基金项目：

国家自然科学基金资助项目(61363026)；广西自然科学基金资助项目(2014GXNSFAA118357)

曹静静（1989-），女，硕士研究生 E-mail：jingjcao@126.com 通讯作者：崔耀东（1957-），男，博士，教授 E-mail：ydcui@263.net

参考文献：

[1]崔耀东. 计算机排样技术及其应用[M]. 北京: 机械工业出版社, 2004.

Cui Y D. Computer Nesting Technology and Its Application [M]. Beijing: China Machine Press, 2004.

[2]汤金春，王培珍. 基于遗传算法的钢锭配切优化 [J]. 安徽工业大学学报：自然科学版, 2012, 29(1):67-69.

Tang J C, Wang P Z. Optimization of steel ingot cutting and matching based on genetic algorithm [J]. Journal of Anhui University of Technology: Natural Science Edition, 2012, 29(1):67-69.

[3]Furini F, Malaguti E, Duran R M, et al. A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size [J]. European Journal of Operational Research, 2010, 218(1): 251-260.

[4]Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems [J]. Mathematical Programming, 1999, 86 (3): 565-594.

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

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

[7]Belov G, Scheithauer G. Setup and open-stacks minimization in one-dimensional stock cutting [J]. Informs Journal on Computing, 2007, 19 (1): 27-35.

[8]Mukhacheva E A, Belov G N, Kartack V M, et al. Linear one-dimensional cutting-packing problems: Numerical experiments with the sequential value correction method (SVC) and a modified branch-and-bound method (MBB) [J]. Pesquisa Operacional, 2000, 20(2):153-168.

[9]Andonov R, Poirrez V, Rajopadhye S. Unbounded knapsack problem: Dynamic programming revisited [J]. European Journal of Operational Research, 2000, 123(2): 394-407.

[10]Cui Y. Dynamic programming algorithms for the optimal cutting of equal rectangles [J]. Applied Mathematical Modelling, 2005, 29(11):1040-1053.

[11]Cui Y, Gu T L. A computational improvement to the dynamic programming algorithm for the optimal cutting of equal rectangles [J]. International Journal of Information and Management Sciences, 2009, 20: 453-458.

[12]Cui Y P, Tang T B. Parallelized sequential value correction procedure for the one-dimensional cutting stock problem with multiple stock lengths [J]. Engineering Optimization, 2014, 46(10):1352-1368.

[13]刘林, 刘心报, 包海飞, 等. 多型材变截面一维下料问题研究[J]. 仪器仪表学报, 2009, 30(6):446-450.

Liu L, Liu X B, Bao H F, et al. A study on the one-dimensional cutting stock problem with stocks of many models and variable-section based on heuristic [J]. Journal of Instrument and Meter, 2009, 30(6):446-450.

服务与反馈：

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