鐵芯迭片的多板材下料優(yōu)化策略研究

陳燕，寧曉軍，胡小春，蔣志一

(1.廣西大學計算機與電子信息學院， 廣西南寧530004；2.廣西財經(jīng)學院信息與統(tǒng)計學院， 廣西南寧530007;3.廣西多媒體通信與網(wǎng)絡技術重點實驗室， 廣西南寧530004)

0 引言

大中型發(fā)電機定子和轉(zhuǎn)子制造所需迭片的沖裁主要采用套裁下料方式，較小圓形迭片可以直接從板材沖裁，較大圓形迭片則需要將大圓分成幾塊扇形迭片進行沖裁。下料問題屬于NP-Hard的經(jīng)典組合優(yōu)化問題[1]。目前常用的方法主要有整數(shù)規(guī)劃、線性規(guī)劃、順序法、進化算法等。Kyung等[2]采用啟發(fā)式算法生成布局圖，通過條帶拼接方式生成整板布局，條帶可放置同質(zhì)件或異形件。此類布局方式由于條帶不具有同質(zhì)性，增加了操作的復雜性。Cui等[3-4]先后采用T形和三段布局，條帶只包含同質(zhì)圓片或扇片，采用動態(tài)規(guī)劃方法生成T形和三段式布局圖，使用線性規(guī)劃方法求下料方案，最后還需對其中的小數(shù)解進行規(guī)整的操作。Melega等[5]求解具有順序依賴的兩階段下料問題，使用列生成方法和分支定價法生成布局圖。列生成法有利于求解需求數(shù)量較大的應用，但面對較多需求種類時計算時間往往會大幅度增加。Poldi等[6]在混合整數(shù)優(yōu)化模型的基礎上，對多周期優(yōu)化問題進行了擴展，用殘余啟發(fā)式算法求解，結果表明可提高整個訂單周期的材料利用率。曾志陽等[7]用并行遺傳算法求解圓形迭片的下料問題，設計了單點交叉和雙點變異的遺傳操作，同時設計了自適應的交叉率和變異率，實驗結果比一般的啟發(fā)式方法結果更優(yōu)。陳燕等[8]提出一種順序分組啟發(fā)式算法生成布局圖，條帶布局采用規(guī)范多級方式，實驗結果表明該方法既可提高材料利用率，又可降低算法的復雜性。Benjaoran等[9]先用密集搜索算法生成一個布局圖，然后利用遺傳算法對布局圖進行優(yōu)化，最后用最佳擬合遞減算法生成剩余需求的布局圖。該方案雖然有效提高了板材利用率，但其生成布局圖操作過多，在大規(guī)模下料時，時間復雜度較高。胡鋼等[10]采用四塊布局方式，并用基于價值修正的順序啟發(fā)式算法迭代生成下料方案，但該方案因加工工藝復雜而變得不實用。Cui等[11]用順序啟發(fā)式算法求解二維裝箱問題來生成下料方案，通過價值調(diào)整公式對零件的價值進行調(diào)整，避免算法陷入局部最優(yōu)情況來提高布局圖的利用率。Liu等[12]提出一種改進的啟發(fā)式排序算法生成多種布局圖，通過主觀方法和客觀方法計算目標的權重，用來選擇最佳布局圖。Long等[13]設計了基于列生成的啟發(fā)式算法求解鋼板切割問題，首先用啟發(fā)式方法求得解向下取整，然后通過調(diào)整啟發(fā)式算法和列生成算法的不同順序，對剩余問題進行求解。Awais等[14]針對不規(guī)則形狀的下料問題，提出一種寬度填充啟發(fā)式算法，將板材的寬度邊、形狀的長度邊和重疊邊進行分組，再用列生成的方法求解。該方法雖然提高了一定的利用率，但在面對大規(guī)模下料問題時，算法時間復雜度較大。

通過上文獻分析可知，采用數(shù)學規(guī)劃的方法，如整數(shù)規(guī)劃、線性規(guī)劃等，雖然可以精確地求得問題的解；但已有研究也表明，數(shù)學規(guī)劃的列生成法對面大規(guī)模種類的下料問題，特別是有多種源材料規(guī)格時，由于布局圖求解過程涉及的組合量巨大，難以保證在一定的時間內(nèi)求得高質(zhì)量的解[13]，因此，采用順序價值校正的啟發(fā)式方法仍是求解下料方案的主流研究方向。

與已有方法只考慮單種迭片的優(yōu)化模型不同，本文構建的是迭片的套裁優(yōu)化模型。在此基礎上，以生成布局圖的優(yōu)化策略和選擇策略為研究重點，將順序價值校正法應用于求解多板材鐵芯迭片下料問題，采用動態(tài)規(guī)劃的遞推方法求得布局圖。與常用的最大值法(best value ，BV)選擇布局圖不同，本文提出最大比值法(best percentage，BP)對多規(guī)格板材的布局圖進行選擇。與已有單種迭片價值調(diào)整不同，本文提出了圓片和扇片2種迭片套裁的價值調(diào)整公式。

