陳燕*,2，龔俊舟，王婷婷，張立

(1.廣西大學計算機與電子信息學院， 廣西南寧530004；2.華南理工大學工商管理學院， 廣東廣州510640)

0 引言

在電機制造過程中，需要將硅鋼片切割成圓片用于加工成定子和轉子[1]。圓片下料問題是在滿足圓片需求的同時最小化廢料的產(chǎn)生，不僅可降低企業(yè)生產(chǎn)成本，而且對環(huán)境保護和資源節(jié)約有重要意義。

電機制造行業(yè)的圓片下料采用兩階段下料工藝，第一階段是剪切操作，使用板材滾剪或平剪切成條帶；第二階段為沖裁階段，即用沖床從條帶上沖出圓片。針對圓片下料問題的研究已有多種算法：文獻[2]采用動態(tài)規(guī)劃算法和隱式枚舉法生成最優(yōu)的四塊排樣方式；文獻[3]采用動態(tài)規(guī)劃算法和基于列生成的線性規(guī)劃生成下料方案；文獻[4]采用順序啟發(fā)式算法對圓片下料問題進行求解；文獻[5]在基于順序啟發(fā)式的基礎上引入了分組思想求解圓片下料問題。文獻[6]采用自適應遺傳算法和模擬退火算法結合求解板材上的圓片下料問題。文獻[7]采用基于橡皮筋勢能下降策略的排樣算法求解圓形鈑金制品下料問題。上述文獻大多是將板材切割成矩形條帶，此外還可以將板材切割成平行四邊形條帶。文獻[8]提出梯形和平行四邊形條帶組合的方式來求解圓片下料問題。文獻[9]考慮了生成余料的下料問題，但只是針對單次訂單的下料方案進行研究，沒有考慮余料庫存的約束。

本文針對圓片下料問題，以符合工廠實際生產(chǎn)的單向直切下料工藝，運用遞推思想，結合順序價值修正方法，提出一種考慮余料利用的多規(guī)格板材電機圓片下料算法，考慮連續(xù)多周期訂單生產(chǎn)過程中余料庫存控制對多種類型板材利用率的影響，利用余料作為庫存緩沖，提高板材利用率。實驗結果表明，允許主動生成余料策略與不允許生成余料策略相比、利用多種規(guī)格板材與利用單種規(guī)格板材相比，材料利用率都有明顯提高;應用主動生成余料與不主動生成余料的策略相比，板材利用率也有明顯提高。

1 數(shù)學模型

1.1 問題描述與建模

在一般的生產(chǎn)情況中，電機生產(chǎn)廠會進貨多種規(guī)格的硅鋼板材。在滿足訂單所需圓片的基礎上，盡可能地提高材料利用率。設進貨的硅鋼板材種類數(shù)為N，Ln和Wn為第n種板材的長度和寬度，其中n=1,…,N。常規(guī)的生產(chǎn)過程中，一段生產(chǎn)時間內(nèi)產(chǎn)出的圓片種類是重復的，設為M種(10～15種)。設訂單需求的圓片種類數(shù)為m(m0)為第i種圓片的需求量，其中i=1,2,…,m。

本文針對上述問題的下料策略為：因使用余料條帶可直接沖出標準直徑的圓片，不需要進行縱剪操作，所以當前生產(chǎn)的訂單優(yōu)先使用余料條帶；允許主動生成余料條帶，新生成的余料條帶加入余料庫存供后續(xù)訂單使用，充分發(fā)揮余料庫存的緩沖作用。余料庫存中，余料條帶的種類數(shù)不能超過長期需求的圓片種類數(shù)，即小于M種。設分類庫存上限約束σ限制每一種余料條帶的數(shù)量，設總庫存上限約束Ψ限制余料條帶的總數(shù)量。

