結(jié)合批量問(wèn)題的多目標(biāo)矩形件優(yōu)化排樣

鄭明月，劉林，2，闞方，方昶

1.合肥工業(yè)大學(xué)管理學(xué)院，合肥 230009

2.過(guò)程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室，合肥 230009

結(jié)合批量問(wèn)題的多目標(biāo)矩形件優(yōu)化排樣

鄭明月1，劉林1，2，闞方1，方昶1

1.合肥工業(yè)大學(xué)管理學(xué)院，合肥 230009

2.過(guò)程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室，合肥 230009

1 引言

批量問(wèn)題[1]（lot-sizing problem）就是解決在規(guī)定時(shí)間內(nèi)每一個(gè)時(shí)期的生產(chǎn)數(shù)量問(wèn)題，目標(biāo)是最優(yōu)化生產(chǎn)中的設(shè)置成本和庫(kù)存成本。下料問(wèn)題[2]（cutting-stock problem）主要分為一維下料與二維下料問(wèn)題，本文所研究的是二維矩形件下料問(wèn)題，主要目標(biāo)一般為利用率最大化。由于批量問(wèn)題對(duì)于生產(chǎn)中的損失成本無(wú)法優(yōu)化，為了更好地解決生產(chǎn)中的最優(yōu)化問(wèn)題，將最小化損失成本考慮到原批量問(wèn)題中去，形成了將下料與批量結(jié)合的新問(wèn)題（下文簡(jiǎn)稱為L(zhǎng)-C問(wèn)題）。L-C問(wèn)題多出現(xiàn)在家具生產(chǎn)、玻璃加工、鋁窗框加工、包裝等工業(yè)中，很多學(xué)者在這類問(wèn)題上都做了研究。Hendry[3]等人在1996年就提出了一種兩階段法來(lái)解決問(wèn)題，他們?cè)诘谝浑A段找到最優(yōu)下料方式，將其作為第二階段的已知條件從而求解，然而這種兩階段求解方法通常只能對(duì)其中一個(gè)目標(biāo)的優(yōu)化較為明顯，并不能得到全局的近似最優(yōu)解；Nonas和Thorstenson[4]解決了包括生產(chǎn)準(zhǔn)備成本和庫(kù)存成本的基于批量問(wèn)題的一維下料問(wèn)題，但其方法只適用于一維下料問(wèn)題，二維問(wèn)題無(wú)法采用此方法；Gramani和Franca[5]提出了一種解決結(jié)合批量問(wèn)題的二維下料問(wèn)題模型，為后來(lái)的學(xué)者研究L-C問(wèn)題提供了研究基礎(chǔ)，但并未提出更為有效的求解算法；Nonas和Thorstenson[6]利用列生成法解決結(jié)合批量的下料問(wèn)題，其方法只能解決小規(guī)模L-C問(wèn)題，并且算法的運(yùn)行效率不高；Poltroniere[7]等人利用啟發(fā)式算法解決造紙業(yè)中的實(shí)際生產(chǎn)問(wèn)題，通過(guò)實(shí)例可發(fā)現(xiàn)，該算法的利用率較低。在研究矩形件優(yōu)化排樣問(wèn)題中，國(guó)內(nèi)眾多學(xué)者通過(guò)設(shè)計(jì)不同算法來(lái)求解。崔耀東提出了利用遞歸算法[8-10]和分支定界法[11]來(lái)獲得有效解，但只適用于小規(guī)模二維下料問(wèn)題，無(wú)法解決批量問(wèn)題；楊玉麗[12]等人采用三塊排樣方式，基于背包問(wèn)題和動(dòng)態(tài)規(guī)劃算法有效地解決了矩形件排樣問(wèn)題，該算法可以得到矩形件排樣的近似最優(yōu)解，但同樣無(wú)法解決批量問(wèn)題；許繼影[13]提出了一種啟發(fā)式遞歸與遺傳算法相結(jié)合的混合啟發(fā)式算法，雖然可以解決較大規(guī)模的矩形件排樣問(wèn)題，但無(wú)法適用于L-C問(wèn)題。L-C問(wèn)題是結(jié)合了下料及批量問(wèn)題的新型復(fù)雜問(wèn)題，國(guó)外學(xué)者的研究起步較早，但總體來(lái)說(shuō)，對(duì)于中大規(guī)模問(wèn)題，并不能在保證算法運(yùn)行時(shí)間較短的情況下獲得近似最優(yōu)解，國(guó)內(nèi)學(xué)者對(duì)L-C問(wèn)題的研究則幾乎沒(méi)有。

