同质块占角排样方式的二维下料模型与算法  

Model and algorithm of two-dimensional cutting stock problem based on homogeneous block corner-occupying layout

作　　者：潘卫平 PAN Weiping(College of Information Engineering,Hainan Vocational University of Science and Technology,Haikou 571126,China)

机构地区：[1]海南科技职业大学信息工程学院,海口571126

出　　处：《自动化与仪器仪表》2024年第9期115-121,共7页Automation & Instrumentation

基　　金：国家重点研发计划资助项目(2019YFB1705002);海南省自然科学基金项目(622RC726);The fifth round of provincial characteristic key discipline“Computer Science and Technology”;provincial high-level professional group“Computer Network Technology” in Hainan Province。

摘　　要：针对矩形件二维下料问题,提出一种基于同质块占角排样方式的优化模型与求解算法。这种排样方式首先在板材的左上角排放一个由同种矩形件组成的同质块,然后将板材的剩余部分水平或竖直划分成2个子板,将子板看作板材继续递归考察,直到子板无法容纳矩形件为止。构造同质块占角排样算法按照板材排样价值最大原则确定板材左上角同质块的尺寸和板材剩余部分的划分方式。提出的列生成算法迭代调用上述同质块占角排样算法生成多个下料方案,选择耗费板材最少的一个下料方案作为最优解。通过文献基准例题和实际生产实例验证了下料算法,实验结果表明:同质块占角下料算法板材利用率高于已有文献给出的下料算法。给出算法计算时间可满足实际应用需要。An optimization model and solution algorithm based on the homogeneous block corner-occupying layout were proposed for the two-dimensional cutting stock problem of rectangular parts.With this layout,a homogeneous block composed of the same rectangular parts was arranged on the upper left corner of the sheet,then the remaining part of the sheet was divided horizontally or vertically into 2 sub-sheets.The sub-sheet was regarded as a sheet and continued to be investigated recursively until the sub-sheet cannot accommodate rectangular parts.The size of the homogeneous block in the upper left corner of the sheet and the partition of the remaining part of the sheet were determined by the proposed homogenous block corner-occupying layout algorithm according to the principle of maximum layout value of the sheet.The above homogenous block corner-occupying layout algorithm was iteratively called by the proposed column generation algorithm to generated multiple cutting stock schemes,and the cutting stock scheme with the least sheet consumption was selected as the optimal solution.The cutting stock algorithm in this paper was verified by benchmark instances in the literature and actual production examples.The experimental results showed that the utilization rate of the homogeneous block corner-occupying cutting stock algorithm was higher than that of the cutting stock algorithm given in the literature.The calculation time of the algorithm given in this paper can meet the needs of practical application.

关 键 词：二维下料 矩形件 占角排样方式 列生成 

分 类 号：TH164[机械工程—机械制造及自动化]