魯淑飛，陳 燕，崔耀東

廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 530004

1 引言

二維矩形件下料廣泛存在于服裝、皮革、木材、金屬制品、機(jī)械設(shè)備等生產(chǎn)制造行業(yè)，作為控制企業(yè)生產(chǎn)成本的重點(diǎn)環(huán)節(jié)，采用合理的優(yōu)化下料技術(shù)具有重要的意義[1]。如在鋼材、機(jī)械、汽車、造船等重工業(yè)領(lǐng)域，由于鋼板一般通過激光、火焰、等離子切割以及沖裁等方式切割成生產(chǎn)零件，切割成本較高，因此采用在提高材料利用率的同時，降低切割成本，縮短生產(chǎn)周期的優(yōu)化下料技術(shù)，對于企業(yè)長遠(yuǎn)發(fā)展具有重要意義。

目前針對矩形件優(yōu)化下料問題，國內(nèi)外專家學(xué)者大多從改進(jìn)算法提高材料利用率角度進(jìn)行研究，文獻(xiàn)[2]應(yīng)用四塊排樣算法生成單個排樣方式，與基于價值修正的順序啟發(fā)式算法相結(jié)合，選擇使用板材張數(shù)最少的下料方案作為最終解；文獻(xiàn)[3]應(yīng)用生成同質(zhì)條帶四塊排樣方式的背包算法，與線性規(guī)劃算法相結(jié)合，以板材張數(shù)最少為目標(biāo)選擇下料方案；文獻(xiàn)[4]將列生成法與有約束排樣方式算法相結(jié)合，求解同質(zhì)條帶四塊排樣的矩形件下料問題以提高材料利用率；文獻(xiàn)[5]提出一種可以確定板材采購尺寸的二維優(yōu)化下料算法，即在已知矩形件需求的情況下，在供應(yīng)商規(guī)定的板材尺寸范圍內(nèi)確定最佳采購尺寸，使板材利用率達(dá)到最優(yōu)，降低材料成本。然而矩形件優(yōu)化下料問題是具有最高計(jì)算復(fù)雜性的NP完全問題，實(shí)際下料問題涉及環(huán)節(jié)多，生成下料方案時，不僅要考慮材料利用率，同時還要考慮下料工藝、切割成本、生產(chǎn)效率等一系列問題，使下料方案在具有高材料利用率的同時具有良好的可加工性[6]、低的切割成本和高的生產(chǎn)效率。針對實(shí)際下料過程中的一些具體問題，文獻(xiàn)[7]提出一種支持一刀切工藝約束的放寬式搜索算法，在得到高材料利用率下料方案的同時滿足特定下料工藝；文獻(xiàn)[8]將基于分組降維規(guī)則與遺傳算法相結(jié)合，求解人造板矩形件優(yōu)化下料問題，解決一張板材上布局矩形件種類過多導(dǎo)致開料鋸在切割過程中鋸路繁瑣開料速度慢的問題；文獻(xiàn)[9]考慮下料方案的可加工性，將根據(jù)板材單方向余料長最小化優(yōu)選條帶方法與基于條帶的連續(xù)啟發(fā)式算法相結(jié)合求解矩形件優(yōu)化下料問題，利用同質(zhì)條帶的共邊排樣設(shè)計(jì)自動切割工藝的下料切割路徑，以縮短總的切割路徑，提高生產(chǎn)效率，降低下料切割成本。但是其利用板材單方向余料長最小化優(yōu)選布局條帶的方法不能保證排樣方式全局最優(yōu)，另外基于布局條帶的連續(xù)啟發(fā)式算法具有貪婪性，即生成下料方案中靠前排樣方式時，剩余矩形件多，容易得到高材料利用率的排樣方式；在生成靠后排樣方式時，剩余矩形件較少，得到排樣方式的材料利用率較低。

基于以上研究基礎(chǔ)，針對鋼板矩形件自動化切割下料問題，本文綜合考慮材料成本、下料工藝、切割成本以及生產(chǎn)效率，將同質(zhì)條帶多級規(guī)范布局方式[10-11]生成算法與基于價值修正的順序啟發(fā)式算法[12-13（]Sequential Value Correction，SVC）相結(jié)合，以材料成本和切割成本為優(yōu)化目標(biāo)，提出一種面向可加工性的矩形件優(yōu)化下料算法。最后通過多組算例進(jìn)行實(shí)驗(yàn)對比，證明應(yīng)用本文算法能夠有效地提高材料利用率和生產(chǎn)效率，降低切割成本。

2 數(shù)學(xué)模型及相關(guān)概念

2.1 問題描述及數(shù)學(xué)模型

