青岛科技大学学报（自然科学版）2021年8月第42卷第4期 42号 8 月 4 日 2021文章编号：（2021）；DOI : 10. 16351/j。。2021. 04. 013 基于动态最优组合的板材切割算法为了解决速率问题，提出了一种矩形板的最优组合算法。该算法在最底层搜索算法的基础上增加了动态最优组合算法。通过启发式定位算法，可以获得板材的切割路径和板材的出料位置信息。为了缩短每次优化排列组合的计算时间，采用了易于描述板材和零件信息的C#语言。为了提高板材的利用率钢材切割 算法，将每一种剩余材料加入数据库，优先使用。根据工厂提供的版材和版材数据，算法可以减少版材切割过程中的残料。关键词：矩形片；启发式定位；动态优化组合；余料优先利用基于动态优化组合的板材切割下料算法研究[J]. 青岛科技大学学报（自然科学版）, 2021, 42 (4): 88-93. , . 祗园[J]. (n), 2021, 42(4): 88-93。收稿日期：2020-07-03 基金项目：山东省自然科学基金项目（，）；青岛市应用基础研究项目（18-2-2-21-jch）。作者简介：鞠云鹏（1982-），男，博士，讲师。, (a.ing; b., , , 中国): G, . , 总称。, . , C#板。晚的 ， 。凯里，吃了。: ; ;ation; 随着板式家具的量产，
计算机辅助排版方法可以提高排版精度，降低人工成本，减少误操作，提高板材切割效率[5]。在一块大板上排列一批不同尺寸的板并实现高板利用率是一个复杂的问题，不确定是否能在多项式时间内找到答案[6]。采用常规方法求解此类多项式不确定性问题已不能满足实际需要。对于小型生产企业，可以采用一些早期的板材切割和下料的方法[7-11]。然而，随着板式家具的大规模定制，很多企业的产量并没有达到市场需求，板料切割利用率低的问题也开始暴露出来。以低效率、低利用率为目标，陆续提出了一些新的算法。最左下角算法[12]首先被提出，然后在此基础上出现了降步算法[13]，然后出现了最底层算法[14-15]和近似算法[16]。上述方法与传统布局方法相比具有明显优势，但不能对所有矩形部分进行全局搜索，因此具有一定的局限性。随着GA、SA、TS、AA、ANN等智能算法的发展，出现了智能算法与传统算法相结合的优化算法。参考文献[17]将蚁群算法与启发式算法相结合，优化了板材的切割和下料。文献[18]根据模拟退火的特点将两者有效结合，
通过智能算法优化，可以为不确定的布局问题寻找更广泛的有效解决方案。对于数量大、尺寸不同、规格不同的板材布局，遗传算法可以在更大的空间内寻找优化，但寻找有效解的时间会更长[19]。与最低水平线算法相比，最低水平线搜索算法在一定范围内进行了优化，但是两个矩形部分的位置需要互换，导致后面板排列过程中小部分的缺失。本研究基于最低水平线搜索算法。首先，要排列的面板根据它们的面积大小排列。其次，在最低水平线上排列矩形块时，根据矩形块的长度或宽度占最低水平线的比例选择它们。如果组合所占的比例较大，则优先选择矩形块的组合进行排列，该组合中矩形块的顺序不能与其他待排列的矩形块互换。通过排列矩形板，这种优化组合算法可以有效提高板的利用率。1 数学模型 整个矩形大板的长宽分别为L和W。为了减少切割过程中产生的残料，应尽量减小出料板之间的间隙。设待排列板的规格数为k，第i板的数量为ni，宽度和长度分别为wi和li。如果大板数量足够，则要切割的小板数量可以表示为n = ∑ki = 1ni。(1)板材出料过程中，可按长边或短边出料，需根据板材是否有纹理处理的要求进行。
第一块板子要先放在大板的左下角，后块板子要均匀排列。以大板的左下角为参考点，第i个板的左上角坐标表示为(x 1 i ,y 1 i )，右下角坐标表示为为 (x 2 i , y 2 i )。根据板块的长边或短边排列，对角线上两点的坐标可表示为x 2 i = x 1 i + li , y 2 i = y 1 i - wi 。{或 x 2 i = x 1 i + wi , y 2 i = y 1 i - li 。{(2) ri = 0, 1，当板材按长边排列时，ri取0。当板材按照短边排列时，ri取1。建立面板左上角和右下角坐标的关系： x 2 i = x 1 i + ( 1- ri ) li + riwi , y 2 i = y 1 i - ( 1 - ri )威日里。{(3)为提高版材利用率，版材上的版材间距应尽量小，但出材时版材不得重叠或压边。取任意两块板R t 、R s ，为了满足排放要求，需要满足坐标关系。根据公式（3），x 1 s + ( 1 - rs ) ls + rsws < x 1 t , x 1 s > x 1 t + ( 1 - rt ) lt + rtwt , y 1 t < y 1 s - ( 1- rs ) ws - rsls , y 1 t - ( 1 - rt ) wt - rtlt > y 1 s 。y 2 i = y 1 i-(1-ri) wi-rili。{(3)为提高版材利用率，版材上的版材间距应尽量小，但出材时版材不得重叠或压边。取任意两块板R t 、R s ，为了满足排放要求，需要满足坐标关系。根据公式（3），x 1 s + ( 1 - rs ) ls + rsws < x 1 t , x 1 s > x 1 t + ( 1 - rt ) lt + rtwt , y 1 t < y 1 s - ( 1- rs ) ws - rsls , y 1 t - ( 1 - rt ) wt - rtlt > y 1 s 。y 2 i = y 1 i-(1-ri) wi-rili。{(3)为提高版材利用率，版材上的版材间距应尽量小，但出材时版材不得重叠或压边。取任意两块板R t 、R s ，为了满足排放要求钢材切割 算法，需要满足坐标关系。根据公式（3），x 1 s + ( 1 - rs ) ls + rsws < x 1 t , x 1 s > x 1 t + ( 1 - rt ) lt + rtwt , y 1 t < y 1 s - ( 1- rs ) ws - rsls , y 1 t - ( 1 - rt ) wt - rtlt > y 1 s 。为了满足排放要求，需要满足坐标关系。根据公式（3），x 1 s + ( 1 - rs ) ls + rsws < x 1 t , x 1 s > x 1 t + ( 1 - rt ) lt + rtwt , y 1 t < y 1 s - ( 1- rs ) ws - rsls , y 1 t - ( 1 - rt ) wt - rtlt > y 1 s 。为了满足排放要求，需要满足坐标关系。根据公式（3），x 1 s + ( 1 - rs ) ls + rsws < x 1 t , x 1 s > x 1 t + ( 1 - rt ) lt + rtwt , y 1 t < y 1 s - ( 1- rs ) ws - rsls , y 1 t - ( 1 - rt ) wt - rtlt > y 1 s 。
（四）出板时，除保证板不能重叠压边外，还应保证板不能出大板边界外，即下横坐标板的右角小于板的长度，板的左上角的纵坐标小于板的宽度。根据上述约束， u ( x 1 t - x 1 s - ( 1 - rs ) ls - rsws ) + u ( x 1 s - x 1 t - ( 1 - rt ) lt - rtwt ) + u ( y 1 s - y 1 t - ( 1 - rs ) ws - rsls ) + u ( y 1 t - y 1 s - ( 1 - rt ) wt - rtlt ) ≥1 , 0≤ x 1 t ≤ L - ( 1 - rt ) lt - rtwt , (1- rt ) wt + rtlt ≤ y 1 t ≤ W , s ≠ t , rt = 0 , 1 , rs = 0 , 1 , s , t , i = 1 , 2 ,, n 。ìîíïïïïïïïïïïïïïï(5) 式(5)中，u 为单位阶跃函数。为了最大化板材的利用率，应满足公式（6）的目标函数。最大 ∑ni = 1 (x 2 i - x 1 i )( y 1 i - y 2 i )∑m - 1j = 1 S j + S m。
（6）一般S j 是一个固定值，代表一个大板在一批板块中的面积；S m 是一次生产中使用的最后一块大板的面积。98青岛科技大学学报（自然科学版）第42卷2最优组合算法分析本作品基于启发式定位算法，逐一计算待排列项目在数据库中的面积，然后根据区域的大小对它们进行排序。采用动态最优组合算法对其进行放电。假设最低水平线的长度为l，则板的排列如下。1）选择要切割的大板的底边作为最低的水平轮廓线，使其成为一个集合元素。2）从待排列的矩形块中搜索一个矩形块或矩形块组合，根据矩形块或矩形块组合占据最低水平线的比例确定搜索原则。如果有多种组合，则根据面积大小优先选择面积较大的组合。3）在已建立的集合中找到最低的水平线，将组件底边的长度与l进行比较： ①如果组件底边的长度较短，则可以将组件放在水平线上。如果拼装底边长度大于l，但宽度小于l，且板材无纹理切割要求，然后组件可以在旋转后放置在水平线上。如果组件的长度不等于其宽度，并且长度和宽度都小于l，并且板子没有纹理切割要求，则将组件按长边放置在水平线上。② 否则，在待卸料的矩形件序列中，将其他总成的长宽与l进行比较，当找到合适的总成时，不要将当前不能卸出的矩形件与搜索到的总成互换。位置，但仅将搜索到的组件放置在当前最低的水平线上。然后将组件按长边放置在水平线上。② 否则，在待卸料的矩形件序列中，将其他总成的长宽与l进行比较，当找到合适的总成时，不要将当前不能卸出的矩形件与搜索到的总成互换。位置，但仅将搜索到的组件放置在当前最低的水平线上。然后将组件按长边放置在水平线上。② 否则，在待卸料的矩形件序列中，将其他总成的长宽与l进行比较，当找到合适的总成时，不要将当前不能卸出的矩形件与搜索到的总成互换。位置，但仅将搜索到的组件放置在当前最低的水平线上。
如果组件的长和宽都大于l，则需要将最小水平线调整到一定高度，并且这个高度应该与水平线相邻的其他最小等高线的高度一致，最小等高线线集也需要更新。4) 重复程序的步骤 2) 和 3)。一块大板裁完后，需要用另一块大板。此时，程序从步骤(1)开始。本工作称该算法为动态最优组合算法。3 比较分析3．1 下料数据 为了更好地验证排版优化组合算法的有效性，本文以工厂提供的实际下料板数据作为实验数据。板材采用常用尺寸2440×1220×18，单位为mm。下料板的尺寸和纹理要求如表1所示。 3. 2. 排列算法的比较与分析 2. 1 最左下算法 图1是最左下算法的布局。依次排列{ +1 , +2 , +3 , +4 } 盘子，数字前的“+”表示盘子不能旋转。根据最左下角规则，板 1、2 和 3 排出后，板 1、2 和 3 之间会产生很大的间隙（图 1（a））。继续板4出料。板4出料完成后，前面留下的间隙仍未补齐（图1（b））。四个板的理想排放形式如图1（c）所示，板的排放相对紧凑。2 排列算法的比较与分析 1 最左下算法 图1 是最左下算法的布局。依次排列{ +1 , +2 , +3 , +4 } 盘子，数字前的“+”表示盘子不能旋转。根据最左下角规则，板 1、2 和 3 排出后，板 1、2 和 3 之间会产生很大的间隙（图 1（a））。继续板4出料。板4出料完成后，前面留下的间隙仍未补齐（图1（b））。四个板的理想排放形式如图1（c）所示，板的排放相对紧凑。2 排列算法的比较与分析 1 最左下算法 图1 是最左下算法的布局。依次排列{ +1 , +2 , +3 , +4 } 盘子，数字前的“+”表示盘子不能旋转。根据最左下角规则，板 1、2 和 3 排出后，板 1、2 和 3 之间会产生很大的间隙（图 1（a））。继续板4出料。板4出料完成后，前面留下的间隙仍未补齐（图1（b））。四个板的理想排放形式如图1（c）所示，板的排放相对紧凑。+3 , +4 } 顺序，数字前的“+”表示盘子不能旋转。根据最左下角规则，板 1、2 和 3 排出后，板 1、2 和 3 之间会产生很大的间隙（图 1（a））。继续板4出料。板4出料完成后，前面留下的间隙仍未补齐（图1（b））。四个板的理想排放形式如图1（c）所示，板的排放相对紧凑。+3 , +4 } 顺序，数字前的“+”表示盘子不能旋转。根据最左下角规则，板 1、2 和 3 排出后，板 1、2 和 3 之间会产生很大的间隙（图 1（a））。继续板4出料。板4出料完成后，前面留下的间隙仍未补齐（图1（b））。四个板的理想排放形式如图1（c）所示，板的排放相对紧凑。前面留下的间隙仍未弥补（图1（b））。四个板的理想排放形式如图1（c）所示，板的排放相对紧凑。前面留下的间隙仍未弥补（图1（b））。四个板的理想排放形式如图1（c）所示，板的排放相对紧凑。
表 1 板详细信息 表 1 序列号 宽度 / mm 高度 / mm 厚度 / mm 数量 质地 1 200 100 18 12 否 2 1000 500 18 4 是 3 350 200 18 8 否 4 450 430 18 6 否 5 500 300 18 4 否6 1000 450 18 4 否 7 1300 500 18 4 是 8 800 400 18 8 是 9 600 300 18 8 是 10 700 400 18 8 否 图 1 底部和左侧算法板 图 。2. 2 降压算法将板块{+1, +2, +3, +4}依次排列。本节中的板与图 1 中的板不同。数字前的“+”表示板不能旋转。比较最左下角算法的布局和降压算法的布局，如图2所示。对于前三个面板的放电，两者之间没有明显优势（图2（a ））。第四块板出料时，有间隙。最左下算法没有将板块放置在最低等高线上，导致整体出料高度较高，而下步算法整体布局更加统一，板块排列整齐。袖珍的。图 2. BL 算法与降压算法的比较。23. 2. 3. 最低水平线算法 最近水平线算法如图3所示。
依次排列 {+1 , -2 , +3 , +4 } 板块，本节板块与前面板块不同。09 第四期 板前“+”表示板不能旋转，“-”表示板旋转90°后出料。图3(a)~(f)是四块面板按最低水平线法放电的过程。图 3 最低水平线算法布局 3 分别使用最低水平线法和降压算法比较六块板的排列效果，如图4所示。对于前5块板的放电，两者都没有具有明显的优势（图4（a））。第六盘排干的时候，两人之间出现了一道缝隙。最低水平线法将板6置于最低等高线，降压算法将板6放置在高于最低等高线的板4上，导致降压算法的整体板排列高度更高。板面不均匀，图4(b)的板面排列效果比较理想。图 4 最低水平线法与降压算法的比较。43. 2. 4. 使用最低水平线搜索算法排出图3中的四个面板。当使用最低水平线法排出面板3时，由于面板3的长度大于当前最低水平线上，面板3不能放在最低水平线上gd。当需要更新最小横线时，将新的最小横线改为ab，然后将待排列的面板块排出。
根据最低水平线搜索算法的规则，当板3在gd中无法出料时，可以从待排的部分中选择合适的板4，避免了出料部分的浪费最低水平线上方的空间。最低水平线搜索算法和最低水平线方法的比较如图5所示。图5（b）比图3（f）更低且更均匀。图 5 基于最低水平线搜索算法的布局（对比图 3）。5 ( . 3 ) 3. 2. 5 动态最优组合算法将面板{-1,+2,-3,+4,-5,+6,-7}依次排列，本节面板不同从前面的面板来看，数字前的“+”表示板不能旋转，“-” 表示板旋转90°后卸料。根据最低水平线的搜索算法规则，如图6所示，排出7个板块。当排出第四个板块时，板块4的长度大于当前最低水平线。因此，使用搜索算法来选择合适的板块。板7，合适和不合适的板的位置已经互换。然后排出板 5、6 和 4，导致图 6(c) 中的总板高度更高，从而在板 2、3、4 和 6 之间留下较大的间隙。搜索算法用于选择合适的板块。板7，合适和不合适的板的位置已经互换。然后排出板 5、6 和 4，导致图 6(c) 中的总板高度更高，从而在板 2、3、4 和 6 之间留下较大的间隙。搜索算法用于选择合适的板块。板7，合适和不合适的板的位置已经互换。然后排出板 5、6 和 4，导致图 6(c) 中的总板高度更高，从而在板 2、3、4 和 6 之间留下较大的间隙。
与最低水平线的搜索算法不同，七个面板按照动态最优组合算法规则排列，如图7所示。找到合适的面板7后，将其放置在当前最低水平线处。然后将板4、5、6排出，效果如图7(b)所示。从图中可以看出，板材排列均匀，整体高度较低。与图6（c）相比，它的利用率更高。图 6 基于最低水平线搜索算法的排列（对比图 7）。6 (.7) 图 7 动态选择。. .