由此可見，L-C問(wèn)題無(wú)論是在國(guó)外還是在國(guó)內(nèi)，其理論研究都較為缺乏，而在當(dāng)今經(jīng)濟(jì)全球化，以及原材料稀缺的社會(huì)，L-C問(wèn)題必將越來(lái)越普遍，無(wú)論是從理論研究出發(fā)還是從生產(chǎn)實(shí)際出發(fā)，提出一種較為有效的解決L-C問(wèn)題的方法是是迫切需要的。近幾十年來(lái)，進(jìn)化算法的應(yīng)用越來(lái)越廣泛，多目標(biāo)進(jìn)化算法成為多目標(biāo)優(yōu)化領(lǐng)域的研究熱點(diǎn)。Deb提出了非支配排序遺傳算法NSGA（Non-dominated Sorting Genetic Algorithm）將非支配排序的概念引入到多目標(biāo)優(yōu)化領(lǐng)域，然而由于其計(jì)算復(fù)雜度較高，沒(méi)有精英策略等缺點(diǎn)，繼而又提出了NSGA-II[14]算法，其良好的分布性和較快的收斂速度受到了國(guó)內(nèi)外學(xué)者的關(guān)注。為了充分解決L-C問(wèn)題，本文建立起多目標(biāo)排樣優(yōu)化模型，通過(guò)啟發(fā)式規(guī)則產(chǎn)生初始種群，并以NSGA-II為基礎(chǔ)設(shè)計(jì)了一種快速非支配排序算法對(duì)其進(jìn)行求解，并取得了較好的結(jié)果。

2 問(wèn)題描述及數(shù)學(xué)模型

某加工企業(yè)有一批長(zhǎng)L寬W的矩形板材，需要加工成長(zhǎng)li寬wi的小矩形零件M種，每種零件的需求數(shù)量為Di，i=1,2,…,M。每一時(shí)期需要生產(chǎn)每種零件數(shù)量多少取決于訂貨商對(duì)最終產(chǎn)品的需求數(shù)量。為了建立數(shù)學(xué)模型以解決在每一時(shí)期如何安排生產(chǎn)下料，現(xiàn)規(guī)定T為生產(chǎn)時(shí)期總數(shù)，M為零件類型總數(shù)，t=1,2,…,T，i=1,2,…,M。參數(shù)和變量定義如下：

在L-C問(wèn)題中，目標(biāo)分別最小化原料成本和零件庫(kù)存成本。原料成本屬于下料中的優(yōu)化目標(biāo)，零件庫(kù)存成本則屬于批量問(wèn)題中的優(yōu)化目標(biāo)，若分開考慮得到原料成本最小的下料方案，則零件庫(kù)存成本就可能相對(duì)偏高，若只是最優(yōu)化零件庫(kù)存成本則又可能導(dǎo)致下料過(guò)程中的原材料浪費(fèi)較多，因此必須將兩個(gè)問(wèn)題同時(shí)考慮。現(xiàn)假設(shè)：

上述數(shù)學(xué)模型中，式（1）為最小化所用原料的總成本；式（2）表示零件庫(kù)存成本最小化；約束條件（3）表示零件i的生產(chǎn)數(shù)量滿足其總需求量；式（4）為庫(kù)存平衡約束。

3 求解L-C問(wèn)題的算法