本文討論的是多規(guī)格、大批量的矩形件優(yōu)化下料問題，即在n種長為Lj，寬為Wj，供應(yīng)量為Dj(j=1,2,…,n)的板材上按照生產(chǎn)工藝要求切割出m種長為li，寬為wi，需求量為di(i=1,2,…,m)的矩形件。

假設(shè)下料方案有K種排樣方式，對于第k(k=1,2,…,K)個排樣方式，Sk為消耗的材料成本，λPk為切割成本（其中λ為控制參數(shù)，Pk為切割路徑長度，切割成本與切割路徑長度成正比，λ∈[1,12]，默認(rèn)值為7），aki為含第i種矩形件的數(shù)量，xk為使用次數(shù)，所使用的板材種類為β(k)，其中β(k)∈[1,2,…,n]。要求滿足矩形件需求量，并使其生產(chǎn)成本（材料成本與切割成本之和）達(dá)到最小。則該問題的整數(shù)規(guī)劃模型為：

其中，式（1）為面向可加工性的矩形件優(yōu)化下料問題的目標(biāo)函數(shù)，即最小化的生產(chǎn)成本，其中板材成本為板材面積，切割成本為下料過程中能源、加工工時、人力資源等消耗通過控制參數(shù)以切割路徑總長度為單位統(tǒng)一折算而來；式（2）為約束條件，表示按此下料方案產(chǎn)出的矩形件數(shù)量應(yīng)該等于矩形件的需求；式（3）為約束條件，表示下料方案使用每種板材的總量不能超過其供應(yīng)量；式（4）為變量的取值范圍，Z+0表示非負(fù)整數(shù)集合。

2.2 條帶

條帶根據(jù)是否含有多種不同尺寸的矩形件，可分為普通條帶和同質(zhì)條帶。如圖1所示，由不同寬度的矩形件組成的條帶稱為普通條帶，由相同種類相同方向的矩形件組成的條帶稱為同質(zhì)條帶。綜合考慮下料方案的可加工性，以及自動化切割的可操作性，本文采用同質(zhì)條帶。

圖1 條帶

分別用X和Y標(biāo)記水平方向和豎直方向，則根據(jù)條帶方向與矩形件長邊的方向，可將條帶分為XX、XY、YX和YY四種類型。其中，XX型條帶表示條帶方向水平，矩形件長邊水平；XY 型條帶表示條帶方向水平，矩形件長邊豎直；YX型條帶表示條帶方向豎直，矩形件長邊水平；YY 型條帶表示條帶方向豎直，矩形件長邊豎直。四種條帶在板材上的布局如圖2所示，其中陰影部分為條帶在板材上排樣后所產(chǎn)生的余料。

圖2 四種條帶布局示意圖

表1分別列出了各類型條帶的相關(guān)標(biāo)記參數(shù)，則各類型條帶的相應(yīng)價值如下：

表1 條帶相關(guān)參數(shù)信息表

其中，ci為第i種矩形件的價值，i=1,2,…,m。

2.3 板材切割

板材切割即按排樣方式切割出板材上所布局的矩形件。本文板材切割方法參考文獻(xiàn)[9]，條帶內(nèi)的矩形件分離采用“之”字型切割，條帶間的分離采用直線型切割。條帶內(nèi)的矩形件分離具體切割方法：當(dāng)條帶為XX、XY型條帶時，若條帶內(nèi)含有矩形件的數(shù)量為奇數(shù)，則自條帶左上角水平向右開始進(jìn)行“之”字型切割分離矩形件；若條帶內(nèi)含有矩形件的數(shù)量為偶數(shù)，則自條帶左上角豎直向下進(jìn)行“之”字型切割分離矩形件。當(dāng)條帶為YX、YY 型條帶時，若條帶內(nèi)含有矩形件的數(shù)量為奇數(shù)，則自條帶左上角豎直向下進(jìn)行“之”字型切割分離矩形件；若條帶內(nèi)含有矩形件的數(shù)量為偶數(shù)，則自條帶左上角水平向右進(jìn)行“之”字型切割分離矩形件。條帶間分離具體切割方法：當(dāng)條帶為XX、XY 型條帶時，自左向右直線分離條帶；當(dāng)條帶為YX、YY 型條帶時，自下而上直線分離條帶。

假設(shè)條帶內(nèi)含有第i種矩形件的數(shù)量為a，則條帶切割路徑長度C(a)的計(jì)算方法如下：

當(dāng)a為奇數(shù)時：

當(dāng)a為偶數(shù)時：

一張板材的切割路徑長度為其上所布局條帶切割路徑長度之和；下料方案的切割路徑長度為其所用板材切割路徑長度之和。

3 算法設(shè)計(jì)與實(shí)現(xiàn)