1 下料問題模型及相關概念

1.1 問題描述及數(shù)學模型

設所需迭片種類為H，包含m種圓片和n種扇片，H=m+n。第i種迭片為圓片，其直徑為di，需求量為bi，其中i=1,2，…,m；第j種迭片為扇片，其外徑為Rj，內(nèi)徑為rj，拼數(shù)為qj，需求量為cj，其中j=1,2，…,n。有M種可供使用的板材，板材的尺寸為Lg?Wg，板材的供應量為Dg,g=1,2,…,M。設已共有K個布局圖，最優(yōu)下料方案的整數(shù)線性規(guī)劃模型表示如下：

(1)

(2)

(3)

(4)

(5)

1.2 相關概念

(a) 單排扇片

圓片和扇片均只允許最多3排，則圓片條帶寬度種類最多有3m種，扇片由于可轉(zhuǎn)置布局，則最多可有6n種，因此所有可能的條帶寬度種類最多為(3m+6n)種。本文所討論的布局圖只考慮在板材的長邊方向放置條帶，所以每根條帶的最大寬度加上允許的工藝余量不能超過板材的寬度。

2 算法設計與實現(xiàn)

經(jīng)典下料問題的求解，存在下料方案和布局圖的雙層優(yōu)化[1]，因此，首先詳細介紹求解模型(1)所示套裁優(yōu)化模型的下料方案算法步驟，然后說明單張板材上布局圖的生成方法，最后給出選擇當前最優(yōu)布局圖的策略，并提出多迭片的價值校正法。

2.1 下料方案算法

下料方案層面的優(yōu)化，常用的方法主要有數(shù)學規(guī)劃方法和基于SVC框架的順序法[13]。算法描述如下。

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

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

Step 2：若G0的板材調(diào)用2.2節(jié)的布局圖生成方法，分別得到對應板材的最優(yōu)布局圖；

Step 3：調(diào)用2.3節(jié)的BV法或BP法從中選擇最優(yōu)的布局圖作為下料方案的第k個布局圖，令k=k+1；

Step 4：根據(jù)xk=min{uh/akh|akh>0}確定第k個布局圖的使用次數(shù)；

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

Step 6：調(diào)用2.4節(jié)的順序價值校正法對迭片的價值進行調(diào)整；

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

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

Step 9：G=G+1，轉(zhuǎn)向Step 2；

輸出：最佳下料方案。該方案包含k個布局圖，組成模型(1)的K個布局圖集合。

上述算法輸入的w為工藝余料，Gmax為算法的最大迭代次數(shù)。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種迭片的數(shù)量；x和y分別為當前考察板材的長度和寬度；zt為布局圖中含寬度為ψt的條帶個數(shù)，令F(x,y)為該板材的最大價值，可用以下遞推式獲得

(8)

式中：η(x,y,h)表示子板材x?y所含第h種迭片的數(shù)量；uh表示第h種迭片的剩余需求；ψt表示當前考慮拼接的條帶寬度，該條帶的價值為λt，該值等于條帶所含迭片的總價值；H和T分別為迭片種類數(shù)和條帶寬度種類數(shù)。

根據(jù)輸入的信息確定所有可行條帶的數(shù)量T及相應的寬度ψt。p0記錄最佳分段點，用Ω(x,y)和Ω(L-x,y)分別記錄排放條帶的編號，最后根據(jù)Ω(L,W)的值，即可確定組成最優(yōu)方式的布局。當x=p0時，板材分為長度p0和L-p0兩段，F(xiàn)(p0,W)和F(L-p0,W)分別表示兩段子板材的最大值，條帶均在板材寬度方向進行拼接。遍歷所有分段點后，即可求得板材最大價值F(L,W)。

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

在大規(guī)模板材種類的下料中，針對每種可用板材都使用當前的剩余需求獲得一種最佳布局圖。對多種布局圖的選擇策略不同，將會得到不同的下料方案。

①最大值(BV)法

目前大部分生成布局圖的方法，通常采用BV法[11]。該方法每次根據(jù)布局圖包含迭片價值最大來選擇。如有g種布局圖，則根據(jù)計算公式(9)選擇，即

(9)

式中：agh為第g種布局所含h迭片的數(shù)量；Vg為布局圖的價值；Bmax為當前考察布局圖中價值最大者。

②最大比值(BP)法

BP法是依據(jù)布局圖所含迭片價值與板材價值之比來選擇。板材價值等于板材的面積。迭片的初始價值等于迭片的面積，當每次獲得一個布局圖后，迭片的價值由2.4節(jié)的順序價值校正公式確定。如有g種布局圖，則根據(jù)下面計算公式選擇，即

(10)

式中：Pg為當前布局圖所含迭片價值與板材價值之比；Lg、Wg分別為布局圖所用板材的長度、寬度；Pmax為當前考察布局圖中價值比最大者。

