陳燁燁,李捍東

(貴州大學(xué)電氣工程學(xué)院,貴州 貴陽(yáng) 550025)

0 引言

在現(xiàn)代制造和加工行業(yè)中,矩形件排樣作為工廠(chǎng)下料第1步,其原材料利用率最大化是提高工廠(chǎng)經(jīng)濟(jì)效益的重要環(huán)節(jié)[1]。從數(shù)學(xué)復(fù)雜度的角度來(lái)看,大多數(shù)類(lèi)型的矩形塊布局問(wèn)題都屬于多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題(non-deterministic polynomial,NP),該類(lèi)問(wèn)題計(jì)算復(fù)雜,難以得到最優(yōu)解[2],且在實(shí)際生產(chǎn)中,需要滿(mǎn)足特定工藝。因此,構(gòu)建一個(gè)算法模型,使得該模型能夠縮短計(jì)算時(shí)間、提高板材利用率并同時(shí)滿(mǎn)足特定生產(chǎn)工藝是此類(lèi)問(wèn)題的研究重點(diǎn)。

對(duì)于矩形件排樣問(wèn)題,國(guó)內(nèi)外學(xué)者已開(kāi)展了相關(guān)研究,并取得了一定的研究成果[3-5]。目前,三階段排樣方式主要有3種不同類(lèi)型:三階段非精確排樣(three-stage non-exact cutting pattern,3NE)、三階段勻質(zhì)排樣 (three-stage uniform cutting pattern,3E)、三階段同質(zhì)排樣 (three-stage homogeneous cutting pattern,3H)[6]。其中,3E 和 3H 排樣方式采用齊頭切方式,在3個(gè)階段內(nèi)切割出準(zhǔn)確尺寸的方形件,屬于精確排樣方式。目前,矩形排樣優(yōu)化算法主要為啟發(fā)式算法和群體智能優(yōu)化算法。啟發(fā)式算法主要用于處理矩形件定位問(wèn)題,BL算法[7]采用最下最左的“占角”思想將矩形件垂直向下、向左平移確定矩形件的最終排列位置。賈志欣等[8]提出最低水平線(xiàn)法對(duì)矩形件位置進(jìn)行確定,根據(jù)矩形件的高度不斷更新最低水平線(xiàn)直至不能放入;張德富等[9]提出砌墻式啟發(fā)算法,將板材進(jìn)行區(qū)域劃分,設(shè)置相應(yīng)的放入條件,以此提高板材利用率。群體智能優(yōu)化算法主要用于定序,確定矩形件排布順序,包括模擬退火算法、蟻群算法、粒子群算法和遺傳算法等[10]。文獻(xiàn)[11]對(duì)傳統(tǒng)的遺傳算法進(jìn)行改進(jìn),使用并行交叉遺傳算法來(lái)解決二維不規(guī)則的排樣問(wèn)題,但該算法具有極強(qiáng)的隨機(jī)性,在數(shù)據(jù)集中表現(xiàn)不一;文獻(xiàn)[12]提出一種遺傳-貪心混合搜索算法,首先使用遺傳算法對(duì)矩形件進(jìn)行優(yōu)化排列,再使用貪心算法對(duì)擇優(yōu)后的工件序列進(jìn)行二次優(yōu)化,使工件排布更合理,利用率更高,但遺傳算法進(jìn)行序列擇優(yōu)時(shí),需緩慢迭代才能得到最優(yōu)解;文獻(xiàn)[13]使用傳統(tǒng)的貪心算法對(duì)矩形件進(jìn)行無(wú)約束排樣,以面積最大的矩形件為局部搜索目標(biāo),以此來(lái)提高板材利用率,該算法流程簡(jiǎn)單,排樣速度快,但原片的利用率比較低;文獻(xiàn)[14]在傳統(tǒng)的貪心算法上加入局部枚舉求解方法,解決齊頭切排樣問(wèn)題的同時(shí)提高了原片利用率,但運(yùn)算時(shí)間會(huì)隨著枚舉空間的增加成指數(shù)增長(zhǎng),不適合應(yīng)用在矩形件數(shù)量多的排樣場(chǎng)合。

