|
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.
|
|
［1］Wscher G, Hauner 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, Parreo F, Tamarit J M. Reactive GRASP for the strip-packing problem [J]. Computers & Operations Research, 2008, 35(4): 1065-1083.
［4］Cté 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.
|
Copyright Forging & Stamping Technology.All rights reserved