Four-Block Layout Algorithm for Two-Dimensional Plate Shearring and Punching of Circular Parts

doi:10.12068/j.issn.1005-3026.2021.11.018

Abstract

Abstract: A cutting stock algorithm based on four-block layout was proposed to solve the two-dimensional plate shearring and punching of circular parts. With this layout， a sheet was divided into four blocks. Only the strips with the same direction and length were arranged in each block， and several rows of the same circular parts were arranged in the strips. A four block layout method for generating circular parts on a single sheet by constructing a layout algorithm. Firstly， the layout of circular parts in the strips was determined. Secondly， recursive algorithm was constructed to generate the layout of the strips in blocks. Finally， implicit enumeration algorithm was used to determine the optimal four-block partition. The column generation algorithm was used to call the above layout algorithm to generate a number of different layouts. Based on the simplex principle， a group of layouts were selected to form the cutting plan， and the decimal solution was rounded. The results showed that the plate utilization ratio of the algorithm in the study is 0.49%， 0.32%， 6.04% and 1.50% higher than those of the four literature algorithms， respectively， and the calculation time can meet the needs of practical applications.

Key words: shearring and punching layout; four-block layout algorithm; recursive algorithm; column generation algorithm; plate; circular part

CLC Number:

TH164

PAN Wei-ping， FAN Zhi-ping， HUANG Min. Four-Block Layout Algorithm for Two-Dimensional Plate Shearring and Punching of Circular Parts[J]. Journal of Northeastern University(Natural Science), 2021, 42(11): 1650-1655.

References

[1]Cui Y.Generating optimal T-shape cutting patterns for circular blanks［J］.Computers & Operations Research，2005，32(1):143-152.
[2]张瑞友，潘卫平，刘士新.基于匀质块五块模式的矩形件非剪切排样算法［J］.东北大学学报(自然科学版)，2018，39(6):771-775.(Zhang Rui-you，Pan Wei-ping，Liu Shi-xin.Non-guillotine cutting algorithm of rectangular items based on five-homogeneous-block mode［J］.Journal of Northeastern University(Natural Science)，2018，39(6):771-775.)
[3]侯桂玉，崔耀东，黄少丽，等.一种求解圆形件下料问题的启发式算法［J］.计算机工程，2010，36(13):227-229.(Hou Gui-yu，Cui Yao-dong，Huang Shao-li，et al.Heuristic algorithm for cutting stock problem of circular item［J］.Computer Engineering，2010，36(13):227-229.)
[4]王峰，张军，胡钢.圆形片剪冲下料问题的一种求解算法［J］.锻压技术，2015，40(10):39-44.(Wang Feng，Zhang Jun，Hu Gang.An algorithm for solving the shearing problem of circular blanks［J］.Forging & Stamping Technology，2015，40(10):39-44.)
[5]Cui Y，Huang B.A heuristic for constrained T-shape cutting patterns of circular items［J］.Engineering Optimization，2011，43(8):867-877.
[6]Cui Y，Gu T，Hu W.A bi-objective guillotine cutting problem of stamping strips of equal circles［J］.International Journal of Computer Mathematics，2010，87(12):2716-2721.
[7]Furini F，Malaguti E.Models for the two-dimensional two-stage cutting stock problem with multiple stock size［J］.Computers & Operations Research，2013，40(8):1953-1962.
[8]Silva E，Alvelos F，Carvalho J.An integer programming model for two-and three-stage two-dimensional cutting stock problems［J］. European Journal of Operational Research，2010，205(3):699-708.
[9]Chen Q，Cui Y，Chen Y.Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns［J］.Optimization Methods and Software，2016，31(1):68-87.
[10]Cui Y，Yao Y，Cui Y P.Hybrid approach for the two-dimensional bin packing problem with two-staged patterns［J］.International Transactions in Operational Research，2016，23(3):539-549.
[11]胡钢，杨瑞，潘立武.基于价值修正的圆片下料顺序启发式算法［J］.图学学报，2016，37(3):337-341.(Hu Gang，Yang Rui，Pan Li-wu.Sequential value correction heuristic algorithm for the circle cutting stock problem［J］.Journal of Graphics，2016，37(3):337-341.)
[12]Cui Y，Wang Q.Exact and heuristic algorithms for the circle cutting problem in the manufacturing industry of electric motors［J］.Journal of Combinatorial Optimization，2007，14(1):35-44.
[13]Birgin E，Lobato R，Morabito R.Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm［J］.Journal of the Operational Research Society，2012，63(2):183-200.
[14]Dolatabadi M，Lodi A，Monaci M.Exact algorithms for the two-dimensional guillotine knapsack［J］.Computers & Operations Research，2012，39(1):48-53.
[15]Pedroso J，Cunha S，Tavares J.Recursive circle packing problems［J］.International Transactions in Operational Research，2016，23(1/2):355-368.
[16]Cui Y.Dynamic programming algorithms for the optimal cutting of equal rectangles［J］.Applied Mathematical Modeling，2005，29(11):1040-1053.
[17]Ozlen M，Burton B，MacRae C.Multi-objective integer programming:an improved recursive algorithm［J］.Journal of Optimization Theory and Applications，2014，160(2):470-482.
[18]杨传民，王树人，王心宇.基于4块结构的斩断切割布局启发性算法［J］.机械设计，2007，24(2):25-26.(Yang Chuan-min，Wang Shu-ren，Wang Xin-yu.Heuristic algorithm on layout of chopped cutting based on 4 pieces of structure［J］.Journal of Machine Design，2007，24(2):25-26.)