針對(duì)上述算法存在的問(wèn)題,本文提出了貪心混合定位算法模型,以板材利用率為優(yōu)化目標(biāo),采用分區(qū)占角的啟發(fā)式算法[15]確定矩形件的排布位置,再采用貪心算法對(duì)矩形件排布序列進(jìn)行優(yōu)化,以達(dá)到板材利用率最大。

1 混合整數(shù)規(guī)劃模型

1.1 目標(biāo)函數(shù)

矩形件排樣優(yōu)化屬于典型的多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題(NP)[2],對(duì)于此類(lèi)計(jì)算復(fù)雜度高的問(wèn)題,本文構(gòu)建了混合整數(shù)模型加以解決。排樣優(yōu)化的目的是優(yōu)化原片排布,提高板材的利用率?；诰匦渭艠恿鞒?研究發(fā)現(xiàn),影響板材利用率的參數(shù)主要有5個(gè),分別為產(chǎn)品總數(shù)、產(chǎn)品的長(zhǎng)和寬、使用板材的總數(shù)和每塊板材的面積,因此,本文以板材利用率為目標(biāo),提出的目標(biāo)函數(shù)為

(1)

式中:N為產(chǎn)品總數(shù);lk、wk分別為第k個(gè)產(chǎn)品的長(zhǎng)和寬;n為使用板材總數(shù);Slw為每塊板材的面積。

1.2 約束條件

為滿(mǎn)足工廠(chǎng)特定生產(chǎn)工藝需求,設(shè)置如下約束條件。

a.齊頭切約束。

本文使用齊頭切工藝對(duì)矩形件進(jìn)行切割。假設(shè)有一組矩形件{k1,k2,…,kn},集合為K,排布在長(zhǎng)為2 440 mm,寬為1 220 mm的原片上。以板材左下角為原點(diǎn)建立坐標(biāo)系,如圖1所示,坐標(biāo)系x、y表示板材的長(zhǎng)和寬。板材上的排布為齊頭切排布,即任何1次直線(xiàn)切割都要保證板材可分離,換言之,每次直線(xiàn)切割都應(yīng)使得板材分成2塊。

圖1 坐標(biāo)系建立方法及齊頭切示意

本文采用三階段齊頭切精確排樣方式,具體為生產(chǎn)1個(gè)產(chǎn)品最多只能切3刀。因此在分區(qū)類(lèi)型為T(mén)ype3時(shí),產(chǎn)品的長(zhǎng)或者寬應(yīng)該等于分區(qū)的寬。

W3=ljorwj

(2)

式中:W3為當(dāng)分區(qū)類(lèi)型為T(mén)ype3時(shí)分區(qū)的寬;lj、wj分別為第j個(gè)產(chǎn)品的長(zhǎng)和寬。

b.切片之間不能相互重疊。

(3)

(4)

式中:xj+1、yj+1為第j+1個(gè)產(chǎn)品的左下角頂點(diǎn)坐標(biāo);xj、yj為第j個(gè)產(chǎn)品的左下角頂點(diǎn)坐標(biāo);lj、wj分別為第j個(gè)產(chǎn)品的長(zhǎng)和寬。

當(dāng)分區(qū)類(lèi)型為T(mén)ype3時(shí),應(yīng)該滿(mǎn)足約束如式(3)所示,當(dāng)分區(qū)類(lèi)型為T(mén)ype1或者Type2時(shí),應(yīng)該滿(mǎn)足約束如式(4)所示。

2 算法分析

2.1 BL算法

BL算法是一種二維矩形件排樣問(wèn)題的算法[7],該算法的思想主要是“占角”,待放置的矩形件從右上角進(jìn)入,最終到達(dá)左下角;其移動(dòng)方向固定,只能垂直向下、向左平移,且矩形件放入的最終位置不能繼續(xù)向下、向左進(jìn)行移動(dòng);當(dāng)矩形件放置完畢或者原片材料沒(méi)有多余位置放置矩形件為止。具體過(guò)程如圖2所示。

圖2 BL算法過(guò)程

由圖2可見(jiàn),BL算法步驟如下:

