一种可变规格板材下料的优化方法

陈 奇，曹德列，饶运清

CHEN Qi, CAO De-lie, RAO Yun-qing

（华中科技大学 数字制造装备与技术国家重点实验室，武汉 430074）

0 引言

零件在一批大小和成本不同的板材上下料（可变规格板材下料）的问题普遍存在于板材加工类企业下料生产中。可变规格板材下料对板材规格不限定，可以是不同形状、不同大小的矩形板材或者不规则板材，以及存在内部缺陷的非完整板材。由于需要统筹兼顾大小和成本不同的板材，可变规格板材下料相对于传统同规格板材下料能获得更为节省的下料方案。

可变规格板材下料注重于板材选择和排样布局的统筹最优，是一种组合优化问题，具有较高的复杂度。当前板材下料方面的研究多针对单张板材限定长宽或不限长度或者针对多张相同板材[1~4]，研究具体的排放算法而未能有效考虑不同规格板材的使用情况。Remesh Babu[5,6]等利用遗传算法给出了多张不同板材时的排样优化方法，然而目标函数只分析了材料面积未计入板材的使用数量，同时也没有涉及到板材成本不同的情况。从可变大小二维装箱问题的角度，Teodor Gabriel Crainic[7]利用箱子单位大小的成本进行分析，但是没有优化箱子的序列选择也没有协调优化箱子之间的装箱效果。

由于该类组合优化问题属于NP-难问题，不存在多项式时间的算法，但遗传算法在求解这类问题上效果突出。鉴于此，本文针对可变规格板材下料问题，以下料方案对应的成本最优为目标，利用遗传算法优化板材序列和零件序列，并在解码过程以模拟退火方式对排样板材间零件加以优化调整提高板材总体利用率，得到最终下料方案。

1 问题分析

有m种大小和成本各异的板材B1，B2，…，Bm，每种 NB1，NB2，…，NBm张，每种成本为 C1，C2，…，Cm。板材的单位质量成本不完全相同。现需要将n个零件P1，P2，…，Pn全部排放在板材上，任一板材都能完全覆盖任一零件，板材为所给板材中的一张或几张，要求下料方案最优。

下料生产存在各种成本，和板材数量相关的有板材启动成本、工人上下料作业成本等。传统以最大化板材利用率为目标的研究具有一定局限性。板材选择使用需要以合理方式权衡板材利用率和板材使用数量。本文以板材成本统一考虑板材利用率和使用数量。为增强对板材使用数量的控制，引进板材加工过程的中间成本。中间成本包括板材启动成本和工人上下料作业成本。本文下料方案成本由板材成本和中间成本两部分构成。

余料在下次下料时仍可使用，计算板材成本时相应扣除。余料成本利用原板材成本按余料面积占原板材面积百分比计算。设可用余料面积与板材面积比值为ηi，则余料成本为ηiCi。设中间成本相同，为Cs。数学模型为：

式中，Ni为板材Bi使用数量，Ni＜NBi。n为使用的板材种类，m为生成的余料数量。式中ηi和板材利用率相关，ηi越大利用率越高，所用板材相对越少，材料成本相对越低。

2 优化方法

可变规格板材下料一般流程如图1所示，下料优化需要确定使用何种板材、每种板材的使用数量、每张板材上排放哪些零件、板材的使用顺序以及零件的排放方式。零件序列按板材序列依次排样，排样结果为一张板材对应一组零件以及一种布局方式。排样之后，每张板材排放哪些零件、零件的排放方式已知。板材使用种类和每种板材的使用数量受板材序列的影响，板材序列确定后二者相应确定。在既有排放算法基础上，为进一步优化排样效果，文章的关键任务是可变规格板材下料的板材序列优化、板材间排样效果协调优化以及在此基础上的总体优化处理。

图1 下料流程图

2.1 板材序列优化

板材选用是要从不同形状、不同大小的矩形板材或者不规则板材以及存在内部缺陷的非完整板材中选择合适的板材组合，并按最优顺序使用。板材按序列依次使用，最佳的板材使用方案是一种板材序列的最佳组合方案。

下料优化是板材和零件的序列优化与布局优化。遗传算法具有较强的全局搜索能力、鲁棒性强，对于组合优化中的NP完全问题的求解非常有效。本文利用遗传算法产生最佳板材序列，同时产生最佳零件序列。板材的利用率、使用数量等因素通过成本在目标函数中反映。

