一種可變規(guī)格板材下料的優(yōu)化方法

陳 奇，曹德列，饒運清

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

（華中科技大學(xué) 數(shù)字制造裝備與技術(shù)國家重點實驗室，武漢 430074）

0 引言

零件在一批大小和成本不同的板材上下料（可變規(guī)格板材下料）的問題普遍存在于板材加工類企業(yè)下料生產(chǎn)中?？勺円?guī)格板材下料對板材規(guī)格不限定，可以是不同形狀、不同大小的矩形板材或者不規(guī)則板材，以及存在內(nèi)部缺陷的非完整板材。由于需要統(tǒng)籌兼顧大小和成本不同的板材，可變規(guī)格板材下料相對于傳統(tǒng)同規(guī)格板材下料能獲得更為節(jié)省的下料方案。

可變規(guī)格板材下料注重于板材選擇和排樣布局的統(tǒng)籌最優(yōu)，是一種組合優(yōu)化問題，具有較高的復(fù)雜度。當(dāng)前板材下料方面的研究多針對單張板材限定長寬或不限長度或者針對多張相同板材[1~4]，研究具體的排放算法而未能有效考慮不同規(guī)格板材的使用情況。Remesh Babu[5,6]等利用遺傳算法給出了多張不同板材時的排樣優(yōu)化方法，然而目標(biāo)函數(shù)只分析了材料面積未計入板材的使用數(shù)量，同時也沒有涉及到板材成本不同的情況。從可變大小二維裝箱問題的角度，Teodor Gabriel Crainic[7]利用箱子單位大小的成本進(jìn)行分析，但是沒有優(yōu)化箱子的序列選擇也沒有協(xié)調(diào)優(yōu)化箱子之間的裝箱效果。

由于該類組合優(yōu)化問題屬于NP-難問題，不存在多項式時間的算法，但遺傳算法在求解這類問題上效果突出。鑒于此，本文針對可變規(guī)格板材下料問題，以下料方案對應(yīng)的成本最優(yōu)為目標(biāo)，利用遺傳算法優(yōu)化板材序列和零件序列，并在解碼過程以模擬退火方式對排樣板材間零件加以優(yōu)化調(diào)整提高板材總體利用率，得到最終下料方案。

1 問題分析

有m種大小和成本各異的板材B1，B2，…，Bm，每種 NB1，NB2，…，NBm張，每種成本為 C1，C2，…，Cm。板材的單位質(zhì)量成本不完全相同?，F(xiàn)需要將n個零件P1，P2，…，Pn全部排放在板材上，任一板材都能完全覆蓋任一零件，板材為所給板材中的一張或幾張，要求下料方案最優(yōu)。

下料生產(chǎn)存在各種成本，和板材數(shù)量相關(guān)的有板材啟動成本、工人上下料作業(yè)成本等。傳統(tǒng)以最大化板材利用率為目標(biāo)的研究具有一定局限性。板材選擇使用需要以合理方式權(quán)衡板材利用率和板材使用數(shù)量。本文以板材成本統(tǒng)一考慮板材利用率和使用數(shù)量。為增強(qiáng)對板材使用數(shù)量的控制，引進(jìn)板材加工過程的中間成本。中間成本包括板材啟動成本和工人上下料作業(yè)成本。本文下料方案成本由板材成本和中間成本兩部分構(gòu)成。

余料在下次下料時仍可使用，計算板材成本時相應(yīng)扣除。余料成本利用原板材成本按余料面積占原板材面積百分比計算。設(shè)可用余料面積與板材面積比值為ηi，則余料成本為ηiCi。設(shè)中間成本相同，為Cs。數(shù)學(xué)模型為：

式中，Ni為板材Bi使用數(shù)量，Ni＜NBi。n為使用的板材種類，m為生成的余料數(shù)量。式中ηi和板材利用率相關(guān)，ηi越大利用率越高，所用板材相對越少，材料成本相對越低。

2 優(yōu)化方法

