铁芯迭片的多板材下料优化策略研究

陈燕，宁晓军，胡小春，蒋志一

(1.广西大学计算机与电子信息学院， 广西南宁530004；2.广西财经学院信息与统计学院， 广西南宁530007;3.广西多媒体通信与网络技术重点实验室， 广西南宁530004)

0 引言

大中型发电机定子和转子制造所需迭片的冲裁主要采用套裁下料方式，较小圆形迭片可以直接从板材冲裁，较大圆形迭片则需要将大圆分成几块扇形迭片进行冲裁。下料问题属于NP-Hard的经典组合优化问题[1]。目前常用的方法主要有整数规划、线性规划、顺序法、进化算法等。Kyung等[2]采用启发式算法生成布局图，通过条带拼接方式生成整板布局，条带可放置同质件或异形件。此类布局方式由于条带不具有同质性，增加了操作的复杂性。Cui等[3-4]先后采用T形和三段布局，条带只包含同质圆片或扇片，采用动态规划方法生成T形和三段式布局图，使用线性规划方法求下料方案，最后还需对其中的小数解进行规整的操作。Melega等[5]求解具有顺序依赖的两阶段下料问题，使用列生成方法和分支定价法生成布局图。列生成法有利于求解需求数量较大的应用，但面对较多需求种类时计算时间往往会大幅度增加。Poldi等[6]在混合整数优化模型的基础上，对多周期优化问题进行了扩展，用残余启发式算法求解，结果表明可提高整个订单周期的材料利用率。曾志阳等[7]用并行遗传算法求解圆形迭片的下料问题，设计了单点交叉和双点变异的遗传操作，同时设计了自适应的交叉率和变异率，实验结果比一般的启发式方法结果更优。陈燕等[8]提出一种顺序分组启发式算法生成布局图，条带布局采用规范多级方式，实验结果表明该方法既可提高材料利用率，又可降低算法的复杂性。Benjaoran等[9]先用密集搜索算法生成一个布局图，然后利用遗传算法对布局图进行优化，最后用最佳拟合递减算法生成剩余需求的布局图。该方案虽然有效提高了板材利用率，但其生成布局图操作过多，在大规模下料时，时间复杂度较高。胡钢等[10]采用四块布局方式，并用基于价值修正的顺序启发式算法迭代生成下料方案，但该方案因加工工艺复杂而变得不实用。Cui等[11]用顺序启发式算法求解二维装箱问题来生成下料方案，通过价值调整公式对零件的价值进行调整，避免算法陷入局部最优情况来提高布局图的利用率。Liu等[12]提出一种改进的启发式排序算法生成多种布局图，通过主观方法和客观方法计算目标的权重，用来选择最佳布局图。Long等[13]设计了基于列生成的启发式算法求解钢板切割问题，首先用启发式方法求得解向下取整，然后通过调整启发式算法和列生成算法的不同顺序，对剩余问题进行求解。Awais等[14]针对不规则形状的下料问题，提出一种宽度填充启发式算法，将板材的宽度边、形状的长度边和重叠边进行分组，再用列生成的方法求解。该方法虽然提高了一定的利用率，但在面对大规模下料问题时，算法时间复杂度较大。

通过上文献分析可知，采用数学规划的方法，如整数规划、线性规划等，虽然可以精确地求得问题的解；但已有研究也表明，数学规划的列生成法对面大规模种类的下料问题，特别是有多种源材料规格时，由于布局图求解过程涉及的组合量巨大，难以保证在一定的时间内求得高质量的解[13]，因此，采用顺序价值校正的启发式方法仍是求解下料方案的主流研究方向。

与已有方法只考虑单种迭片的优化模型不同，本文构建的是迭片的套裁优化模型。在此基础上，以生成布局图的优化策略和选择策略为研究重点，将顺序价值校正法应用于求解多板材铁芯迭片下料问题，采用动态规划的递推方法求得布局图。与常用的最大值法(best value ，BV)选择布局图不同，本文提出最大比值法(best percentage，BP)对多规格板材的布局图进行选择。与已有单种迭片价值调整不同，本文提出了圆片和扇片2种迭片套裁的价值调整公式。

1 下料问题模型及相关概念

1.1 问题描述及数学模型

设所需迭片种类为H，包含m种圆片和n种扇片，H=m+n。第i种迭片为圆片，其直径为di，需求量为bi，其中i=1,2，…,m；第j种迭片为扇片，其外径为Rj，内径为rj，拼数为qj，需求量为cj，其中j=1,2，…,n。有M种可供使用的板材，板材的尺寸为Lg⊗Wg，板材的供应量为Dg,g=1,2,…,M。设已共有K个布局图，最优下料方案的整数线性规划模型表示如下：