BV法是在每一步獲得布局圖后盡可能多地滿足剩余迭片的需求，選擇迭片價值之和最大的布局圖，有利于減少下料方案的布局圖數(shù)[11]；但由于下料方案是采用順序滿足迭片需求的方法，加上貪婪算法的特性，總是優(yōu)先選擇價值最大的布局，使得布局圖利用率均衡性變差，使最先得到的布局圖利用率較高、越到后面獲得的布局圖利用率越低，因此導致下料方案的整體利用率下降。

與BV法不同的是，BP法選擇迭片價值與板材價值之比最大的布局圖，使得每次確定當前布局圖時優(yōu)先考慮板材利用的均衡性，從而可保證下料方案的整體利用率較高，因此，2種方法均有各自優(yōu)勢，BV法有利于減少布局圖數(shù)，而BP法有利于提高板材的利用率。在實際應用中可根據(jù)具體要求來選擇不同的優(yōu)化策略。

2.4 順序價值校正法

迭片的初始價值僅等于其面積。順序價值校正的基本思想是確定一種布局圖后，要根據(jù)布局圖利用率對毛坯的價值進行校正；然后按新價值對剩余毛坯繼續(xù)生成新的布局圖。價值校正法使迭片的選擇具有多樣化，擴大迭片組合的搜索空間，從而提高解的質(zhì)量。目前已有不少應用價值校正法的成功案例[11]，但往往只考慮一種毛坯的價值的校正，而本文布局圖采用的是圓片和扇片混合編排的方法，需要同時對2種毛坯的價值進行校正。

(11)

g1=1-g2，

(12)

(13)

(14)

式中：g1、g2為價值校正法公式的權重因子；rh、sh分別為第h種迭片的剩余需求和面積；μk為第k種布局圖的利用率；L、W分別為第k種布局圖使用板材的長度、寬度；δ和γ均為控制參數(shù)，取值范圍分別為δ∈[1.01,1.05]和γ∈[0.6,0.9][11]。

3 實驗

算法在Windows操作系統(tǒng)下采用C#編程語言實現(xiàn)，計算機為i5@2.2 GHz，內(nèi)存為4 G。隨機生成各10種迭片，圓片直徑為[200,500]，需求量為[1 000,3 000]；扇片的外徑[600,1 200]，內(nèi)徑[300,900]，拼數(shù)為{6,8,9}，需求量為[500,1 500]。直徑單位均為mm。板材規(guī)格有3種：2 000 mm×1 000 mm、2 500 mm×1 250 mm、3 000 mm×1 500 mm。隨機生成的迭片數(shù)據(jù)如表1所示。系數(shù)δ=1.03，γ=0.75，w=0，Gmax=100。

根據(jù)表1的迭片信息隨機生成10組迭片需求用于實驗測試。具體組合見表2，其中圓片和扇片的編號分別對應表1中的編號。

表1 隨機生成的迭片數(shù)據(jù)Tab.1 Randomly generated lamination data

表2 測試用的10組數(shù)據(jù)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所示。圖中數(shù)字為所使用迭片的編號，圖片下方的數(shù)字分別為布局圖的長、寬和該布局圖使用次數(shù)。

(a) 3 000*1 500*39

(d) 3 000*1 500*1

(g) 2 000*1 000*1

3.2 布局圖選擇算法對布局圖數(shù)的影響

表4為BV法與BP法的布局圖數(shù)比較，其中Δ表示采用BP法與BV法的差值。從表中可看出，與BV法相比，BP法的布局圖數(shù)有小幅增加，平均增加3至4個布局圖。

表4 BV法與BP法的布局圖數(shù)比較Tab.4 Comparison of BV and BP algorithm in layout number

通過以上測試結果的分析，BP法可減少布局圖數(shù)，減少生產(chǎn)操作成本；而BV法可獲得較高利用率可減少材料成本。在實際生產(chǎn)中，企業(yè)需要權衡多個布局圖數(shù)產(chǎn)生的操作成本與利用率提高節(jié)約的材料成本，選擇合適的下料方法。

4 結語

下料問題在制造業(yè)中廣泛出現(xiàn)，大中型發(fā)電機定子和轉(zhuǎn)子制造所需迭片的沖裁主要采用套裁下料方式。本文根據(jù)企業(yè)的實際生產(chǎn)需求，構建鐵芯迭片套裁下料問題的數(shù)學模型，采用經(jīng)典的順序價值校正框架求解。與已有方法只考慮單種迭片的優(yōu)化模型不同，本文構建的是2種迭片的套裁優(yōu)化模型，提出了混合迭片的價值調(diào)整公式法。與目前常用的最大值BV法選擇布局圖不同，本文提出的最大比值BP法可獲得較高的材料利用率。論文提供了生成布局圖的偽代碼，給出了套裁迭片的價值調(diào)整公式，說明了求解下料方案的具體步驟，可對企業(yè)的實際生產(chǎn)下料具有參考的價值和實踐指導的意義。