a.矩形件從右上角進(jìn)入,向下平移。

b.接觸到原片邊界或者已放入的矩形件,不再繼續(xù)向下移動(dòng),轉(zhuǎn)而向左移動(dòng)。

c.當(dāng)?shù)竭_(dá)左邊界或者接觸到左邊已放入的矩形件,左移停止,轉(zhuǎn)向下移。

d.當(dāng)把原片上左下角“填滿(mǎn)”,即不能向下、向左移動(dòng)時(shí),矩形件放置完成,并轉(zhuǎn)向新的矩形件放置。

BL算法雖然可以解決二維矩形排樣問(wèn)題,但在進(jìn)行排樣時(shí),會(huì)存在待放入的矩形件與已放入的矩形件存在高度差,導(dǎo)致排樣時(shí)板材出現(xiàn)大部分空余,造成板材的浪費(fèi),降低了材料的利用率。

2.2 分區(qū)界定

基于上述研究,為了更好區(qū)分板材切割過(guò)程中出現(xiàn)的不同情況,本文引入分區(qū)[15]。分區(qū)是由切割線(xiàn)與板材構(gòu)成的為未被放置的區(qū)域。以原片左下角底點(diǎn)為坐標(biāo)原點(diǎn),原片的長(zhǎng)為x軸,原片的寬為y軸。將板材切割過(guò)程中的3種情況用3個(gè)分區(qū)類(lèi)型(Type1、Type2、Type3)來(lái)表示,如圖3所示。

圖3 分區(qū)類(lèi)型

由圖3可知,圖3a為T(mén)ype1分區(qū),即未放置矩形件的原片,將第1塊矩形件從左下角位置放入,然后根據(jù)齊頭切原則,在矩形件最右側(cè)進(jìn)行完全切割。切割之后的區(qū)域?yàn)門(mén)ype2分區(qū),如圖3b所示,在該分區(qū)繼續(xù)放置矩形件;放置矩形件還留有區(qū)域,則設(shè)置成Type3分區(qū),如圖3c所示,在該分區(qū)放置的矩形件的長(zhǎng)或者寬必須與該分區(qū)的寬相等。如果Type3分區(qū)已經(jīng)沒(méi)有剩余空間可放入矩形件,則舍棄該分區(qū),在該分區(qū)上方開(kāi)辟新的Type2分區(qū),如果Type2分區(qū)不能放入任何矩形件,則在當(dāng)前原片剩下的部分開(kāi)辟新的Type1分區(qū),如果Type1分區(qū)也不能放入任何矩形件,則說(shuō)明當(dāng)前原片已經(jīng)用完了,所以選擇新的原片開(kāi)辟新的Type1分區(qū)。以上是分區(qū)放置原則。

產(chǎn)品不能超過(guò)分區(qū)的邊界,具體約束如式(5)和式(6)所示。

lj≤LiorWi

(5)

wj≤LiorWi

(6)

式中:lj、wj分別為第j個(gè)產(chǎn)品的長(zhǎng)和寬;Li為分區(qū)i的長(zhǎng);Wi為分區(qū)i的寬,i=1,2,3。

為了能在分區(qū)中將產(chǎn)品j切出,產(chǎn)品j的長(zhǎng)不能同時(shí)大于分區(qū)的長(zhǎng)和寬,產(chǎn)品j的寬也不能同時(shí)大于分區(qū)的長(zhǎng)和寬。

分區(qū)不能超過(guò)原片的邊界,原片的規(guī)格為2 400 mm×1 200 mm,如式(7)所示。

(7)

式中:xi為分區(qū)i左下角的橫坐標(biāo);yi為分區(qū)i左下角的縱坐標(biāo),i=1,2,3。

2.3 貼邊度

本文在BL算法的基礎(chǔ)上加入貼邊度,即矩形件與在板材右邊界的距離。當(dāng)分區(qū)類(lèi)型為T(mén)ype2或Type3時(shí),取放入矩形件與有邊界的最小值為第一貼邊度,該值是一個(gè)正值。隨著放入的矩形件,第一貼邊度值不斷進(jìn)行更新,所添加的矩形件不能超出分區(qū)邊界。貼邊度值越小,說(shuō)明該矩形件放置越貼合,對(duì)整體布局影響越小,板材面積空余,原片利用率就可以得到較大提升。