L-C問(wèn)題是兩種問(wèn)題的結(jié)合，單一問(wèn)題的求解方法對(duì)于該問(wèn)題的求解就存在了很多的局限性，傳統(tǒng)的最低水平線法以及智能算法都不能單獨(dú)有效解決L-C問(wèn)題。因此，通過(guò)利用相關(guān)啟發(fā)式規(guī)則優(yōu)化產(chǎn)生該問(wèn)題的初始種群，再利用能夠有效解決多目標(biāo)優(yōu)化問(wèn)題的改進(jìn)快速非支配排序算法進(jìn)行求解，可以同時(shí)解決下料問(wèn)題與批量問(wèn)題，大大提高了算法的有效性，具體算法流程如下：

步驟1初始化，隨機(jī)啟發(fā)生成種群規(guī)模為Npop的初始種群P0，計(jì)算個(gè)體的多目標(biāo)適應(yīng)值，對(duì)P0進(jìn)行快速非支配排序，執(zhí)行進(jìn)化算子，產(chǎn)生規(guī)模為Npop的子代種群Qg（g為進(jìn)化代數(shù)）。

步驟2合并父代種群Pg與子代種群Qg為Rg，計(jì)算Rg中個(gè)體的多目標(biāo)適應(yīng)值。

步驟3對(duì)Rg進(jìn)行快速非支配排序，確定各層Pareto最優(yōu)前沿面{F1,F2,…}。

步驟4計(jì)算個(gè)體擁擠度值，比較個(gè)體的優(yōu)劣，產(chǎn)生規(guī)模為Npop的新父代種群Pg。

步驟5執(zhí)行進(jìn)化算子，產(chǎn)生規(guī)模為Npop的新子代種群Qg。

步驟6判斷是否滿足終止條件，若滿足，輸出Pareto最優(yōu)解集，結(jié)束算法；否則，返回步驟2。

3.1 編碼方法

用Pj=(a1j,a2j,…,aij,…,aMj)，i=1,2,…,M，來(lái)表示第j種下料方式，其中aij表示下料方式j(luò)中含零件i的個(gè)數(shù)（aij可重復(fù)出現(xiàn)，總數(shù)不超過(guò)需求量）。yjt表示在t時(shí)期內(nèi)下料方式j(luò)的使用次數(shù)，則在t時(shí)期內(nèi)的下料方案就可以表示為：3.2初始下料方式

3.2.1 相關(guān)規(guī)則

在對(duì)下料方式進(jìn)行解碼排樣時(shí)，常見的算法有BL算法[15]、下臺(tái)階法[16]、最低水平線法[17]、剩余矩形算法[18]等。針對(duì)本文L-C問(wèn)題的特殊性，在最低水平線算法的基礎(chǔ)上進(jìn)行了改進(jìn)，制定了相關(guān)規(guī)則，使得排樣結(jié)果更加合理。為了方便敘述，現(xiàn)定義以下兩個(gè)概念：

定義1最低水平線寬度MinHW，是指距離板材底邊最近的那條水平線段的寬度，如圖1（a）所示。

定義2最低水平線高度MinHH，是指距離板材底邊最近的那條水平線段與板材底邊的高度，如圖1（b）所示。

圖1 最低水平線寬度及高度

（1）轉(zhuǎn)向規(guī)則：取β為板材的小邊，β=min(L,W)，比較d1=β-a×li，d2=β-b×wi，若d1＜d2，則li∥β，否則wi∥β。

（2）排放規(guī)則：

若MinHW大于所有未排零件尺寸，則繼續(xù)排樣；

若MinHW等于某一未排零件尺寸，則提前排入該零件，再繼續(xù)排樣；

若MinHW的大小介于未排零件尺寸之間，則搜索未排零件找到使得剩余寬度最小的零件排入，直至無(wú)法排入零件為止，再提升最低水平線高度MinHH，繼續(xù)排樣。

3.2.2 算法步驟