SVC框架在求解下料問題時得到廣泛應(yīng)用[12-13]。本文將基于價值修正的順序啟發(fā)式算法與排樣方式生成算法相結(jié)合，形成下料方案的生成算法。利用基于價值校正的順序啟發(fā)式算法多代、順序、價值校正的特點(diǎn)，經(jīng)多次迭代后，從多個下料方案中優(yōu)選生產(chǎn)成本最小者作為最終下料方案。

3.1 下料方案生成算法

按照式（1）計(jì)算下料方案總成本，Gmax為最高迭代次數(shù)，G為當(dāng)前迭代次數(shù)，ri為第i種矩形件的剩余需求量(i=1,2,…,m) ，bj為第j種板材的剩余庫存量(j=1,2,…,n)，qi為排樣方式所含第i種矩形件的數(shù)量(i=1,2,…,m)，f為排樣方式的使用次數(shù)。下料方案生成算法步驟如下，其中GetPattern()函數(shù)和CorrectValue()函數(shù)將分別在3.2和3.3節(jié)中介紹。

步驟1令G=1，初始化毛坯價值ci=li×wi，i=1,2,…,m；令最佳下料方案的總成本為正無窮大。

步驟2如果G ＞Gmax，轉(zhuǎn)步驟9，否則，令矩形件的剩余需求量等于初始需求量，即ri=di，令板材的剩余庫存量等于初始供應(yīng)量，即bj=Dj，其中i=1,2,…,m，j=1,2,…,n。

步驟3調(diào)用GetPattern()函數(shù)生成當(dāng)前排樣方式。

步驟4根據(jù)當(dāng)前使用第j種板材(j∈[1,2,…,n])的庫存量和需求量確定當(dāng)前排樣方式使用次數(shù)f，，更新矩形件剩余需求量ri=ri-fqi，更新板材庫存量bj=bj-f，并將此排樣方式加入當(dāng)前下料方案中。

步驟5調(diào)用CorrectValue()函數(shù)修正矩形件的價值。

步驟6對于所有的矩形件，只要存在一個ri ＞0(i=1,2,…,m)則轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟7。

步驟7計(jì)算當(dāng)前下料方案的生產(chǎn)成本，若當(dāng)前下料方案的生產(chǎn)成本低于目前最佳下料方案的生產(chǎn)成本，則更新最佳下料方案。

步驟8G=G+1。轉(zhuǎn)步驟2。

步驟9輸出最佳下料方案。

3.2 GetPattern()函數(shù)

構(gòu)建前瞻法，采用同質(zhì)條帶多級規(guī)范布局方式，通過求解如下有界二維背包問題（6）確定當(dāng)前板材的排樣方式：

前瞻法即每偽布局一根條帶，都要考慮剩余子板的所有布局可能性，并計(jì)算出其價值，最后以式（6）確定最終排樣方式，示意圖如圖3所示，具體方法描述如下。

設(shè)lmin，wmin分別為矩形件尺寸中的最小長度和最小寬度，在尺寸為x×y的板材上生成同質(zhì)條帶多級規(guī)范布局方式，板材最大價值為F(x,y)，則遞推公式如下：

圖3 前瞻法示意圖

當(dāng)x ＜lmin或y ＜wmin，同時x ＜wmin或y ＜lmin，F(xiàn)(x,y)=0。

否則，

式（7）的時間復(fù)雜度為O(mLW)，而且其具有全容量特性：一旦計(jì)算出F(x,y) ，那么對于所有的x×y(x∈[1,L]?y∈[1,W])，F(xiàn)(x,y) 的值均已計(jì)算出來。即每一步根據(jù)F(x,y)的取值情況，可以確定板材x×y的排樣方式。

設(shè)函數(shù)getPattern(x,y)返回當(dāng)前排樣板材最大價值，函數(shù)算法步驟如下：

步驟1令F(x,y)=0，i=1。

步驟2令VXX=0，VXY=0，VYX=0，VYY=0。若當(dāng)前待排樣板材x×y不能布局任何一種矩形件條帶，則轉(zhuǎn)步驟 5；否則：如果x≥li，而且y≥wi時，則令VXX=uXX(i,x)+getPattern(x,y-wi)，VYX=uYX(i,y)+getPattern(x-li,y)；若x≥wi且y≥li，令VXY=uXY(i,x)+getPattern(x,y-li)，VYY=uYY(i,y)+getPattern(x-wi,y)。

步驟3令V=max{VXX,VXY,VYX,VYY} 。

步驟4如果F(x,y)＜V，令F(x,y)=V。

步驟5令i=i+1。如果i≤m，則轉(zhuǎn)步驟2。

步驟6返回F(x,y)。

