锻压技术

基于最优同质块的分段式矩形优化排样

英文标题：Rectangular optimal layout based on segments filled with optimal homogeneous blocks

作者：姜永亮

单位：海南师范大学

分类号：TP391.7

出版年,卷(期):页码：2017,42(7):182-186

摘要：

为有效解决企业实际生产中的矩形优化排样问题，对矩形优化算法进行研究，提出基于最优同质块的分段式矩形优化排样算法，有效解决了企业实际生产中的剪切排样问题。该算法首先使用剪床将板材剪成不同长度的子段，然后在子段上基于最优同质块进行优化排样。算法将板材的分段问题以及最优同质块在子段上的最优排样问题均转化为背包问题，并基于动态规划算法求解；使用枚举法求解最优同质块排样。将板材分成若干个子段使算法可以有效解决长板排样问题，使用最优同质块对子段进行优化排样使算法的优化性能得到提高。两组实例应用表明本文算法优于文献中的其他算法。

To solve the problems of rectangles optimal layout effectively in practical production, the rectangular optimal algorithms were studied, and a rectangular optimal layout algorithm based on segments filled with optimal homogeneous blocks was proposed. So the problem of shear layout in practical production was solved effectively. Firstly, the sheet was cut into different sub-segments by the shearing machine, and then the sub-segments were nested by the optimal homogeneous blocks. Then, both the segmentation problem and the problem of optimal layout of optimal homogeneous blocks on sub-segments were translated into knapsack problems by the algorithm. Based on dynamic programming algorithm, the optimal layout of optimal homogeneous blocks was solved by enumeration algorithm. Therefore, the problems of long board layout were solved by the algorithm dividing the sheet into sub-segments, and the optimization performances of the algorithm were improved by optimizing the sub-segments layout based on optimal homogeneous blocks. Finally, two sets of application examples show that this algorithm is superior to other algorithms in the literature.

基金项目：

国家自然科学基金资助项目(71361008)

作者简介：姜永亮（1980-）,男，硕士，副教授，E-mail：yongliangjiang@126.com

参考文献：

[1]Gilmore P C, Gomory R E. Multistage cutting stock problems of two and more dimentions[J]. Operations Research, 1965, 13(1): 94-120.

[2]何琨,黄文奇,金燕.基于动作空间求解二维矩形Packing问题的高效算法[J].软件学报,2012,23(5):1037-1044.

He K, Huang W Q, Jin Y. Efficient algorithm based on action space for solving the 2D rectangular packing problem[J]. Journal of Software, 2012, 23(5): 1037-1044.

[3]Cui Y D. Recursive algorithm for generating optimal T-shape cutting patterns of rectangular blanks[J]. Journal of Computer-Aided Design & Computer Graphics, 2006, 18(1):125-127.

[4]梁秋月,崔耀东,游凌伟. 应用三块排样方式求解二维下料问题[J].广西师范大学学报:自然科学版,2012,32(3):41-45.

Liang Q Y, Cui Y D, You L W. Solving two-dimensional cutting stock problem with three-block patterns[J]. Journal of Guangxi Normal University: Natural Science Edition, 2012,32(3):41-45.

[5]杨玉丽,崔耀东,许道云.矩形毛坯四块排样方式及其算法[J].微电子学与计算机,2009,26(4):156-158.

Yang Y L, Cui Y D, Xu D Y. An algorithm for generating four-block patterns of rectangular items[J]. Microelectronics & Computer, 2009,26(4):156-158.

[6]Hifi M. Exact algorithms for large scale unconstrained two and three staged cutting problems [J]. Computational Optimization and Applications, 2001,18(1):63-88.

[7]Cui Y. A new dynamic programming procedure for three-staged cutting patterns[J]. Journal of Global Optimization, 2013, 55(2):349-357.

[8]李立平，陈秋莲，宋仁坤. 基于束搜索的三阶段约束排样算法[J].锻压技术,2016,41(5):142-145.

Li L P, Chen Q L, Song R K. An algorithm of three-stage constraint nesting based on beam search[J]. Forging & Stamping Technology, 2016,41(5):142-145.

[9]扈少华,潘立武,管卫利.复合条带三阶段排样方式的生成算法[J]. 锻压技术,2016,41(11):149-152.

Hu S H, Pan L W, Guan W L. A generating algorithm of three-stage nesting patterns for composite strip[J]. Forging & Stamping Technology, 2016,41(11):149-152.

[10]姜永亮,张亚敏.基于两阶段分块式长板矩形优化排样[J]. 锻压技术,2016,41(1):150-154.

Jiang Y L, Zhang Y M. Optimal nesting of rectangles based on two stage sub-block long board [J]. Forging ＆ Stamping Technology, 2016,41(1):150-154.

[11]Cui Y. Dynamic programming algorithms for the optimal cutting of equal rectangles[J]. Applied Mathematical Modelling, 2005, 29(11):1040-1053.

[12]Cui Y D, He D L, Song X X. Generating optimal two-section cutting patterns for rectangular blanks[J]. Computers & Operations Research, 2006, 33(6):1505-1520.

服务与反馈：

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