將期初作為當前下料活動的開始，開始時的余料庫存稱為期初余料庫存，設bi為圓片的期初需求，li(li

根據(jù)上述問題為期初剩余需求li求解的下料方案數(shù)學模型為：

(1)

(2)

(3)

(4)

σk≤σ，k=1,2,…,M,

(5)

(6)

上述數(shù)學模型中，J是排樣圖集合，Sj是第j種排樣圖的余料條帶面積，xj是第j種排樣圖的使用頻率，α(j)=n表示第j種排樣圖是由第n種板材生成的。式(1)的優(yōu)化目標為最小化板材消耗總面積，其值等于消耗整板板材的總面積與余料面積之差;式(2)約束產(chǎn)出的圓片數(shù)量大于或等于期初剩余需求量li;式(3)約束排樣圖的使用頻率小于使用的板材數(shù)量;式(4)表示所有余料條帶數(shù)量之和小于或等于余料總庫存Ψ;式(5)約束每種新入庫的余料數(shù)量小于其分類庫存上限σ;式(6)表示排樣圖的使用次數(shù)必須為整數(shù)。

1.2 相關概念

① 條帶及圓片布局：一根或多根水平條帶組成板材，每根條帶包含一排或多排大小相同的圓片，圓片在條帶中的布局最多為3排，圖1是單排條帶，圖2是雙排條帶。令圓片的直徑為di，圓片到邊界的最小距離為δ/2，相鄰圓片間的距離為δ，其中δ稱作工藝余量，圓片多于1排時,上下兩排的圓心相連構成一個等邊三角形。第i種g排圓片條帶寬度為wig=「(di+δ)(1+(g-1)sin60°)?。

圖1 單排條帶Fig.1 One-row strip

圖2 雙排條帶Fig.2 Two-row strip

② 余料條帶：每根余料條帶包含的圓片是前述M種常生產(chǎn)的圓片之一，此種類型的圓片不在當前訂單的需求中。同一種余料條帶可以有不同的寬度，因為其中包含的不同排數(shù)。其中，在當前訂單中產(chǎn)生的余料條帶稱為新余料條帶，其入庫供后續(xù)訂單使用，并不在當前下料方案中使用。在過去的訂單中產(chǎn)生的余料條帶稱為舊余料，該條帶可用于滿足當前訂單及后續(xù)訂單的下料需求。

③ 排樣方式和排樣方案：圓片在板材上的排列布局稱為“排樣方式”或“布局圖”，一種排樣方式就是具體下料時的“切割圖樣”。給訂單需求的所有圓片確定在板材上的切割下料方案就稱為“排樣方案或下料方案”。一個下料方案包含一種或多種具體的排樣方式及其使用頻率。

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

算法涉及的部分參數(shù)如下：

G：當前迭代次數(shù)，表示當前在生成第G個下料方案。

Gmax：最大迭代次數(shù)。

vi：第i種圓片的單價，i=1,2,…,m。

σk：第k種余料條帶的當前庫存根數(shù)，0≤σk<σ，k=1,2,…,M。

fn：第n種板材排樣圖的使用次數(shù)，n=1,2,…,N。

Zbest：當前最好下料方案的總成本。

2.1 排樣圖生成函數(shù)GetPattern()

通過枚舉所有可能的條帶，在板材的長邊布局一根余料，以使布局圖的產(chǎn)出率達到最大。生成排樣圖的數(shù)學模型表示為：

(7)

(8)

(9)

(10)

上述模型為有約束的背包問題，其中vi為圓片的單價，λi為板材內(nèi)有效圓片的數(shù)量，zi為當前排樣圖所含圓片數(shù)量，li為圓片剩余需求量，其中i=1,2,…,m；K為當前剩余需求圓片對應的所有可行條帶的種類數(shù)，wt為條帶寬度，χt為條帶數(shù)量，其中t=1,2,…,K。式子(7)表示模型優(yōu)化目標是使板材價值利用率最大化，即板材包含有效圓片的總價值最大；式子(8)表示當前排樣圖所含第i種圓片數(shù)量等于所有條帶所包含的同種圓片數(shù)量；式子(9)表示第i種圓片的有效個數(shù)是剩余需求li與實際布局的圓片個數(shù)zi兩者中的較小值；式子(10)約束排樣圖中條帶組合后的總寬度不大于板材的寬度。

圖3是一個包含余料的排樣圖，其中有2條當前訂單需求條帶和1條余料條帶。

圖3 一個包含余料的排樣圖Fig.3 A cutting pattern with leftover

具體的求解過程如下所述：

step 1：令n=0，最優(yōu)布局圖的產(chǎn)出率Obest初始化為零，即Obest=0。

step 2：若n=N，轉step 6；否則令n=n+1，轉step 3。

step 3：若qn=0，轉step 2；否則求當前剩余需求圓片的一個最優(yōu)排樣圖，在長寬為Ln?Wn的板材從寬度方向上進行遍歷條帶拼接，每次只拼接一根條帶，直到組成整張板材上的排樣圖Pn，此時所有拼接的條帶寬度之和必須小于Wn，并記錄此種不拼接余料條帶的排樣圖產(chǎn)出率On。

step 4：遍歷庫存中所有的余料條帶，在當前規(guī)格板材上從寬度方向上進行遍歷余料條帶拼接，每只拼接一根余料條帶，記錄其中最大產(chǎn)出率O0n和其排樣圖P0n，并記錄用來拼接的余料條帶。

step 5：將當前最大產(chǎn)出率Obest、無余料條帶排樣圖的產(chǎn)出率On和有余料條帶排樣圖的產(chǎn)出率O0n三者進行比較，把其中最大者記為當前最大產(chǎn)出率Obest，并把Obest對應的排樣圖記為當前最好排樣圖Pbest。令n=n+1，轉step 2。

step 6：輸出當前最大產(chǎn)出率Obest和最優(yōu)排樣圖Pbest。

在確定最優(yōu)排樣圖后，排樣圖的使用頻率確認分為兩種情況：

① 最優(yōu)排樣圖中沒有產(chǎn)生余料條帶，根據(jù)式(11)確定最優(yōu)排樣圖的使用頻率。

② 最優(yōu)排樣圖中含第k種余料，根據(jù)式(12)確定最優(yōu)排樣圖的使用頻率。

(11)

(12)

2.2 圓片價值修正函數(shù)CorrectValue()

單一的順序法求解下料方案的過程中不改變圓片的價值，只會產(chǎn)生單一的下料方案。為了得到利用率更高的排樣方案，在生成當前排樣方式之后，需要根據(jù)剩余圓片種類和需求量調(diào)整圓片的價值，使之生成多種不同的排樣方式。本文采用的圓片價值修正公式如下：

(13)

(14)

(15)

其中Ω和p均為控制參數(shù)，u為當前布局圖的板材利用率，si為第i種圓片的單片面積，p=1.03，Ω=0.75。

2.3 下料方案生成算法

允許在板材上布局一根水平方向的余料(圖3)，下料方案生成算法步驟如下：

Step 1：令G=0；初始化vi為圓片面積，其中i=1,2,…,m；初始化最好下料方案總成本Zbest=+∞。

Step 2：若G=Gmax，轉step 9；否則G=G+1。

Step 4：調(diào)用GetPattern()函數(shù)生成排樣圖Pbest，記錄該排樣圖使用頻率fn，n=1,2,…,N。

Step 5：將排樣圖Pbest加入當前下料方案，更新圓片剩余需求量li=li-fnyi，i=1,2,…,m。更新第n種板材的數(shù)量qn=qn-fn。若當前排樣圖中含有第k種余料條帶，則令余料的當前分庫存σk=σk+fn，當前總庫存φ=φ+fn。

Step 6：調(diào)用CorrectValue()函數(shù)修正圓片價值。

Step 7：如果存在li>0，其中i=1,2,…,m，即圓片需求量還未滿足，轉step 4。

Step 8：若當前下料方案總成本小于最好下料方案總成本，即Z

Step 9：輸出最好的下料方案。

3 實驗

本文算法基于C#語言實現(xiàn)，電腦配置為CPU Intel(R) CoreTMi7-5500U 2.4 GHz，RAM 8 GB，程序在操作系統(tǒng)WIN10上執(zhí)行。根據(jù)電機行業(yè)實際生產(chǎn)情況，對某電機廠實際生產(chǎn)中的30個連續(xù)訂單(訂單數(shù)據(jù)詳見附表1)，分別應用有余料策略和無余料策略，分析幾種不同板材使用時消耗面積和節(jié)材率的不同。其中：

有余料策略：在排樣過程中允許主動生成規(guī)范余料條帶；

無余料策略：在排樣過程中不允許主動產(chǎn)生余料條帶。

3.1 單板材實驗數(shù)據(jù)分析

分別使用3種不同尺寸的標準板材2 000×1 000、2 500×1 000和2 000×1 500，應用上述兩種策略給30個連續(xù)訂單確定下料方案，消耗的板材面積和節(jié)材率如表1所示。

表1 單種板材組合的節(jié)材率Tab.1 Cost saving rate of one types of sheet

tN和LT分別表示兩種策略為每個訂單求解下料方案所需要的平均運行時間。SN和SL分別表示應用兩種策略所消耗的板材總面積。ΔS表示應用有余料策略對無余料策略的節(jié)材率，其值為ΔS=[(SN-SL)/SN]×100 %。UN和UL分別表示應用兩種策略30個訂單的總體利用率。ΔU表示無余料兩種策略的利用率的差值，其值為ΔU=UL-UN。

從表1可看出，同一訂單下使用三種不同規(guī)格板材的節(jié)材效果不同，最低的是第三種板材，差不多達到了2 %，最高是第二種板材，達到5 %以上，三種板材的節(jié)材率平均達到3.24 %。在以上三種板材計算30個訂單的平均時間分別是2.90、3.36、2.78 s，都在較短時間內(nèi)完成。因此，對采購板材種類數(shù)的建議為，按照實際訂單情況對所有規(guī)格板材進行下料預計算，根據(jù)計算結果指導采購選擇。

3.2 雙板材實驗數(shù)據(jù)分析

將上述三種板材進行兩兩組合，分析兩種板材組合的節(jié)材率。分別應用有余料和無余料兩種策略給上述的例題下料，消耗的板材面積和節(jié)材率如表2所示。從表2中可知，不同尺寸的板材組合供同一訂單下料，節(jié)材率的差別不如單板材的大。兩兩組合的平均節(jié)均率為2.54 %，比單板材的平均節(jié)材率3.24 %稍低，原因是其中兩種板材的利用率較低。

表2 兩種板材組合的節(jié)材率Tab.2 Cost saving rate of two types of sheets

3.3 三種板材實驗數(shù)據(jù)分析

針對上述實驗訂單，分別應用有余料條帶策略和無余料條帶策略，使用三種板材同時進行優(yōu)化組合下料，消耗的板材面積和節(jié)材率見表3。從表3中可知，僅有兩種板材供下料的節(jié)材率2.54 %，略高于三種板材同時供下料選擇時的節(jié)材率2.35 %，原因是其中兩種板材組合的利用率較低。

表3 三種板材組合的節(jié)材率Tab.3 Cost saving rate of three types of sheets

在多規(guī)格板材可供下料時，不同板材下料方案的平均消耗成本如表4所示。其中板材種類1代表單板材、種類2代表兩種板材、種類3代表三種板材。S總表示板材消耗總面積，ΔS總表示不同板材種類數(shù)所消耗的板材面積的差值。例如第二行第二列的ΔS總值等于S總列中第二行減去第一行的差值，即26 285.0-27 510.9=1 225.9。因此第一行的ΔS總為空值，用“-”表示。U表示不同板材組合使用時，企業(yè)長期下料使用板材的利用率，ΔU表示不同種類板材利用率的差值。ΔU的計算方法與ΔS總計算方法類似，第二行的ΔU值等于U的第二行的值減去第一行的值。

表4 三種組合方式的平均消耗成本Tab.4 Average consumption cost of three combination mode

圖4 板材利用率和板材種類數(shù)的關系Fig.4 Relations between utilization and species number of sheets

從表4可知，隨著可供下料使用的板材種類數(shù)增多，板材利用率在逐步提高。只有一種板材供選擇時，利用率不到70 %；三種板材可供下料時，利用率差不多達到了74 %，比只有一種板材時提高約4 %。

根據(jù)上述三個表的數(shù)據(jù)繪制了圖4，從圖4可知，隨著板材種類數(shù)的增多，板材利用率的提升速度是變慢的。但板材利用率變化與板材種類數(shù)的關系并不是直線上升、而是呈折線上升狀態(tài)，其斜率逐漸漸變小、板材利用率上升趨勢變慢。因此，在條件允許時建議企業(yè)可定購多種規(guī)格板材，但不需要太多，通常在3種左右，板材利用率就會有明顯的提升。

4 結論

本文針對圓片的單向直切下料問題，提出多規(guī)格板材的順序優(yōu)化排樣算法，主動考慮余料的生成，并控制余料產(chǎn)生的數(shù)量緩沖庫存。在保證直切下料工藝簡單性的前提下，應用本文算法可使長期生產(chǎn)的材料利用率得到較為明顯的提高。利用余料的控制策略，可供電機生產(chǎn)廠及不銹鋼制品業(yè)參考。