锻压技术

基于多段排样方式的卷材二维剪切下料算法

英文标题：Two-dimensional cutting stock algorithm of coil based on multi-segment layout

作者：邓国斌沈萍潘立武

分类号：TP391

出版年,卷(期):页码：2019,44(9):46-50

摘要：

讨论了卷材二维剪切下料问题，即使用宽度固定、长度可变的卷材剪切出若干种不同尺寸和数量的矩形件，优化目标为最大化卷材利用率。下料过程分3个阶段:第1阶段将卷材切成段，第2阶段将段切成条带，第3阶段将条带切成矩形件。提出一种基于多段排样方式的下料算法，首先采用动态规划算法分别生成矩形件在条带中的优化布局和条带在段中的优化布局，然后采用顺序启发式算法得到段在卷材中的优化布局。采用文献例题，将本文算法与3种文献算法进行比较，数值实验结果表明：本文算法生成的剪切下料方案的材料利用率比文献算法分别高2.39%、0.69%和0.46%，且平均每道例题计算时间均在3 s内。

Two-dimensional cutting stock problem of coil was discussed, namely, several rectangular parts of different sizes and quantities were cut from the coil with fixed width and variable length, and the optimization goal was to maximize the material utilization ratio of coil. The cutting process was divided into three stages. The first stage was to cut the coil into segments, the second stage was to cut segments into strips, and the third stage was to cut strips into rectangular parts. Then, the cutting algorithm based on multi-segment layout was proposed. Firstly, the optimal layout of rectangular parts on strips and strips on segments were generated by the dynamic programming algorithm respectively, and then, the optimal layout of segments on coil was obtained by the sequential heuristic algorithm. Furthermore, the literature instances were adapted, and the above algorithms were compared with three literature algorithms. The numerical experiment results show that the material utilization ratios of the cutting stock plan generated by the above algorithms are 2.39%, 0.69% and 0.46% higher than that of the literature algorithms respectively, and the average calculation time of each instance is within 3 s.

基金项目：

广西教育厅科研项目（KY2016YB610）；广西高校中青年教师基础能力提升项目（2018KY0954）

邓国斌（1976-），男，硕士，副教授 E-mail：jsgxdgb@163.com 通讯作者：潘立武（1971-），男，博士，高级工程师 E-mail：panlw71@163.com

参考文献：

［1］崔耀东. 计算机排样技术及其应用
［M］. 北京：机械工业出版社，2004.

Cui Y D. Computer Packing Technology and Its Application
［M］. Beijing: China Machine Press, 2004.

［2］Trespalacios F, Grossmann I E. Symmetry breaking for generalized disjunctive programming formulation of the strip packing problem
［J］. Annals of Operations Research, 2017, 258(2): 747-759.

［3］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.

［4］Hifi M, Roucairol C. Approximate and exact algorithms for constrained (un) weighted two-dimensional two-staged cutting stock problems
［J］. Journal of Combinatorial Optimization, 2001, 5(4): 465-494.

［5］Cui Y. Generating optimal T-shape cutting patterns for rectangular blanks
［J］. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2004, 218(8): 857-866.

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

［7］王祺, 张春利, 龚击. 基于均匀条带排样方式的二维下料启发式算法
［J］. 锻压技术, 2017, 42(4):63-67.

Wang Q, Zhang C L, Gong J. A heuristic algorithm for two dimensional cutting stock problem based on uniform strip pattern
［J］. Forging & Stamping Technology，2017, 42(4):63-67.

［8］邓国斌, 朱强, 沈萍. 基于两阶段排样方式的卷材下料算法研究
［J］. 锻压技术, 2017, 42(5): 185-189.

Deng G B, Zhu Q, Shen P. Research on coil cutting algorithm based on the two-stage cutting layout
［J］. Forging & Stamping Technology，2017, 42(5): 185-189.

［9］朱强, 薛峰, 李碧青. 硅钢卷材二维剪切下料问题的一种求解算法
［J］. 变压器, 2018,55(3): 18-20.

Zhu Q, Xue F, Li B Q. An algorithm for 2D guillotine cutting stock problem of silicon steel coil
［J］.Transformer, 2018,55(3): 18-20.

［10］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.

［11］Kellerer H, Pferschy U, Pisinger D. Knapsack Problems
［M］. Berlin: Springer, 2004.

［12］Cui Y P, Cui Y, Tang T. Sequential heuristic for the two-dimensional bin-packing problem
［J］. European Journal of Operational Research, 2015, 240(1): 43-53.

服务与反馈：

【本网站尚未开通全文下载服务】【加入收藏】