Transactions of Materials and Heat Treatment

Title：Two-dimensional cutting stock algorithm of coil based on multi-segment layout

Authors： Deng Guobin Shen Ping Pan Liwu

Unit： Guangxi Vocational & Technical College Henan University of Animal Husbandry and Economy

KeyWords： two-dimensional cutting stock problem of coil multi-segment layout dynamic programming sequential heuristic algorithm rectangular part

ClassificationCode：TP391

year,vol(issue):pagenumber：2019,44(9):46-50

Abstract：

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.

Funds：

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

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

Reference：

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

Service：

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