锻压技术

可限定级数的单一矩形件多级排样精确算法

英文标题：Accurate algorithm of multi-section layout for single rectangular part with limited sections

单位：1.广西电力职业技术学院汽车与交通工程学院 2.广西农业职业技术大学信息与机电工程系 3.川北幼儿师范高等专科学校美术系

分类号：TP391

出版年,卷(期):页码：2021,46(12):74-78

摘要：

讨论单一矩形件排样问题，即用长度为L宽度为W的板材切割出长度为l宽度为w的矩形件，优化目标是使得切割出的矩形件的数量最多。提出一种可限定级数的多级排样方式及其精确生成算法。该排样方式将板材划分为多个级，每个级中排放方向相同的矩形件，相邻级中矩形件的方向互相垂直。首先,采用隐式枚举法确定所有可能尺寸的级中最多可以排放的矩形件个数;然后,按照矩形件数量最大原则确定板材的最优多级划分。采用随机例题和实际生产实例将本文算法与普通排样算法进行比较。实验结果表明，多级排样方式的板材利用率随着级数的增加而递增，当级数达到5级时，板材利用率达到最高；最优多级排样方式的板材利用率比普通排样方式高3.88%。

The problem of single rectangular part layout was discussed, that was, the rectangular part with length of l and width of w was cut by using the sheet with length of L and width of W, the optimization objective was to maximize the number of rectangular parts cut out, and a multi-section layout method with limited sections and its accurate generation algorithm was proposed. With this layout method, the sheet was divided into several sections, and in each section, the rectangular parts with the same direction were placed, but the direction of the rectangular parts in the adjacent sections was perpendicular to each other. Firstly, the maximum number of rectangular parts placed in all possible size sections was determined by implicit enumeration method, and then the optimal multi-section division of sheet was determined according to the principle of the maximum number for rectangular parts. Furthermore, the proposed algorithm was compared with the common layout algorithm by using random examples and practical production examples. The experimental results show that the sheet utilization rate of the multi-section layout method increases with the increasing of the number of sections. When five sections are reached, the sheet utilization rate reaches the highest, and the sheet utilization rate of the optimal multi-section layout method is 3.88% higher than that of the ordinary layout method.

基金项目：

教育部新一代信息技术创新项目（2020ITA03027）；广西2020年度中青年教师基础能力提升项目(2020KY41016 )；广西农业职业技术大学2021年科学研究与技术开发计划课题（YKJ2124）

作者简介：唐伟萍（1983-），女，学士，副教授 E-mail：hxnz2002@126.com 通信作者：黄欣（1983-），男，硕士，副教授 E-mail：nyzg2001@163.com

参考文献：

[1]Delorme M, Iori M. Enhanced pseudopolynomial formulations for bin packing and cutting stock problems[J]. INFORMS Journal on Computing, 2020, 32(1): 101-119.

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

[3]周家智, 尹令, 张素敏. 基于遗传模拟退火算法的布局优化研究[J]. 图学学报, 2018, 39(3): 567-572.

Zhou J Z, Yin L, Zhang S M . On layout optimization based on genetic simulated annealing algorithm[J]. Journal of Graphics, 2018, 39(3): 567-572.

[4]Wscher G, Hauner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3):1109-1130.

[5]Delorme M, Iori M. Enhanced pseudopolynomial formulations for bin packing and cutting stock problems[J]. INFORMS Journal on Computing, 2020, 32(1): 101-119.

[6]Mellouli A, Mellouli R, Masmoudi F. An innovative genetic algorithm for a multiobjective optimization of twodimensional cuttingstock problem[J]. Applied Artificial Intelligence, 2019, 33(6):531-547.

[7]Cui Y P, Cui Y, Tang T. Sequential heuristic for the twodimensional binpacking problem[J]. European Journal of Operational Research, 2015, 240(1): 43-53.

[8]杨传民, 王树人, 王心宇. 基于 4 块结构的斩断切割布局启发性算法[J]. 机械设计, 2007, 24(2): 25-26.

Yang C M, Wang S R, Wang X Y. Heuristic algorithm on layout of chopped cutting based on 4 pieces of structure[J]. Journal of Machine Design, 2007, 24(2): 25-26.

[9]Cui Y. Simple block patterns for the twodimensional cutting problem[J]. Mathematical and Computer Modelling, 2007, 45(7-8): 943-953.

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

[11]崔耀东, 周儒荣. 单一尺寸矩形毛坯排样时长板的最优分割[J]. 计算机辅助设计与图形学学报, 2001，13(5):434-437.

Cui Y D, Zhou R R. Optimum cutting rectangles of a single size from a long rectangular sheet[J]. Journal of ComputerAided Design & Computer Graphics, 2001，13(5):434-437.

[12]杨家武, 王永章, 董现华. 单一尺寸矩形板件最优化下料方法研究[J]. 林业机械与木工设备, 2007, 35(5):22-24.

Yang J W, Wang Y Z, Dong X H. The study on single size rectangular plate optimal design method[J]. Forestry Machinery & Woodworking Equipment, 2007, 35(5):22-24.

[13]Cui Y D, Gu T L, Hu W. Recursive algorithms for the optimum cutting of equal rectangles[J]. International Journal of Computers & Applications, 2011, 33(2):103-107.

[14]杜远坤, 牛庆丽, 管卫利. 同尺寸矩形件多板材下料算法[J]. 机械设计与制造, 2017，54(8)：61-63.

Du Y K, Niu Q L, Guan W L. An algorithm for the problem of cutting stock equal rectangular items with multiple plates[J]. Machinery Design & Manufacture, 2017，54(8)：61-63.

[15]胡钢, 孙洪涛, 潘立武. 矩形件单一排样问题的一种精确算法[J]. 锻压技术, 2016, 41(10): 43-47.

Hu G, Sun H T, Pan L W. An exact algorithm of the single layout problem for rectangular parts[J]. Forging & Stamping Technology, 2016, 41(10): 43-47.

服务与反馈：

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