步驟1（初始化）原料剩余面積=原料初始面積，將待排零件放入集合π中。

步驟2隨機(jī)從π中選擇一種待排零件，在不超過(guò)原

步驟5判斷是否滿足所有零件需求，若滿足，輸出下料方式，結(jié)束算法。否則，更新零件的剩余需求量后返回步驟1。料剩余面積和該零件需求量的前提下，隨機(jī)生成一個(gè)整數(shù)作為該零件的排樣個(gè)數(shù)，根據(jù)規(guī)則排入到原料中。

步驟3更新原料剩余面積，將面積大于原料剩余面積的零件從π中刪除。判斷π是否為空，若為空，轉(zhuǎn)下一步；若不為空，更新π中待排零件的剩余需求量，返回步驟2。

步驟4按得到的下料方式Pj重復(fù)下料yjt次，直到該下料方式中的一個(gè)（或多個(gè)）零件滿足需求，或某一零件的需求量小于其在該下料方式中的排樣個(gè)數(shù)為止。

3.3 快速非支配排序算法

采用文獻(xiàn)[12]中NSGA-II算法對(duì)種群進(jìn)行排序并計(jì)算其個(gè)體擁擠度，每個(gè)個(gè)體i將得到非支配序ir和擁擠度id兩個(gè)屬性，采用偏序關(guān)系?n來(lái)比較兩個(gè)個(gè)體的優(yōu)劣，只有當(dāng)ir＜jr或者ir＝j(luò)r且id＞jd時(shí)，i?nj，表示如果兩個(gè)個(gè)體的非支配序不同，則序號(hào)低的個(gè)體（分級(jí)排序時(shí)先被分離出的個(gè)體）較優(yōu)；如果兩個(gè)個(gè)體的非支配序相同，則處于稀松區(qū)域的個(gè)體較優(yōu)。

3.4 進(jìn)化算子

為了保證種群個(gè)體的多樣性，本文設(shè)計(jì)了一種進(jìn)化方法，具體操作如下：

對(duì)于每一個(gè)個(gè)體隨機(jī)進(jìn)行位置變換操作或基因重新生成操作，由隨機(jī)數(shù)0和1決定。位置變換操作就是隨機(jī)選擇個(gè)體中的兩個(gè)基因位k1和k2(k1＜k2)，將k1前面的基因與k2后面的基因進(jìn)行位置交換（包括k1,k2），得到新的個(gè)體，例如，個(gè)體P1=(a41,a81,a31,a11,a51,a21)，k1=2，k2=5，則新個(gè)體P′1=(a51,a21,a31,a11,a41,a81)。重新生成操作則是隨機(jī)選擇個(gè)體中的一個(gè)基因位k，并將該基因位后面的基因全部刪除，還原成對(duì)應(yīng)的待排零件數(shù)量，再利用上述生成算法重新生成后面的基因。

3.5 精英策略

對(duì)所有產(chǎn)生的子代種群，將其與父代種群合并，共同產(chǎn)生新一代種群，提高優(yōu)化精度，以避免在進(jìn)化過(guò)程中的優(yōu)良個(gè)體丟失。

4 算例

為檢驗(yàn)算法的有效性，現(xiàn)假設(shè)現(xiàn)有某加工企業(yè)需制定3周生產(chǎn)計(jì)劃，生產(chǎn)的矩形件長(zhǎng)度在100～800范圍內(nèi)，寬度在100～500范圍內(nèi)，總需求數(shù)量在100～700范圍內(nèi)，板材尺寸為4 100×1 500。用隨機(jī)生成的方式產(chǎn)生矩形件的尺寸及需求數(shù)量，如表1所示。設(shè)零件平均庫(kù)存成本hit=0.5，單位原料成本c=100，規(guī)定進(jìn)化算法的初始種群規(guī)模Npop=2×106，進(jìn)化代數(shù)為100，算法在英特爾奔騰2.4 GHz處理器上的運(yùn)行時(shí)間為267 s，結(jié)果如表2和圖2所示。