在實(shí)際生成排樣方式的過程中，初始化x=Lj，y=Wj(j=1,2,…,n)，依次調(diào)用函數(shù)getPattern(x,y)，得到每種可用板材最大價值的排樣方式。根據(jù)2.3 節(jié)計(jì)算每種板材的切割路徑長度，按下式計(jì)算板材的產(chǎn)出率：

以最高產(chǎn)出率確定最終使用板材種類及其排樣方式。

3.3 CorrectValue()函數(shù)

下料方案生成算法中，每生成一個排樣方式后，都對矩形件價值進(jìn)行修正[12]，調(diào)整矩形件的優(yōu)先級，解決局部最優(yōu)問題，實(shí)現(xiàn)下料方案多樣化。矩形件價值修正公式[14]如下：

其中，g1+g2=1；g2=εqi(di+ri)；參數(shù)ε∈[0.6,0.9]，默認(rèn)值為0.75；ρ為略大于1的控制參數(shù)，默認(rèn)值為1.02；U為當(dāng)前排樣方式利用率，。

4 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)采用C#編程，實(shí)驗(yàn)用計(jì)算機(jī)配置為Intel Core i5-4590 CPU，3.3 GHz 主頻，4 GB 內(nèi)存。其中參數(shù)Gmax=500。

4.1 單一算例實(shí)驗(yàn)對比

采用文獻(xiàn)[9]中的例題，僅有1組矩形件和1組板材尺寸（分別為500×400、800×600、1 000×800）。本文算法運(yùn)行結(jié)果如圖4所示，共有3個排樣方式，每個排樣方式使用次數(shù)為1、板材尺寸均為800×600，其中圖4（d）中帶箭頭的紅色實(shí)線表示分離矩形件的切割線，帶箭頭的藍(lán)色虛線表示分離條帶的切割線。本文算法與文獻(xiàn)[9]算法材料利用率均為99.58%，切割總路徑分別為36 180和36 660，前者小于后者，與后者相比前者切割總路徑降低1.31%。由此可知，針對本算例，與文獻(xiàn)[9]相比，本文算法在材料利用率相同的情況下，下料方案具有更短的切割路徑和更高的生產(chǎn)效率。

圖4 下料方案及排樣方式切割路徑圖

4.2 多組算例實(shí)驗(yàn)對比

由于單一算例實(shí)驗(yàn)結(jié)果具有偶然性，為了進(jìn)一步驗(yàn)證本文算法的有效性與可行性，從文獻(xiàn)[15]中選取20道基準(zhǔn)實(shí)例與文獻(xiàn)[9]算法進(jìn)行對比，其中每道題都有20組矩形件，5 種可供使用板材（尺寸分別為1 400×700、1 700×850、2 000×1 000、2 800×1 400 和4 000×2 000）。表2列出了本文算法與文獻(xiàn)[9]算法的測試結(jié)果，其中U和CL分別代表本文算法的材料利用率和切割路徑總長度，U1和CL1則分別代表文獻(xiàn)[9]算法的材料利用率和切割路徑總長度，ΔU和ΔCL分別表示材料利用率和切割路徑總長度的差值，其中ΔU=U-U1，ΔCL=CL-CL1。從表中可以看出，兩種算法的平均材料利用率分別為95.66%和88.62%，前者較后者提高7.04%；平均切割路徑分別為83 218.8 和87 741.6，前者較后者減少4 552.8，與后者相比前者切割總路徑降低5.19%。由數(shù)據(jù)對比可知，本文算法能夠有效地降低生產(chǎn)成本，縮短下料時間，提高下料效率。

表2 兩種算法的實(shí)驗(yàn)結(jié)果及對比情況

5 結(jié)束語

本文以材料利用率和切割成本為優(yōu)化目標(biāo)，提出一種面向可加工性的矩形件優(yōu)化下料算法，其中算法以低割成本和高材料利用率為目標(biāo)，建立了以生產(chǎn)成本（材料成本與切割成本之和）最小為目標(biāo)函數(shù)的數(shù)學(xué)模型，模型中將下料過程中能源、加工工時、人力資源等消耗通過控制參數(shù)統(tǒng)一折算為切割成本，以生產(chǎn)成本最小為目標(biāo)函數(shù)，簡化了優(yōu)化下料過程中相關(guān)環(huán)節(jié)的處理方法，對優(yōu)化下料問題的研究具有重要意義。另外，最后通過實(shí)驗(yàn)對比證實(shí)本文提出的優(yōu)化下料算法符合實(shí)際生產(chǎn)的需求，能在維持高材料利用率的同時，使下料方案具有較低的切割成本和良好的可加工性，提高下料效率，對于企業(yè)的長遠(yuǎn)發(fā)展具有重要意義。