锻压技术

冲压条带二维优化排样问题的一种启发式算法

英文标题：A heuristic algorithm for twodimensional optimal nesting problem of stamping strips

作者：曾兆敏王祺潘立武

分类号：TP391

出版年,卷(期):页码：2018,43(7):204-208

摘要：

针对条带在板材中的优化排样问题，提出一种启发式算法。这种启发式算法的基本思想是每刀从板材上剪切下一根水平或竖直条带，直至板材被剪切完，并且在每次剪切时按照板材排样价值最大原则确定条带的方向和宽度。首先，计算所有可能尺寸的条带的价值，按照条带价值最大原则确定条带中零件的最优布局。然后，采用动态规划原理按照从小到大顺序依次生成板材上的条带优化排样方式。采用文献中的基准例题，将本文算法与多段排样算法、三块排样算法和四块排样算法进行比较，数值实验结果表明本文算法排样价值更高，并且计算时间可满足实际应用的需要。

For the optimal nesting problem of strips in plate, a heuristic algorithm was proposed. The basic idea of this heuristic algorithm was to cut a horizontal or vertical strip from the plate with each cut until the plate was cut out, and the direction and width of strip were determined in the process of each cutting by principle of the maximum value of plate nesting. First, the values of strips with all possible dimensions were calculated, and the optimal nesting of parts in the strip was determined by the principle of maximizing strip value. Then, the optimal nesting of strip in plate was generated in order from small to large by the principle of dynamic programming. Furthermore, the above algorithm was compared with multistage nesting algorithm, threeblock nesting algorithm and fourblock nesting algorithm by the benchmark questions in the literature. The results of numerical experiments show that the above algorithm has higher nesting value, and the computation time can meet the needs of practical applications.

基金项目：

四川省教育厅科研项目（GZY15C45）

曾兆敏（1974-），女，学士，副教授，E-mail：zengzmsc@163.com；通讯作者：潘立武（1971-），男，博士，高级工程师，E-mail：panlw71@163.com

参考文献：

[1]Cui Y. Recursive algorithm for the twodimensional cutting problem of punched strips[J]. Engineering Computations: Int. J. for Computeraided Engineering, 2013, 23(6):587-596.

[2]呼子宇, 杨景明, 侯新培，等. 基于离散差分进化算法的热连轧批量计划优化[J]. 塑性工程学报，2017，24 (3): 148-153．

Hu Z Y, Yang J M, Hou X P, et al. Optimization of hot rolling batch planning based on discrete differential evolution[J]. Journal of Plasticity Engineering, 2017, 24 (3): 148-153.

[3]王祺, 张春利, 龚击. 基于均匀条带排样方式的二维下料启发式算法[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.

[4]姜永亮. 基于最优同质块的分段式矩形优化排样[J]. 锻压技术, 2017, 42(7):182-186.

Jiang Y L. Rectangular optimal layout based on segments filled with optimal homogeneous blocks[J]. Forging & Stamping Technology, 2017, 42(7):182-186.

[5]Cui Y. Exact algorithm for generating two-segment cutting patterns of punched strips[J]. Applied Mathematical Modelling, 2007,31(9): 1865-1873.

[6]李尚芳, 崔耀东, 王晓庆. 冲裁条带最优多段排样方式的动态规划算法[J]. 计算机工程与应用, 2011,47(34)：238-241.

Li S F, Cui Y D, Wang X Q. Dynamic programming algorithm for optimal multiple-segment patterns of punched strips[J].Computer Engineering and Applications, 2011, 47（34): 238-241.

[7]苏兰. 冲裁条带三块排样方式的动态规划算法[J]. 河南师范大学学报: 自然科学版, 2014, 42(6): 143-147.

Su L. Dynamic programming algorithm for three-block cutting patterns of punched strips[J]. Journal of Henan Normal University: Natural Science, 2014, 42(6): 143-147.

[8]潘卫平, 苏兰, 陈秋莲,等. 生成冲裁条带四块排样方式的最优算法[J]. 计算机应用与软件, 2015, 32(10): 253-255.

Pan W P, Su L, Chen Q L, et al. Optimal algorithm for generating four-block layout patterns of blanking strips[J]. Computer Applications and Software, 2015, 32(10): 253-255.

[9]Durak B, Aksu D T. Dynamic programming and mixed integer programming based algorithms for the online glass cutting problem with defects and production targets[J]. International Journal of Production Research, 2017, 55(24): 7398-7411.

[10]Dusberger F, Raidl G R. Solving the 3-staged 2-dimensional cutting stock problem by dynamic programming and variable neighborhood search[J]. Electronic Notes in Discrete Mathematics, 2015, 47: 133-140.

[11]Birgin E G, Lobato R D, 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.

服务与反馈：

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