由圖4可知,圖4a顯示的Type2分區(qū)放入矩形件,b代表貼邊度,L2表示Type2分區(qū)的長(zhǎng)度,圖4b顯示的Type3分區(qū)放入矩形件,L3表示Type3分區(qū)的長(zhǎng)度,分區(qū)2貼邊度計(jì)算如式(8)所示,分區(qū)3貼邊度計(jì)算如式(9)所示。

圖4 貼邊度放置

bk=(L2-lk)min

(8)

bk=(L3-lk)min

(9)

式中:bk為第k塊矩形件的第一貼邊度。

2.4 貪心混合定位算法

使用貪心算法對(duì)排布順序進(jìn)行優(yōu)化,之后使用混合定位算法對(duì)矩形件進(jìn)行排布,找出一個(gè)最佳的排布順序。對(duì)于一個(gè)給定的產(chǎn)品序列號(hào),該算法按序列中的排列方式依次將產(chǎn)品放入箱中,每次都將產(chǎn)品放到一個(gè)目前來(lái)看最優(yōu)的位置,如果當(dāng)前產(chǎn)品在任一分區(qū)無(wú)法排布,則將產(chǎn)品放入候選序列,考慮剩余可以進(jìn)行的產(chǎn)品,以此來(lái)提高板材的利用率。算法框架如圖5所示。

圖5 算法框架

由圖5可知,算法步驟如下:

a.對(duì)產(chǎn)品進(jìn)行排序,并初始化分區(qū)類(lèi),將分區(qū)類(lèi)型初始化為T(mén)ype1分區(qū)。

b.使用貪心算法對(duì)輸入列表產(chǎn)品進(jìn)行序列優(yōu)化并輸入優(yōu)化后的序列。

c.判斷產(chǎn)品能否放入當(dāng)前分區(qū),若能放入,將產(chǎn)品放入該分區(qū),并轉(zhuǎn)向步驟d;若不能放入,則轉(zhuǎn)向步驟e。

d.更新分區(qū)類(lèi)型,將現(xiàn)有分區(qū)更新為放置矩形件之后出現(xiàn)的分區(qū),并轉(zhuǎn)向步驟f。

e.判斷剩余產(chǎn)品能否放入該分區(qū),若能放入,轉(zhuǎn)向步驟d;若不能放入,開(kāi)辟新分區(qū),并轉(zhuǎn)向步驟c。

f.判斷產(chǎn)品列表是否為空,若不為空,程序轉(zhuǎn)向步驟b;若為空,程序繼續(xù)執(zhí)行。

g.程序結(jié)束。

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)數(shù)據(jù)

為了更好驗(yàn)證本文所提貪心混合定位算法的有效性,本次實(shí)驗(yàn)環(huán)境為Python3.7,實(shí)驗(yàn)數(shù)據(jù)采用華為杯數(shù)學(xué)建模中的4組板材數(shù)據(jù),每組數(shù)據(jù)集有700多塊工件。原片規(guī)格為2 440 mm×1 220 mm,部分實(shí)驗(yàn)數(shù)據(jù)如表1所示。

表1 矩形件排樣數(shù)據(jù)集(部分)

實(shí)驗(yàn)數(shù)據(jù)包含產(chǎn)品序列號(hào)、產(chǎn)品材質(zhì)、產(chǎn)品數(shù)量、產(chǎn)品長(zhǎng)寬以及訂單號(hào),每種材質(zhì)的矩形件需在同一塊原片上進(jìn)行切割,4組數(shù)據(jù)中,每組數(shù)據(jù)的矩形件材質(zhì)均相同,故不考慮材質(zhì)不同問(wèn)題。

3.2 實(shí)驗(yàn)結(jié)果

