陳 奇，曹德列，饒運(yùn)清

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

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

0 引言

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

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

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

1 問題分析

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

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

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

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

2 優(yōu)化方法

可變規(guī)格板材下料一般流程如圖1所示，下料優(yōu)化需要確定使用何種板材、每種板材的使用數(shù)量、每張板材上排放哪些零件、板材的使用順序以及零件的排放方式。零件序列按板材序列依次排樣，排樣結(jié)果為一張板材對(duì)應(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)，對(duì)于組合優(yōu)化中的NP完全問題的求解非常有效。本文利用遺傳算法產(chǎn)生最佳板材序列，同時(shí)產(chǎn)生最佳零件序列。板材的利用率、使用數(shù)量等因素通過成本在目標(biāo)函數(shù)中反映。

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

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

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

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

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

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

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

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

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

第四步：獲得[0, a]內(nèi)隨機(jī)數(shù)RP，作為基礎(chǔ)板材上零件調(diào)整個(gè)數(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ù)，解碼過程對(duì)初始排樣結(jié)果按2.2中的方法對(duì)初始排樣結(jié)果協(xié)調(diào)優(yōu)化。算法流程如圖2所示。

圖2 算法流程圖

2.3.1 種群初始化

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

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

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

2.3.2 遺傳算子

1）選擇算子

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

2）交叉算子

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

圖3 LOX交叉

3）變異算子

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

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

2.3.3 終止條件

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

3 算例驗(yàn)證

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

表1 板材信息

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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