锻压技术

矩形件剪切下料问题的一种顺序价值修正算法

英文标题：A sequential value correction algorithm for cutting stock problem of rectangular part

作者：沈萍邓国斌

单位：广西职业技术学院

分类号：TP391

出版年,卷(期):页码：2018,43(4):180-184

摘要：

针对矩形件剪切下料问题，提出一种基于顺序价值修正策略的优化下料算法。首先构造普通块排样方式的生成算法，生成矩形件在单张板材上的排样方式。然后采用顺序价值修正算法，调用上述排样算法，逐个生成排样方式，每个排样方式满足部分矩形件的需求量，直到所有矩形件的需求量均被满足为止，在生成每个排样方式后按照一定规则修正这个排样方式中矩形件的价值。最后将上述顺序价值修正算法迭代执行多次得到多个下料方案，选择耗费板材张数最少的作为最终解。使用基准例题将本文算法与两种文献算法进行对比实验，结果表明，本文算法在节省板材方面优于两种文献算法，且计算时间合理。

For the cutting stock shearing problem of rectangular part, an optimal cutting stock algorithm based on sequential value correction strategy was proposed. Firstly, the generation algorithm of ordinary nesting type was constructed, and the nesting type of rectangular part on single plate was generated. Then, by the sequential value correction algorithm, the above algorithm was invoked to generate nesting types one by one, and every nesting type met the demands of some rectangular parts, the operation was terminated until the demands of all rectangular parts were satisfied. After generating every nesting type, the value of rectangular part in this nesting type was corrected according to a certain rule. Finally, the above sequential value correction algorithm was executed and iterated repeatedly to obtain multiple cutting stock plans, and the cutting stock plan which consumed the minimum number of plates was chosen as the final solution. The algorithm was compared with two algorithms from literatures by benchmark examples. The results show that the proposed algorithm is superior to two algorithms from literatures in term of saving plates and reasonable calculation time.

基金项目：

广西自然科学基金资助项目（2015GXNFBA139264）；广西教育厅科研项目（KY2016YB610）

沈萍（1974-），女，硕士，实验师；E-mail：jsgxdgb@163.com

参考文献：

[1]Silva E, Oliveira J F, Wscher G. 2DCPackGen: A problem generator for two-dimensional rectangular cutting and packing problems[J]. European Journal of Operational Research, 2014, 237(3): 846-856.

[2]Andrade R, Birgin E G, Morabito R. Two-stage two-dimensional guillotine cutting stock problems with usable leftover[J]. International Transactions in Operational Research, 2016, 23(1):121-145.

[3]姜永亮. 基于最优同质块的分段式矩形优化排样[J]. 锻压技术, 2017, 42(7):182-186.

Jiang Y L. Rectangular optimal layout based on segments filled with optimal homogeneous blocks[J]. Forging & Stamping Technology, 2017, 42(7):182-186.

[4]Polyakovsky S, M′Hallah R. An agent-based approach to the two-dimensional guillotine bin packing problem[J]. European Journal of Operational Research, 2009, 192(3): 767-781.

[5]Charalambous C, Fleszar K. A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts[J]. Computers & Operations Research, 2011, 38(10): 1443-1451.

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

[7]易向阳, 仝青山, 潘卫平. 矩形件二维下料问题的一种求解方法[J]. 锻压技术, 2015, 40(6):150-153.

Yi X Y, Tong Q S, Pan W P. A solving method of two-dimensional cutting for the rectangular blanks [J].Forging & Stamping Technology, 2015, 40(6):150-153.

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

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

[9]Kellerer H，Pferschy U，Pisinger D. Knapsack Problems[M]. Berlin: Springer, 2004.

[10]胡钢, 杨瑞, 潘立武. 基于价值修正的圆片下料顺序启发式算法[J]. 图学学报, 2016, 37(3):337-341.

Hu G, Yang R, Pan L W. Sequential value correction heuristic algorithm for the circle cutting stock problem[J]. Journal of Graphics, 2016, 37(3):337-341.

[11]Belov G, Scheithauer G, Mukhacheva E A. One-dimensional heuristics adapted for two-dimensional rectangular strip packing[J]. Journal of the Operational Research Society, 2008, 59(6):823-832.

[12]呼子宇, 杨景明, 侯新培，等. 基于离散差分进化算法的热连轧批量计划优化[J]. 塑性工程学报，2017，24 (3): 148-153.

Hu Z Y, Yang J M, Hou X P, et al. Optimization of hot rolling batch planning based on discrete differential evolution[J]. Journal of Plasticity Engineering, 2017, 24 (3): 148-153.

[13]Mahori S, Yagiura M, Umetani S, et al. Local Search Algorithms for the Two-dimensional Cutting Stock Problem with a Given Number of Different Patterns[M]. US: Springer, 2005.

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

服务与反馈：

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