可變規(guī)格板材下料一般流程如圖1所示，下料優(yōu)化需要確定使用何種板材、每種板材的使用數(shù)量、每張板材上排放哪些零件、板材的使用順序以及零件的排放方式。零件序列按板材序列依次排樣，排樣結(jié)果為一張板材對應(yīng)一組零件以及一種布局方式。排樣之后，每張板材排放哪些零件、零件的排放方式已知。板材使用種類和每種板材的使用數(shù)量受板材序列的影響，板材序列確定后二者相應(yīng)確定。在既有排放算法基礎(chǔ)上，為進(jìn)一步優(yōu)化排樣效果，文章的關(guān)鍵任務(wù)是可變規(guī)格板材下料的板材序列優(yōu)化、板材間排樣效果協(xié)調(diào)優(yōu)化以及在此基礎(chǔ)上的總體優(yōu)化處理。

圖1 下料流程圖

2.1 板材序列優(yōu)化

板材選用是要從不同形狀、不同大小的矩形板材或者不規(guī)則板材以及存在內(nèi)部缺陷的非完整板材中選擇合適的板材組合，并按最優(yōu)順序使用。板材按序列依次使用，最佳的板材使用方案是一種板材序列的最佳組合方案。

下料優(yōu)化是板材和零件的序列優(yōu)化與布局優(yōu)化。遺傳算法具有較強(qiáng)的全局搜索能力、魯棒性強(qiáng)，對于組合優(yōu)化中的NP完全問題的求解非常有效。本文利用遺傳算法產(chǎn)生最佳板材序列，同時產(chǎn)生最佳零件序列。板材的利用率、使用數(shù)量等因素通過成本在目標(biāo)函數(shù)中反映。

2.2 板材間排樣效果協(xié)調(diào)優(yōu)化

零件序列按板材序列依次排樣，并通過向后搜索合適零件對可能存在的孔洞空域加以填充。排樣受零件面積的影響，排樣后期隨小型零件的減少，孔洞空域逐步增加。一張板材完全排滿后再排放下一張會使后續(xù)板材利用率逐漸降低。如果在當(dāng)前限制某些后續(xù)搜索零件的插入，后續(xù)的排樣效果可以趨于更優(yōu)。

排樣一般從板材左下角開始，排放過程會在板材右端和上端留下一些空域。如果在該零件組中增加或刪除一個零件重新排樣，排樣結(jié)果會發(fā)生較大變化。當(dāng)增加一個或多個零件時，由于使用的零件不一樣，排樣布局效果發(fā)生改變，原空域部分可以得到填充，排樣結(jié)果可以趨于更優(yōu)。

排樣結(jié)果為一張板材對應(yīng)一組零件以及一種布局方式。優(yōu)化以初始排樣結(jié)果為基礎(chǔ)展開，向著下料更優(yōu)的方向進(jìn)行，即增大余料提高利用率降低成本。協(xié)調(diào)優(yōu)化是一個不斷調(diào)整排樣效果的過程。為增強(qiáng)優(yōu)化調(diào)整得到解的可行性，調(diào)整方向以參與排樣的有效板材序列中某一張開始向后推動。

板材序列中參與排樣的板材為序列前Li張。取[1, Li-1]內(nèi)隨機(jī)整數(shù)RB作為當(dāng)前板材調(diào)整號，以RB號板材為基礎(chǔ)向后調(diào)整，RB號以前排樣情況不變。為避免產(chǎn)生多張余料，調(diào)整前RB及其后續(xù)所有板材連同對應(yīng)零件重新排樣。調(diào)整時，RB號板材上無法再追加新零件，調(diào)整過程為減少其已有零件數(shù)量。同時為不破壞排樣過程帶來的擇優(yōu)插入和避免調(diào)整結(jié)果惡化，每次調(diào)整量不宜過大，調(diào)整量取[0, a]內(nèi)隨機(jī)整數(shù)RP。本文取a＝3，RP取RB板材對應(yīng)零件組的后RP個。RB號板材及其調(diào)整后剩余零件重新排樣，RP個零件加入后續(xù)零件序列并在后續(xù)板材上重新排樣。

如果調(diào)整效果不優(yōu)，以當(dāng)前調(diào)整結(jié)果為基礎(chǔ)進(jìn)一步調(diào)整存在更優(yōu)的可能性，可以按概率接收作為新的基礎(chǔ)解。但當(dāng)調(diào)整數(shù)量過多時以該結(jié)果為基礎(chǔ)無論怎樣調(diào)整，效率都低，此時接收概率降低。模擬退火隨著溫度降低，接收概率逐漸減小，最后系統(tǒng)收斂于某一能量最小的狀態(tài)，該狀態(tài)即可作為目標(biāo)函數(shù)的全局優(yōu)化值。解碼過程按模擬退火技術(shù)進(jìn)行排樣再優(yōu)化，步驟如下：

