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

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

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

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

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

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

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

1 引言

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

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

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

某加工企業(yè)有一批長L寬W的矩形板材，需要加工成長li寬wi的小矩形零件M種，每種零件的需求數(shù)量為Di，i=1,2,…,M。每一時(shí)期需要生產(chǎn)每種零件數(shù)量多少取決于訂貨商對最終產(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問題中，目標(biāo)分別最小化原料成本和零件庫存成本。原料成本屬于下料中的優(yōu)化目標(biāo)，零件庫存成本則屬于批量問題中的優(yōu)化目標(biāo)，若分開考慮得到原料成本最小的下料方案，則零件庫存成本就可能相對偏高，若只是最優(yōu)化零件庫存成本則又可能導(dǎo)致下料過程中的原材料浪費(fèi)較多，因此必須將兩個(gè)問題同時(shí)考慮?，F(xiàn)假設(shè)：

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

3 求解L-C問題的算法

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

步驟1初始化，隨機(jī)啟發(fā)生成種群規(guī)模為Npop的初始種群P0，計(jì)算個(gè)體的多目標(biāo)適應(yīng)值，對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對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，來表示第j種下料方式，其中aij表示下料方式j(luò)中含零件i的個(gè)數(shù)（aij可重復(fù)出現(xiàn)，總數(shù)不超過需求量）。yjt表示在t時(shí)期內(nèi)下料方式j(luò)的使用次數(shù)，則在t時(shí)期內(nèi)的下料方案就可以表示為：3.2初始下料方式

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

在對下料方式進(jìn)行解碼排樣時(shí)，常見的算法有BL算法[15]、下臺(tái)階法[16]、最低水平線法[17]、剩余矩形算法[18]等。針對本文L-C問題的特殊性，在最低水平線算法的基礎(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的大小介于未排零件尺寸之間，則搜索未排零件找到使得剩余寬度最小的零件排入，直至無法排入零件為止，再提升最低水平線高度MinHH，繼續(xù)排樣。

3.2.2 算法步驟

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

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

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

3.4 進(jìn)化算子

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

對于每一個(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，并將該基因位后面的基因全部刪除，還原成對應(yīng)的待排零件數(shù)量，再利用上述生成算法重新生成后面的基因。

3.5 精英策略

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

4 算例

為檢驗(yàn)算法的有效性，現(xiàn)假設(shè)現(xiàn)有某加工企業(yè)需制定3周生產(chǎn)計(jì)劃，生產(chǎn)的矩形件長度在100～800范圍內(nèi)，寬度在100～500范圍內(nèi)，總需求數(shù)量在100～700范圍內(nèi)，板材尺寸為4 100×1 500。用隨機(jī)生成的方式產(chǎn)生矩形件的尺寸及需求數(shù)量，如表1所示。設(shè)零件平均庫存成本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ī)模矩形件排樣問題中，本文算法能夠在較快的時(shí)間內(nèi)保證較高的利用率，同時(shí)降低總成本。

5 結(jié)束語

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

圖2 下料方案對應(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]崔耀東，黃健民，張顯全.矩形毛料無約束二維剪切排樣的遞歸算法[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]劉德全，滕弘飛.矩形件排樣問題的遺傳算法求解[J].小型微型計(jì)算機(jī)系統(tǒng)，1998，19（12）：20-25.

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

[18]李滿江，孟祥旭，王志強(qiáng).矩形件和任意多邊形排樣問題的算法及應(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)化算法，研究了一種考慮批量問題的二維矩形件排樣問題，建立了含有原材料成本最小化和零件庫存成本最小化的多目標(biāo)優(yōu)化模型。先用啟發(fā)式算法初始化下料方式，再用改進(jìn)的快速非支配排序算法進(jìn)行優(yōu)化求解，確定下料方案。通過實(shí)驗(yàn)結(jié)果以及與其他算法的對比表明，在中等規(guī)模的矩形件排樣問題中，該算法能夠在較快的時(shí)間內(nèi)既保證較高的原料利用率，又能降低該問題的總成本，證明了該算法的有效性。

矩形件排樣；批量問題；多目標(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.

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

鄭明月（1988—），女，碩士生，研究領(lǐng)域?yàn)槎嗄繕?biāo)優(yōu)化下料問題；劉林（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