Transactions of Materials and Heat Treatment

Title：An algorithm for solving the shearing problem of circular blanks

Authors： Wang Feng1 Zhang Jun2 Hu Gang3

Unit： 1.Hebei Finance University 2.Zhengzhou University of Science & Technology 3.Sichuan Institute of Information Technology

KeyWords： shearing dynamic programming linear programming circular blanks

ClassificationCode：

year,vol(issue):pagenumber：2015,40(10):39-44

Abstract：

Solving the shearing problem of circular blanks is to cut out all the required circular blanks with the least sheet. A deterministic algorithm to generate four-block cutting scheme was put forward. First, the nesting patterns were generated by the dynamic programming technique, and then the cutting scheme was generated by the linear programming technique based on column generation to call pattern generation algorithm. The above algorithm was compared with the direction cutting stock algorithm and T-shaped cutting stock algorithm by the tests. The experimental results show that the cutting stock utilization generated by the above algorithm is higher than that of the two well-known algorithms. Finally, a cutting stock example shows that the algorithm is efficient both in computation time and in cutting stock utilization.

Funds：

王峰（1965-），男，硕士，讲师

Reference：

[1]黄永生，钟贤栋，董华军.集成环境下客车用料优化排样与定额管理[J]. 锻压技术，2014, 39(1)：142-145.

Huang Y S, Zhong X D, Dong H J. Optimal layout and quota management of rail vehicle material underintegration environment[J]. Forging & Stamping Technology,2014, 39(1)：142-145.

[2]潘卫平, 陈秋莲, 崔耀东, 等. 多板材单一矩形件下料问题的一种求解算法[J]. 锻压技术, 2014, 39(11): 6-10.

Pan W P, Chen Q L, Cui Y D, et al. An algorithm for solving problem of multiple plate single rectangle cutting stock[J]. Forging & Stamping Technology, 2014, 39(11): 6-10.

[3]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.

[4]季君. 基于同形块的剪切下料布局算法研究[D]. 北京：北京交通大学, 2012.

Ji J. Research on Guillotine Cutting Stock Packing Algorithm Based on Same-shape Block[D]. Beijing：Beijing Jiaotong University, 2012.

[5]Bennell J A, Oliveira J F. The geometry of nesting problems: A tutorial[J]. European Journal of Operational Research, 2008, 184(2): 397-415.

[6]Cui Y. Generating optimal T-shape cutting patterns for circular blanks[J]. Computers & Operations Research, 2005,32 (1): 143-152.

[7]Kellerer H, Pferschy U, Pisinger D. Knapsack Problems[M].Berlin: Springer, 2004.

[8]Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem[J].Operations Research, 1961,9(6)： 849-859.

[9]Gilmore P C, Gomory R E. A linear programming approach to the cutting stock problem—Part II [J]. Operations Research, 1963, 11(6):863-888.

[10]Furini F, Malaguti E, Durán R M, et al. A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size[J].European Journal of Operational Research, 2012, 218(1):251-260.

Service：

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