Transactions of Materials and Heat Treatment

Title：Accurate algorithm of multi-section layout for single rectangular part with limited sections

Authors： Tang Weiping1 Qiu Gangwei2 Zhang Juanmei3 Huang Xin2

Unit： 1. Department of Automotive and Traffic Engineering Guangxi Electric Polytechnic Institute 2. Department of Information and Electromechanical Engineering Guangxi Agriculture Vocational and Technical University 3. Department of Fine Arts North Sichuan Preschool Teachers College

KeyWords： sheet rectangular part cutting multi-section layout method layout algorithm

ClassificationCode：TP391

year,vol(issue):pagenumber：2021,46(12):74-78

Abstract：

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.

Funds：

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

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

Reference：

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

Service：

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