2.2 板材间排样效果协调优化

零件序列按板材序列依次排样，并通过向后搜索合适零件对可能存在的孔洞空域加以填充。排样受零件面积的影响，排样后期随小型零件的减少，孔洞空域逐步增加。一张板材完全排满后再排放下一张会使后续板材利用率逐渐降低。如果在当前限制某些后续搜索零件的插入，后续的排样效果可以趋于更优。

排样一般从板材左下角开始，排放过程会在板材右端和上端留下一些空域。如果在该零件组中增加或删除一个零件重新排样，排样结果会发生较大变化。当增加一个或多个零件时，由于使用的零件不一样，排样布局效果发生改变，原空域部分可以得到填充，排样结果可以趋于更优。

排样结果为一张板材对应一组零件以及一种布局方式。优化以初始排样结果为基础展开，向着下料更优的方向进行，即增大余料提高利用率降低成本。协调优化是一个不断调整排样效果的过程。为增强优化调整得到解的可行性，调整方向以参与排样的有效板材序列中某一张开始向后推动。

板材序列中参与排样的板材为序列前Li张。取[1, Li-1]内随机整数RB作为当前板材调整号，以RB号板材为基础向后调整，RB号以前排样情况不变。为避免产生多张余料，调整前RB及其后续所有板材连同对应零件重新排样。调整时，RB号板材上无法再追加新零件，调整过程为减少其已有零件数量。同时为不破坏排样过程带来的择优插入和避免调整结果恶化，每次调整量不宜过大，调整量取[0, a]内随机整数RP。本文取a＝3，RP取RB板材对应零件组的后RP个。RB号板材及其调整后剩余零件重新排样，RP个零件加入后续零件序列并在后续板材上重新排样。

如果调整效果不优，以当前调整结果为基础进一步调整存在更优的可能性，可以按概率接收作为新的基础解。但当调整数量过多时以该结果为基础无论怎样调整，效率都低，此时接收概率降低。模拟退火随着温度降低，接收概率逐渐减小，最后系统收敛于某一能量最小的状态，该状态即可作为目标函数的全局优化值。解码过程按模拟退火技术进行排样再优化，步骤如下：

第一步：设置初始温度；

第二步：设置循环计数器起点；

第三步：获得[1, Li-1]内随机整数RB，作为零件调整基础板材序号，并就RB及后续板材连同对应零件重新排样；

第四步：获得[0, a]内随机数RP，作为基础板材上零件调整个数，按调整策略进行排样优化调整；

第五步：如果当前结果更优，接收该结果，否则按概率接收；

第六步：如果步数小于终止步数，增大步数，转向第三步；

第七步：如果未达到冷却状态，继续降温，转向第二步；否则，输出结果。

板材间排样效果协调优化不追求每张板材布局最大化，通过排样零件在不同板材间的优化协调提高总体利用率，寻求总体的布局更优。

2.3 基于遗传算法的下料优化处理

根据图1及问题分析，下料问题需优化板材序列、零件序列以及板材间排样效果。本文优化方法以遗传算法为基础，在遗传算法处理过程，将板材序列优化和零件序列优化结合起来。遗传算法采用目标函数作为适应度函数，解码过程对初始排样结果按2.2中的方法对初始排样结果协调优化。算法流程如图2所示。

图2 算法流程图

2.3.1 种群初始化

遗传算法染色体包括两段，一段为零件序列，一段为板材序列。为便于序列化操作，所有零件和板材均从1开始标号。

零件序列部分采用随机初始方式，部分采用有序初始方式[8]。有序初始方式首先将零件按面积非增序排列，面积相等时按长度非增序排列，对序列中每个标号随机赋予“+”“-”表示旋转方向，生成带符号的有序种群。

板材序列主要由板材随机排序生成。其中，板材序列中的m个序列，每个序列前NBi项为一种板材Bi，其余项按剩下板材单位质量成本非降序排列。另外1个序列直接按板材单位质量成本非降序排序。

2.3.2 遗传算子

1）选择算子

遗传算法采用轮盘赌选择，根据每条染色体的适应度的比例来确定该个体的选择概率。

2）交叉算子

零件序列和板材序列交叉操作均采用LOX交叉。LOX是一种改进的次序杂交，能尽可能多的保留基因间的相对位置。操作时，先从两父代P1、P2中选择交叉点，交换选中的基因子串；然后将原P1(P2)中与P2(P1)子串不同的基因依次填入P1(P2)中非子串基因位置构成后代。如图3，在选择交叉位置3、7后按操作步骤进行得到子代C1、C2。