表1 待加工零件尺寸及數(shù)量

表2 運(yùn)行結(jié)果

表3給出了本文算法與最短路徑列生成算法（SCM）以及兩階段算法（LSP+CCSP）的比較結(jié)果，數(shù)據(jù)均為平均值。

表3 算法比較

實(shí)驗(yàn)結(jié)果表明，在中等規(guī)模矩形件排樣問(wèn)題中，本文算法能夠在較快的時(shí)間內(nèi)保證較高的利用率，同時(shí)降低總成本。

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

矩形件排樣問(wèn)題與批量問(wèn)題相結(jié)合是實(shí)際生產(chǎn)中的常見問(wèn)題，本文通過(guò)建立包含原材料成本和零件庫(kù)存成本最小化兩個(gè)目標(biāo)的優(yōu)化模型，設(shè)計(jì)了一種啟發(fā)式進(jìn)化算法來(lái)求解該NP-hard問(wèn)題。該算法不僅解決了使用啟發(fā)式算法利用率低的缺點(diǎn)，而且還能夠在較短的時(shí)間內(nèi)得到較優(yōu)的下料方案，通過(guò)算例和其他算法的比較，證明了該算法的有效性。L-C問(wèn)題在實(shí)際生產(chǎn)中遠(yuǎn)比本文研究的要復(fù)雜的多，實(shí)際生產(chǎn)中往往要考慮到加工設(shè)備的等待與維護(hù)，以及設(shè)備的加工能力和使用原料的種類，如何有效解決這類問(wèn)題正是作者以后的研究方向。

圖2 下料方案對(duì)應(yīng)成本

[1]Lee A H I，Kang H Y，Lai C M.Solving lot-sizing problem with quantity discount and transportation cost[J].International Journal of Systems Science，2013，44（4）：760-774.

[2]Mobasher A，Ekici A.Solution approaches for the cutting stock problem with setup cost[J].Computers&Operation Research，2013，40（1）：225-235.

[3]Hendry L C，F(xiàn)ok K K，Shek K W.A cutting stock scheduling problem in the copper industry[J].Journal of the Operational Research，1996，47：38-47.

[4]Nonas S L，Thorstenson A.A combined cutting-stock and lot-sizingproblem[J].EuropeanJournalofOperational Research，2000，120（2）：327-342.

[5]Gramani M C N，F(xiàn)ranca P M.The combined cutting stock and lot-sizing problem in industrial processes[J].European Journal of Operational Research，2006，174：509-521.

[6]Nonas S L，Thorstenson A.Solving a combined cutting-stock and lot-sizing problem with a column generating procedure[J]. Computers&Operations Research，2008，35：3371-3392.

[7]Poltroniere S C，Poldi K C，Toledo F M B，et al.A coupling cutting stock-lot sizing problem in the paper industry[J]. Annals of Operations Research，2008，157（1）：91-104.

[8]崔耀東，黃健民，張顯全.矩形毛料無(wú)約束二維剪切排樣的遞歸算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（7）：948-951.

[9]崔耀東.生成矩形毛坯最優(yōu)T形排樣方式的遞歸算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（1）：125-127.

[10]崔耀東，季君，曾窕俊.生成矩形毛坯最優(yōu)兩段排樣方式的遞歸算法[J].南京航空航天大學(xué)學(xué)報(bào)，2006，38（1）：111-114.

[11]崔耀東，張春玲，趙誼.同尺寸矩形毛坯排樣的連分?jǐn)?shù)分支定界算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004，16（2）：252-256.

[12]楊玉麗，崔耀東，景運(yùn)革，等.生成矩形毛坯最優(yōu)三塊排樣方式的精確算法[J].機(jī)械設(shè)計(jì)與制造，2008（9）：11-13.

[13]許繼影.矩形件優(yōu)化排樣的混合啟發(fā)式方法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（13）：234-239.

