基于貪心混合定位算法三階段排樣問題研究

陳燁燁,李捍東

(貴州大學電氣工程學院,貴州 貴陽 550025)

0 引言

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

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

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

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

1.1 目標函數(shù)

矩形件排樣優(yōu)化屬于典型的多項式復雜程度的非確定性問題(NP)[2],對于此類計算復雜度高的問題,本文構建了混合整數(shù)模型加以解決。排樣優(yōu)化的目的是優(yōu)化原片排布,提高板材的利用率。基于矩形件排樣流程,研究發(fā)現(xiàn),影響板材利用率的參數(shù)主要有5個,分別為產品總數(shù)、產品的長和寬、使用板材的總數(shù)和每塊板材的面積,因此,本文以板材利用率為目標,提出的目標函數(shù)為

(1)

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

1.2 約束條件

為滿足工廠特定生產工藝需求,設置如下約束條件。

a.齊頭切約束。

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

圖1 坐標系建立方法及齊頭切示意

本文采用三階段齊頭切精確排樣方式,具體為生產1個產品最多只能切3刀。因此在分區(qū)類型為Type3時,產品的長或者寬應該等于分區(qū)的寬。

W3=ljorwj

(2)

式中:W3為當分區(qū)類型為Type3時分區(qū)的寬;lj、wj分別為第j個產品的長和寬。

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

(3)

(4)

式中:xj+1、yj+1為第j+1個產品的左下角頂點坐標;xj、yj為第j個產品的左下角頂點坐標;lj、wj分別為第j個產品的長和寬。

當分區(qū)類型為Type3時,應該滿足約束如式(3)所示,當分區(qū)類型為Type1或者Type2時,應該滿足約束如式(4)所示。

2 算法分析

2.1 BL算法

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

圖2 BL算法過程

由圖2可見,BL算法步驟如下:

a.矩形件從右上角進入,向下平移。

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

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

d.當把原片上左下角“填滿”,即不能向下、向左移動時,矩形件放置完成,并轉向新的矩形件放置。

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

2.2 分區(qū)界定

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

圖3 分區(qū)類型

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

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

lj≤LiorWi

(5)

wj≤LiorWi

(6)

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

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

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

(7)

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

2.3 貼邊度

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

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

圖4 貼邊度放置

bk=(L2-lk)min

(8)

bk=(L3-lk)min

(9)

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

2.4 貪心混合定位算法

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

圖5 算法框架

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

a.對產品進行排序,并初始化分區(qū)類,將分區(qū)類型初始化為Type1分區(qū)。

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

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

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

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

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

g.程序結束。

3 實驗驗證

3.1 實驗數(shù)據

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

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

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

3.2 實驗結果

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

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

圖6 矩形件排布

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

表 3 實驗結果

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

3.3 對比分析

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

表4 不同模型利用率對比 %

圖7 不同模型在測試數(shù)據中的運行時長

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

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

4 結束語

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

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

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

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