图3 LOX交叉

3）变异算子

零件序列变异过程包括序列顺序变异和旋转方向变异，前者采用逆序变异，后者采用均匀变异。板材序列变异操作采用逆序变异。逆序变异根据选中的两个变异点，将变异区间内基因顺序颠倒产生新个体。

排样时不是每张板材都参与排样，而是依板材序列排样直至零件全部排完。板材序列中只有序列前面一部分起实际作用。为提高板材序列交叉变异效果，交叉变异针对参与排样板材序列部分展开。设板材序列中参与排样的板材为序列前Li张。交叉操作时Li取两序列较小者，并以此值作为变异位置基础。交叉、变异过程两位置之一的取值范围限定在[1, Li]。

2.3.3 终止条件

按算法流程循环，直到下料方案满足优化目标或达到预定的进化代数，停止计算，输出结果。

3 算例验证

算例以矩形排样为例，排放算法采用文献[8]中基于最低水平线的择优插入算法。该方法在排样过程按最低水平线法形成空洞时向后搜索合适零件插入当前序列位置并填入空洞。根据文章分析和算法框架，选用几种大小和成本各异的板材以及相关零件进行实验。板材材质为Q235，板厚20，不同规格之间单位质量成本不同。板材的大小、数量、成本等信息见表1。算例中设中间成本10，余料长度大于300时余料有效。

表1 板材信息

每种板材单独排样时所耗板材数量、利用率及成本如表2所示。

表2 同规格板材下料

表2中余料1是直接排样后剩下的余料长度，余料2是进行排样效果协调优化后剩下的余料长度。零件序列按板材序列依次排样，余料出现在最后一张板材。其中B1、B4板材余料在排样协调优化前后均小于300，视作废料处理。成本按协调优化后使用情况计算。从表2可以看出，板材间排样效果协调优化效果有效。

采用可变规格板材下料优化方法的结果如表3所示。

表3 可变规格板材下料

优化结果为板材B1使用3张、B2使用2张，顺序为B2B1B1B2B1。其中B2无余料，最后一张B1板材余料长度941。总体优化成本为1998.9，较表2中同种规格板材下料成本更优。

单张板材利用率不高时，板材间排样协调优化效果较为明显。算例中所用矩形零件大小相差各异且较为明显，同时数量不一。在算例中排样效果再优化体现出其有效性。由表可以看出，本文方法能够有效处理可变规格板材选用，并有效进行零件排样效果再优化。

4 结论

本文针对可变规格板材下料优化问题，在板材的选择使用过程中考虑板材利用率和使用数量两因素，利用遗传算法实现板材选用优化；在遗传算法处理过程，将板材序列优化和零件序列优化结合起来，并在解码过程以模拟退火方式对排样板材间零件加以优化调整提高板材总体利用率。实验表明，本文所论述的方法具有较强可行性，能够有效降低下料成本。基于本文方法开发的优化模块已嵌入到排样软件系统中，取得了良好的应用效果。利用本文提出的思路和方法，还可根据实际需求进一步研究在成本中考虑加工成本、库存成本、延期交货成本等因素的情况。

[1]陈学松,曹炬,方仍存.一种求解矩形件排样问题的启发式算法[J].锻压技术,2004,(05).

[2]陈仕军,曹炬.矩形件优化排样的一种启发式算法[J].计算机工程与应用,2010,(12).

[3]张立驰,李健.基于遗传算法的二维排样问题求解新策略[J].南通职业大学学报,2009,(03).

[4]张丽平,李松.二维优化排样方法及实现技术[J].计算机应用与软件,2009,(04).

[5]A.Ramesh Babu, N.Ramesh Babu.Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms[J].Int J Prod Res, 1999,37(7)∶1625-1643.

[6]A.Ramesh Babu, N.Ramesh Babu.A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms[J].Computer-Aided Design, 2001,33(12)∶879-891.

[7]Teodor Gabriel Crainic, Guido Perboli, Walter Reiand.Efficient lower bounds and heuristics for the variable cost and size bin packing problem[J].Computers & Operations Research, 2011, 38(11)∶1474-1482.

[8]赵新芳,崔耀东,杨莹等.矩形件带排样的一种遗传算法[J].计算机辅助设计与图形学学报,2008,(04).