對(duì)4組數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理,將矩形件按照長(zhǎng)度從大到小排列。結(jié)合貪心混合定位算法,運(yùn)用Python3.7進(jìn)行實(shí)驗(yàn)。使用4個(gè)數(shù)據(jù)集分別進(jìn)行10次實(shí)驗(yàn)。表2中記錄的是矩形件排布信息,包括所用的第幾塊原片,原片上排布的矩形件編號(hào),矩形件左下底角位于原片上的x、y坐標(biāo)以及在x、y方向的長(zhǎng)度。圖6根據(jù)表2所提供的數(shù)據(jù)進(jìn)行繪制,顯示的是矩形件在原片上的排布結(jié)果。

表2 矩形件排樣數(shù)據(jù)集(部分)

圖6 矩形件排布

由表2和圖6可知,原片上排布的是序列號(hào)為256、222、311、156、710、296、774、703、647、583、227、143、680、432、417、560、171的矩形件。排布在第86塊原片上,實(shí)驗(yàn)結(jié)果如表3所示。

表 3 實(shí)驗(yàn)結(jié)果

由表3可知, dataA1原片利用率為94.15%,所用時(shí)長(zhǎng)為23.56 s;dataA2原片利用率為93.32%,所用時(shí)長(zhǎng)為20.16 s;dataA3原片利用率為95.05%,所用時(shí)長(zhǎng)為23.56 s;dataA4原片利用率為94.67%,所用時(shí)長(zhǎng)為30.21 s。

3.3 對(duì)比分析

使用數(shù)據(jù)集所包含的4組數(shù)據(jù),對(duì)貪心及局部枚舉算法[14]、并行交叉遺傳算法[11]以及遺傳貪心混合搜索算法[12]進(jìn)行對(duì)比測(cè)試。在4組數(shù)據(jù)中4種模型得到的原片利用率對(duì)比結(jié)果如表4所示,實(shí)驗(yàn)運(yùn)行的時(shí)長(zhǎng)如圖7所示。

表4 不同模型利用率對(duì)比 %

圖7 不同模型在測(cè)試數(shù)據(jù)中的運(yùn)行時(shí)長(zhǎng)

由表4可知,在數(shù)據(jù)集dataA1中,本文算法原片利用率較其他算法分別提高4.14百分點(diǎn)、2.79百分點(diǎn)、0.90百分點(diǎn);在數(shù)據(jù)集dataA2中,分別提高5.37百分點(diǎn)、0.20百分點(diǎn)、0.72百分點(diǎn);在數(shù)據(jù)集dataA3中,分別提高2.84百分點(diǎn)、7.91百分點(diǎn)、0.35百分點(diǎn);在數(shù)據(jù)集dataA4中,分別提高9.55百分點(diǎn)、4.46百分點(diǎn),較遺傳貪心混合搜索算法利用率低0.93百分點(diǎn)。從整體來(lái)看,貪心混合定位算法優(yōu)于其他3種算法,且在4個(gè)數(shù)據(jù)集中算法優(yōu)化結(jié)果較為穩(wěn)定。

由圖7可知,貪心混合定位算法在運(yùn)行時(shí)長(zhǎng)上明顯優(yōu)于其他3種算法。最長(zhǎng)時(shí)長(zhǎng)僅為30 s,貪心及局部枚舉算法最低時(shí)長(zhǎng)為1 800 s;并行交叉遺傳算法最低時(shí)長(zhǎng)為7 800 s,遺傳貪心混合搜索算法最低時(shí)長(zhǎng)為9 600 s。因此在處理多數(shù)量矩形件排布時(shí),本文模型具有顯著優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

本文針對(duì)三階段矩形件排樣優(yōu)化問(wèn)題,以板材利用率為目標(biāo),提出貪心混合定位算法。

a.使用貪心算法對(duì)輸入序列進(jìn)行優(yōu)化,使得矩形件能更快速地進(jìn)行排布。

b.使用混合定位算法對(duì)矩形件的位置加以確定,使得矩形件在板材上排布最優(yōu),提高板材利用率。

本文方法經(jīng)實(shí)驗(yàn)驗(yàn)證,能在一定程度上提高板材利用率并能在較大的數(shù)據(jù)集中進(jìn)行快速排布。在4個(gè)數(shù)據(jù)集中,本文方法利用率波動(dòng)較小,算法較為穩(wěn)定。