锻压技术

圆形片剪冲下料问题的一种求解算法

英文标题：An algorithm for solving the shearing problem of circular blanks

作者：王峰1 张军2 胡钢3

分类号：

出版年,卷(期):页码：2015,40(10):39-44

摘要：

求解圆形片剪冲下料问题，即解决如何用最少的板材切割出所需的全部圆形片毛坯。本文提出一种生成圆形片条带四块下料方案的确定型算法。首先采用动态规划技术生成排样方式，然后采用基于列生成的线性规划技术迭代调用排样方式生成算法生成下料方案。采用测题将本算法与直切下料算法与T型下料算法进行比较，研究结果表明，本算法生成的下料利用率高于以上两种经典算法。最后通过一个下料实例的解表明：所提出的算法在计算时间和下料利用率两方面都有效。

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.

基金项目：

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

参考文献：

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

服务与反馈：

【文章下载】【加入收藏】