二维板材排样问题的递归多块布局算法

来源：计算机集成制造系统杂志2025年第6期北京时间：

作者：潘卫平, 樊治平, 黄敏, 计明军

单位：1.大连海事大学交通运输工程学院2.东北大学工商管理学院3.东北大学信息科学与工程学院4.东北大学流程工业综合自动化国家重点实验室

摘要：针对矩形件二维板材排样问题,提出递归多块排样方式及其动态规划生成算法。递归多块排样方式将板材划分成多个块,然后递归地对每个块进行多块划分,直到每个新产生的块中排放一种最优矩形件为止。为了均衡考虑排样方式的计算复杂度和板材排样价值,对于一刀切排样问题将多块划分的块数定为两块,对于非一刀切排样问题将多块划分的块数定为5块。动态规划算法首先计算每个块中分别排放一种矩形件所得到的1阶多块排样方式的最大价值,然后计算每个块中分别排放一个1阶多块排样方式得到的2阶多块排样方式的最大价值,以此递推,得到任意阶数的多块排样方式的最大价值。通过比较块的排样价值的上界和下界来剔除不必要的多块划分,通过离散化划分线位置来控制算法的时间复杂度。采用文献典型例题和实际生产实例,将所提算法与一刀切排样算法和非一刀切排样算法进行对比,表明了所提算法的优越性。

关键词：二维板材排样,递归多块排样方式,动态规划,排样价值,矩形件

基金资助：国家重点研发计划资助项目(2019YFB1705003);国家自然科学基金资助项目(71971035);国家自然科学基金重点国际合作研究资助项目(71620107003);辽宁省“兴辽英才计划”资助项目(XLYC1802115);流程工业综合自动化国家重点实验室基础科研业务费资助项目(2013ZCX11) 。