(1)

(2)

(3)

(4)

(5)

1.2 相关概念

(a) 单排扇片

圆片和扇片均只允许最多3排，则圆片条带宽度种类最多有3m种，扇片由于可转置布局，则最多可有6n种，因此所有可能的条带宽度种类最多为(3m+6n)种。本文所讨论的布局图只考虑在板材的长边方向放置条带，所以每根条带的最大宽度加上允许的工艺余量不能超过板材的宽度。

2 算法设计与实现

经典下料问题的求解，存在下料方案和布局图的双层优化[1]，因此，首先详细介绍求解模型(1)所示套裁优化模型的下料方案算法步骤，然后说明单张板材上布局图的生成方法，最后给出选择当前最优布局图的策略，并提出多迭片的价值校正法。

2.1 下料方案算法

下料方案层面的优化，常用的方法主要有数学规划方法和基于SVC框架的顺序法[13]。算法描述如下。

输入：di，bi，Rj，rj，qj，cj，Lg，Wg，Dg，w

Step 1：令当前剩余迭片需求uh等于初始需求，令k=1，G=1，Gmax=100；

Step 2：若G0的板材调用2.2节的布局图生成方法，分别得到对应板材的最优布局图；

Step 3：调用2.3节的BV法或BP法从中选择最优的布局图作为下料方案的第k个布局图，令k=k+1；

Step 4：根据xk=min{uh/akh|akh>0}确定第k个布局图的使用次数；

Step 5：令uh=uh-xkakh更新剩余需求，令Dg=Dg-xk更新板材供应量；

Step 6：调用2.4节的顺序价值校正法对迭片的价值进行调整；

Step 7：重复Step 2到Step 5，直到所有剩余的迭片需求得到满足；

Step 8：保存当前最少材料消耗的下料方案作为最佳下料方案；

Step 9：G=G+1，转向Step 2；

输出：最佳下料方案。该方案包含k个布局图，组成模型(1)的K个布局图集合。

上述算法输入的w为工艺余料，Gmax为算法的最大迭代次数。Step 1初始化当前剩余迭片需求，当h=1,2,…,m时，uh=bi；当h=m+1,m+2,…,m+n时，uh=cj。此外，g=1,2,…,M。

2.2 布局图生成方法

布局图的生成是尽可能使板材所含迭片价值最大，可表示为

(6)

(7)

式中：vh为第h种迭片的单价；yh为布局图所含第h种迭片的数量；x和y分别为当前考察板材的长度和宽度；zt为布局图中含宽度为ψt的条带个数，令F(x,y)为该板材的最大价值，可用以下递推式获得

(8)

式中：η(x,y,h)表示子板材x⊗y所含第h种迭片的数量；uh表示第h种迭片的剩余需求；ψt表示当前考虑拼接的条带宽度，该条带的价值为λt，该值等于条带所含迭片的总价值；H和T分别为迭片种类数和条带宽度种类数。

根据输入的信息确定所有可行条带的数量T及相应的宽度ψt。p0记录最佳分段点，用Ω(x,y)和Ω(L-x,y)分别记录排放条带的编号，最后根据Ω(L,W)的值，即可确定组成最优方式的布局。当x=p0时，板材分为长度p0和L-p0两段，F(p0,W)和F(L-p0,W)分别表示两段子板材的最大值，条带均在板材宽度方向进行拼接。遍历所有分段点后，即可求得板材最大价值F(L,W)。

2.3 最大值(BV)法与最大比值(BP)法

在大规模板材种类的下料中，针对每种可用板材都使用当前的剩余需求获得一种最佳布局图。对多种布局图的选择策略不同，将会得到不同的下料方案。

①最大值(BV)法

目前大部分生成布局图的方法，通常采用BV法[11]。该方法每次根据布局图包含迭片价值最大来选择。如有g种布局图，则根据计算公式(9)选择，即

(9)

式中：agh为第g种布局所含h迭片的数量；Vg为布局图的价值；Bmax为当前考察布局图中价值最大者。

②最大比值(BP)法

BP法是依据布局图所含迭片价值与板材价值之比来选择。板材价值等于板材的面积。迭片的初始价值等于迭片的面积，当每次获得一个布局图后，迭片的价值由2.4节的顺序价值校正公式确定。如有g种布局图，则根据下面计算公式选择，即

(10)

式中：Pg为当前布局图所含迭片价值与板材价值之比；Lg、Wg分别为布局图所用板材的长度、宽度；Pmax为当前考察布局图中价值比最大者。

