锻压技术

基于两阶段排样方式的卷材下料算法研究

英文标题：Research on coil cutting algorithm based on the two-stage cutting layout

作者：邓国斌朱强沈萍

分类号：TP391

出版年,卷(期):页码：2017,42(5):185-189

摘要：

讨论矩形件卷材下料问题，采用切割工艺简单的两阶段排样方式采进行下料。这种排样方式采用一组平行于卷材宽度方向的剪切线将卷材切割成多个条带，然后将每个条带切割成所需要的矩形件。首先，构造一种有界背包算法确定矩形件在条带中的优化布局；然后，采用基于列生成的线性规划算法调用上述有界背包算法生成排样方式；最后，采用顺序启发式算法，用当前矩形件剩余需求量反复调用线性规划算法生成各个排样方式，直至每种矩形件剩余需求量均为零，组合各个排样方式形成下料方案。将本文算法与2种文献算法进行比较，计算结果表明，本文算法下料方案比2种文献算法分别节省1.97%和1.66%的卷材。

The problem of rectangles coil cutting was discussed, and the cutting process was carried out by simple two-stage cutting layout. Through this cutting layout, the coil was cut into a variety of strips by a set of shearing lines which were paralleled to the coil width direction, then each strip was cut into desirable rectangles. Firstly, a bounded backpack algorithm was constructed to determine the optimal layout of the rectangles in the strip. Next, the cutting layout was generated by the linear programming algorithm to call the bounded backpack algorithm based on the column generation. Finally, a variety of cutting layout were generated by the sequential heuristic algorithm to repeat call the linear programming algorithm through the remaining demand of current rectangle until zero, and a cutting plan was formed by combining each cutting layout. The results of calculation comparisons between the proposed algorithm and the two literature algorithms show that the proposed algorithm can save 1.97% and 1.66% of the coil, respectively.

基金项目：

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

邓国斌（1976-），男，硕士，讲师朱强（1985-），男，硕士，讲师

参考文献：

［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］He K, Jin Y, Huang W. Heuristics for two-dimensional strip packing problem with 90° rotations [J]. Expert Systems with Applications, 2013, 40(14):5542-5550.
［3］Alvarez-Valdés R, Parreo F, Tamarit J M. Reactive GRASP for the strip-packing problem [J]. Computers & Operations Research, 2008, 35(4): 1065-1083.
［4］Cté J F, Dell'Amico M, Iori M. Combinatorial Benders′ cuts for the strip packing problem [J]. Operations Research, 2014, 62(3): 643-661.
［5］Lodi A, Martello S, Vigo D. Models and bounds for two-dimensional level packing problems [J]. Journal of Combinatorial Optimization, 2004, 8(3): 363-379.
［6］Bettinelli A, Ceselli A, Righini G. A branch-and-price algorithm for the two-dimensional level strip packing problem [J]. 4OR, 2008, 6(4): 361-374.
［7］赵新芳，崔耀东，杨莹，等. 矩形件带排样的一种遗传算法[J]. 计算机辅助设计与图形学学报, 2008, 20(4):540-544.Zhao X F, Cui Y D， Yang Y,et al. A genetic algorithm for the rectangular strip packing problem [J]. Journal of Computer-Aided Design and Computer Graphics，2008, 20(4):540-544.
［8］Cintra G F, Miyazawa F K, Wakabayashi Y, et al. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation [J]. European Journal of Operational Research, 2008, 191(1):61-85.
［9］Mrad M. An arc flow-based optimization approach for the two-stage guillotine strip cutting problem [J]. Journal of the Operational Research Society, 2015, 66(11):1850-1859.
［10］张丽英，贾增耀，苏俭华，等. 液压滚切剪在不同剪切速度下剪切过程数值模拟与实验研究[J]. 塑性工程学报, 2016, 23(5):209-215.Zhang L Y, Jia Z Y, Su J H. Simulation and experimental research on cutting process of hydraulic rolling-cut shear with different cutting speeds [J]. Journal of Plasticity Engineering, 2016, 23(5):209-215.
［11］易向阳, 仝青山, 潘卫平. 矩形件二维下料问题的一种求解方法[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.
［12］Kellerer H，Pferschy U，Pisinger D. Knapsack Problems [M]. Berlin: Springer, 2004.

服务与反馈：

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