[14]Deb K，Pratap A，Agrawal S，et al.A fast and elitist multi objective genetic algorithm：NSGA II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

[15]Edmund B，Robert H，Graham K，et al.A new bottom-left fill Heuristic algorithm for the two dimensional irregular packing problem[J].Operations Research，2006，54（3）：587-601.

[16]劉德全，滕弘飛.矩形件排樣問(wèn)題的遺傳算法求解[J].小型微型計(jì)算機(jī)系統(tǒng)，1998，19（12）：20-25.

[17]賈志欣，殷國(guó)富，羅陽(yáng).二維不規(guī)則零件排樣問(wèn)題的遺傳算法求解[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14（5）：467-470.

[18]李滿江，孟祥旭，王志強(qiáng).矩形件和任意多邊形排樣問(wèn)題的算法及應(yīng)用[J].貴州工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2002，31（4）：126-131.

ZHENG Mingyue1,LIU Lin1，2,KAN Fang1,FANG Chang1

1.School of Management,Hefei University of Technology,Hefei 230009,China
2.Key Laboratory of Process Optimization and Intelligent Decision-making,Ministry of Education,Hefei 230009,China

This paper studies the multi-objective rectangle packing problem combined with lot-sizing problem by multi-objective heuristic evolutionary algorithm.Establish a multi-objective optimization model containing the raw materials cost minimization and parts inventory cost minimization.Initialize the patterns by heuristic algorithm and then use improved fast non-dominated sorting algorithm getting the cutting program.Through the results and comparison with other algorithms, this algorithm can solve small rectangle packing problem with high utilization and low total cost in a fast time.

rectangle packing;lot-sizing;multi-objective optimization;heuristic;evolutionary algorithm

設(shè)計(jì)多目標(biāo)啟發(fā)式進(jìn)化算法，研究了一種考慮批量問(wèn)題的二維矩形件排樣問(wèn)題，建立了含有原材料成本最小化和零件庫(kù)存成本最小化的多目標(biāo)優(yōu)化模型。先用啟發(fā)式算法初始化下料方式，再用改進(jìn)的快速非支配排序算法進(jìn)行優(yōu)化求解，確定下料方案。通過(guò)實(shí)驗(yàn)結(jié)果以及與其他算法的對(duì)比表明，在中等規(guī)模的矩形件排樣問(wèn)題中，該算法能夠在較快的時(shí)間內(nèi)既保證較高的原料利用率，又能降低該問(wèn)題的總成本，證明了該算法的有效性。

矩形件排樣；批量問(wèn)題；多目標(biāo)優(yōu)化；啟發(fā)式；進(jìn)化算法

A

TP391

10.3778/j.issn.1002-8331.1212-0338

ZHENG Mingyue,LIU Lin,KAN Fang,et al.Multi-objective rectangle packing problem combined with lot-sizing problem.Computer Engineering and Applications,2014,50（22）：260-264.

國(guó)家自然科學(xué)基金重點(diǎn)基金（No.71231004）；國(guó)家自然科學(xué)基金（No.71171071）；安徽省高校省級(jí)自然科學(xué)研究項(xiàng)目（重點(diǎn)）（No.KJ2011A215）。

鄭明月（1988—），女，碩士生，研究領(lǐng)域?yàn)槎嗄繕?biāo)優(yōu)化下料問(wèn)題；劉林（1964—），男，博士，副教授，研究方向?yàn)樯a(chǎn)運(yùn)作管理、優(yōu)化與決策、管理信息系統(tǒng)；闞方（1989—），女，碩士生，研究方向多目標(biāo)優(yōu)化下料、決策科學(xué)與技術(shù)；方昶（1986—），男，博士生，研究方向?yàn)閮?yōu)化調(diào)度、多目標(biāo)優(yōu)化下料。E-mail：mingyue1020@126.com

2012-12-28

2013-04-17

1002-8331（2014）22-0260-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-04-18,http://www.cnki.net/kcms/detail/11.2127.TP.20130418.1618.019.html