Transactions of Materials and Heat Treatment

Title：A cutting stock algorithm of heterogeneous rectangular pieces based on Tshaped layout

Authors： Hu Gang Zhang Chunli Pan Liwu

Unit： Sichuan Institute of Information Technology Hebei Finance University Henan University of Animal Husbandry & Economy

KeyWords： cutting stock problem Tshaped layout column generation algorithm constrained layout algorithm heterogeneous rectangle

ClassificationCode：TP391

year,vol(issue):pagenumber：2017,42(6):180-185

Abstract：

The cutting stock problem of heterogeneous rectangular pieces was discussed, and an optimization cutting algorithm based on Tshaped layout was proposed. Firstly, a constrained layout algorithm was constructed to generate the Tshaped layout of rectangular pieces on the single sheet. Then, the column generation algorithm was used to generate a virtual cutting plan according to the current remaining demand of rectangular pieces, partial layouts was admitted into actual cutting plan according to the rule that no redundant rectangular pieces was generated, and the current remaining demand of rectangular pieces was updated. The above steps were repeated until the remaining demand of rectangular pieces was zero. Comparing the proposed algorithm with three algorithms in the literature through benchmark instances, the results of numerical experiments show that the proposed algorithm can save sheets by 3.93%, 1.27% and 1.17% respectively.

Funds：

河南省科技厅科技攻关项目(152102210320)；河南省高等学校重点科研项目(15B52000)

胡钢（1982-），男，学士，讲师潘立武（1971-），男，博士，副教授

Reference：

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

［3］Clautiaux F, Jouglet A, Hayek J E. A new lower bound for the nonoriented twodimensional binpacking problem [J]. Operations Research Letters, 2007, 35(3):365-373.

［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］Monaci M, Toth P. A setcoveringbased heuristic approach for binpacking problems[J]. Informs Journal on Computing, 2006, 18(1): 71-85.

［6］Chan T M, Alvelos F, Silva E, et al. Heuristics with stochastic neighborhood structures for twodimensional bin packing and cutting stock problems[J]. AsiaPacific Journal of Operational Research, 2011, 28(2): 255-278.

［7］Mack D, Bortfeldt A. A heuristic for solving large bin packing problems in two and three dimensions[J]. Central European Journal of Operations Research, 2012, 20(2):337-354.

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

［9］Fleszar K. Three insertion heuristics and a justification improvement heuristic for twodimensional bin packing with guillotine cuts[J]. Computers & Operations Research, 2013, 40(1):463-474.

［10］朱强, 薛峰, 郑仕勇, 等. 约束二维排样问题的一种求解算法[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.

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

［12］Berkey J O, Wang P Y. Twodimensional finite binpacking algorithms[J]. Journal of the Operational Research Society, 1987, 38(5): 423-429.

［13］Lodi A, Martello S, Vigo D. Heuristic and metaheuristic approaches for a class of twodimensional bin packing problems[J]. Informs Journal on Computing, 1999, 11(4): 345-357.

Service：

【This site has not yet opened Download Service】【Add Favorite】