BV法是在每一步获得布局图后尽可能多地满足剩余迭片的需求，选择迭片价值之和最大的布局图，有利于减少下料方案的布局图数[11]；但由于下料方案是采用顺序满足迭片需求的方法，加上贪婪算法的特性，总是优先选择价值最大的布局，使得布局图利用率均衡性变差，使最先得到的布局图利用率较高、越到后面获得的布局图利用率越低，因此导致下料方案的整体利用率下降。

与BV法不同的是，BP法选择迭片价值与板材价值之比最大的布局图，使得每次确定当前布局图时优先考虑板材利用的均衡性，从而可保证下料方案的整体利用率较高，因此，2种方法均有各自优势，BV法有利于减少布局图数，而BP法有利于提高板材的利用率。在实际应用中可根据具体要求来选择不同的优化策略。

2.4 顺序价值校正法

迭片的初始价值仅等于其面积。顺序价值校正的基本思想是确定一种布局图后，要根据布局图利用率对毛坯的价值进行校正；然后按新价值对剩余毛坯继续生成新的布局图。价值校正法使迭片的选择具有多样化，扩大迭片组合的搜索空间，从而提高解的质量。目前已有不少应用价值校正法的成功案例[11]，但往往只考虑一种毛坯的价值的校正，而本文布局图采用的是圆片和扇片混合编排的方法，需要同时对2种毛坯的价值进行校正。

(11)

g1=1-g2，

(12)

(13)

(14)

式中：g1、g2为价值校正法公式的权重因子；rh、sh分别为第h种迭片的剩余需求和面积；μk为第k种布局图的利用率；L、W分别为第k种布局图使用板材的长度、宽度；δ和γ均为控制参数，取值范围分别为δ∈[1.01,1.05]和γ∈[0.6,0.9][11]。

3 实验

算法在Windows操作系统下采用C#编程语言实现，计算机为i5@2.2 GHz，内存为4 G。随机生成各10种迭片，圆片直径为[200,500]，需求量为[1 000,3 000]；扇片的外径[600,1 200]，内径[300,900]，拼数为{6,8,9}，需求量为[500,1 500]。直径单位均为mm。板材规格有3种：2 000 mm×1 000 mm、2 500 mm×1 250 mm、3 000 mm×1 500 mm。随机生成的迭片数据如表1所示。系数δ=1.03，γ=0.75，w=0，Gmax=100。

根据表1的迭片信息随机生成10组迭片需求用于实验测试。具体组合见表2，其中圆片和扇片的编号分别对应表1中的编号。

表1 随机生成的迭片数据Tab.1 Randomly generated lamination data

表2 测试用的10组数据Tab.2 10 sets of data for the test

3.1 布局图选择算法对利用率的影响

BV法与BP法的利用率比较见表3，其中Δ表示采用BP法与BV法的利用率差值。从表中可见，与BV法相比，BP法的板材利用率总体上平均提高了1.04%。

表3 BV法与BP法的利用率比较Tab.3 Comparison of utilization ratio between BV and BP

对于表3中第5组算例，给出运用BP法得到的下料方案如图2所示。图中数字为所使用迭片的编号，图片下方的数字分别为布局图的长、宽和该布局图使用次数。

(a) 3 000*1 500*39

(d) 3 000*1 500*1

(g) 2 000*1 000*1

3.2 布局图选择算法对布局图数的影响

表4为BV法与BP法的布局图数比较，其中Δ表示采用BP法与BV法的差值。从表中可看出，与BV法相比，BP法的布局图数有小幅增加，平均增加3至4个布局图。

表4 BV法与BP法的布局图数比较Tab.4 Comparison of BV and BP algorithm in layout number

通过以上测试结果的分析，BP法可减少布局图数，减少生产操作成本；而BV法可获得较高利用率可减少材料成本。在实际生产中，企业需要权衡多个布局图数产生的操作成本与利用率提高节约的材料成本，选择合适的下料方法。

4 结语

下料问题在制造业中广泛出现，大中型发电机定子和转子制造所需迭片的冲裁主要采用套裁下料方式。本文根据企业的实际生产需求，构建铁芯迭片套裁下料问题的数学模型，采用经典的顺序价值校正框架求解。与已有方法只考虑单种迭片的优化模型不同，本文构建的是2种迭片的套裁优化模型，提出了混合迭片的价值调整公式法。与目前常用的最大值BV法选择布局图不同，本文提出的最大比值BP法可获得较高的材料利用率。论文提供了生成布局图的伪代码，给出了套裁迭片的价值调整公式，说明了求解下料方案的具体步骤，可对企业的实际生产下料具有参考的价值和实践指导的意义。