第一步：設(shè)置初始溫度；

第二步：設(shè)置循環(huán)計數(shù)器起點；

第三步：獲得[1, Li-1]內(nèi)隨機(jī)整數(shù)RB，作為零件調(diào)整基礎(chǔ)板材序號，并就RB及后續(xù)板材連同對應(yīng)零件重新排樣；

第四步：獲得[0, a]內(nèi)隨機(jī)數(shù)RP，作為基礎(chǔ)板材上零件調(diào)整個數(shù)，按調(diào)整策略進(jìn)行排樣優(yōu)化調(diào)整；

第五步：如果當(dāng)前結(jié)果更優(yōu)，接收該結(jié)果，否則按概率接收；

第六步：如果步數(shù)小于終止步數(shù)，增大步數(shù)，轉(zhuǎn)向第三步；

第七步：如果未達(dá)到冷卻狀態(tài)，繼續(xù)降溫，轉(zhuǎn)向第二步；否則，輸出結(jié)果。

板材間排樣效果協(xié)調(diào)優(yōu)化不追求每張板材布局最大化，通過排樣零件在不同板材間的優(yōu)化協(xié)調(diào)提高總體利用率，尋求總體的布局更優(yōu)。

2.3 基于遺傳算法的下料優(yōu)化處理

根據(jù)圖1及問題分析，下料問題需優(yōu)化板材序列、零件序列以及板材間排樣效果。本文優(yōu)化方法以遺傳算法為基礎(chǔ)，在遺傳算法處理過程，將板材序列優(yōu)化和零件序列優(yōu)化結(jié)合起來。遺傳算法采用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，解碼過程對初始排樣結(jié)果按2.2中的方法對初始排樣結(jié)果協(xié)調(diào)優(yōu)化。算法流程如圖2所示。

圖2 算法流程圖

2.3.1 種群初始化

遺傳算法染色體包括兩段，一段為零件序列，一段為板材序列。為便于序列化操作，所有零件和板材均從1開始標(biāo)號。

零件序列部分采用隨機(jī)初始方式，部分采用有序初始方式[8]。有序初始方式首先將零件按面積非增序排列，面積相等時按長度非增序排列，對序列中每個標(biāo)號隨機(jī)賦予“+”“-”表示旋轉(zhuǎn)方向，生成帶符號的有序種群。

板材序列主要由板材隨機(jī)排序生成。其中，板材序列中的m個序列，每個序列前NBi項為一種板材Bi，其余項按剩下板材單位質(zhì)量成本非降序排列。另外1個序列直接按板材單位質(zhì)量成本非降序排序。

2.3.2 遺傳算子

1）選擇算子

遺傳算法采用輪盤賭選擇，根據(jù)每條染色體的適應(yīng)度的比例來確定該個體的選擇概率。

2）交叉算子

零件序列和板材序列交叉操作均采用LOX交叉。LOX是一種改進(jìn)的次序雜交，能盡可能多的保留基因間的相對位置。操作時，先從兩父代P1、P2中選擇交叉點，交換選中的基因子串；然后將原P1(P2)中與P2(P1)子串不同的基因依次填入P1(P2)中非子串基因位置構(gòu)成后代。如圖3，在選擇交叉位置3、7后按操作步驟進(jìn)行得到子代C1、C2。

圖3 LOX交叉

3）變異算子

零件序列變異過程包括序列順序變異和旋轉(zhuǎn)方向變異，前者采用逆序變異，后者采用均勻變異。板材序列變異操作采用逆序變異。逆序變異根據(jù)選中的兩個變異點，將變異區(qū)間內(nèi)基因順序顛倒產(chǎn)生新個體。

排樣時不是每張板材都參與排樣，而是依板材序列排樣直至零件全部排完。板材序列中只有序列前面一部分起實際作用。為提高板材序列交叉變異效果，交叉變異針對參與排樣板材序列部分展開。設(shè)板材序列中參與排樣的板材為序列前Li張。交叉操作時Li取兩序列較小者，并以此值作為變異位置基礎(chǔ)。交叉、變異過程兩位置之一的取值范圍限定在[1, Li]。

2.3.3 終止條件

按算法流程循環(huán)，直到下料方案滿足優(yōu)化目標(biāo)或達(dá)到預(yù)定的進(jìn)化代數(shù)，停止計算，輸出結(jié)果。

3 算例驗證

算例以矩形排樣為例，排放算法采用文獻(xiàn)[8]中基于最低水平線的擇優(yōu)插入算法。該方法在排樣過程按最低水平線法形成空洞時向后搜索合適零件插入當(dāng)前序列位置并填入空洞。根據(jù)文章分析和算法框架，選用幾種大小和成本各異的板材以及相關(guān)零件進(jìn)行實驗。板材材質(zhì)為Q235，板厚20，不同規(guī)格之間單位質(zhì)量成本不同。板材的大小、數(shù)量、成本等信息見表1。算例中設(shè)中間成本10，余料長度大于300時余料有效。

表1 板材信息

每種板材單獨排樣時所耗板材數(shù)量、利用率及成本如表2所示。

表2 同規(guī)格板材下料

表2中余料1是直接排樣后剩下的余料長度，余料2是進(jìn)行排樣效果協(xié)調(diào)優(yōu)化后剩下的余料長度。零件序列按板材序列依次排樣，余料出現(xiàn)在最后一張板材。其中B1、B4板材余料在排樣協(xié)調(diào)優(yōu)化前后均小于300，視作廢料處理。成本按協(xié)調(diào)優(yōu)化后使用情況計算。從表2可以看出，板材間排樣效果協(xié)調(diào)優(yōu)化效果有效。

采用可變規(guī)格板材下料優(yōu)化方法的結(jié)果如表3所示。

表3 可變規(guī)格板材下料

優(yōu)化結(jié)果為板材B1使用3張、B2使用2張，順序為B2B1B1B2B1。其中B2無余料，最后一張B1板材余料長度941?？傮w優(yōu)化成本為1998.9，較表2中同種規(guī)格板材下料成本更優(yōu)。

單張板材利用率不高時，板材間排樣協(xié)調(diào)優(yōu)化效果較為明顯。算例中所用矩形零件大小相差各異且較為明顯，同時數(shù)量不一。在算例中排樣效果再優(yōu)化體現(xiàn)出其有效性。由表可以看出，本文方法能夠有效處理可變規(guī)格板材選用，并有效進(jìn)行零件排樣效果再優(yōu)化。

4 結(jié)論

本文針對可變規(guī)格板材下料優(yōu)化問題，在板材的選擇使用過程中考慮板材利用率和使用數(shù)量兩因素，利用遺傳算法實現(xiàn)板材選用優(yōu)化；在遺傳算法處理過程，將板材序列優(yōu)化和零件序列優(yōu)化結(jié)合起來，并在解碼過程以模擬退火方式對排樣板材間零件加以優(yōu)化調(diào)整提高板材總體利用率。實驗表明，本文所論述的方法具有較強(qiáng)可行性，能夠有效降低下料成本?；诒疚姆椒ㄩ_發(fā)的優(yōu)化模塊已嵌入到排樣軟件系統(tǒng)中，取得了良好的應(yīng)用效果。利用本文提出的思路和方法，還可根據(jù)實際需求進(jìn)一步研究在成本中考慮加工成本、庫存成本、延期交貨成本等因素的情況。

[1]陳學(xué)松,曹炬,方仍存.一種求解矩形件排樣問題的啟發(fā)式算法[J].鍛壓技術(shù),2004,(05).

[2]陳仕軍,曹炬.矩形件優(yōu)化排樣的一種啟發(fā)式算法[J].計算機(jī)工程與應(yīng)用,2010,(12).

[3]張立馳,李健.基于遺傳算法的二維排樣問題求解新策略[J].南通職業(yè)大學(xué)學(xué)報,2009,(03).

[4]張麗平,李松.二維優(yōu)化排樣方法及實現(xiàn)技術(shù)[J].計算機(jī)應(yīng)用與軟件,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].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2008,(04).