基于寬容分層策略的啟發(fā)式排樣算法

梁利東,賈文友

0 引言

Packing問題的排樣優(yōu)化方法是工程設(shè)計(jì)及制造領(lǐng)域中的研究熱點(diǎn),廣泛應(yīng)用于機(jī)械制造、印刷業(yè)排版、木材加工、玻璃切割、家具下料、服裝裁剪等行業(yè)中,高效排樣算法的研究對(duì)提高生產(chǎn)效率和經(jīng)濟(jì)效益具有重要的實(shí)際意義。二維(2D) Packing問題是尋找平面最優(yōu)布局的優(yōu)化問題,即將一系列零件不可相互重疊地合理布置在原材料中,使原材料的利用率達(dá)到最大。作為組合優(yōu)化領(lǐng)域中計(jì)算復(fù)雜性最高的一類非確定性多項(xiàng)式完全(Nondeterministic Polynomial Complete, NPC)問題[1],排樣方法涉及計(jì)算機(jī)科學(xué)及數(shù)值優(yōu)化理論的核心問題,因此具有深刻的理論研究?jī)r(jià)值。

通常的優(yōu)化排樣問題(以矩形件為例)的數(shù)學(xué)模型可表示為:

(1)

s.t.Pi(Δxi,Δyi)∩Pj(Δxj,Δyj)=?,i≠j

(2)

0≤xim(θi,Δxi,Δyi)≤L,m=1,2,…,ni

(3)

0≤yim(θi,Δxi,Δyi)≤W,m=1,2,…,ni

(4)

其中：ti為參與排樣因子,表示零件i是否參與排樣,取值為1或0;xim和yim為零件i上第m個(gè)頂點(diǎn)的坐標(biāo)。約束式(2)表示零件與互不重疊,約束式(3)～(4)表示所有零件不能排在原材料之外。由于面積Si是一個(gè)與位置無關(guān)的參數(shù),因此上面的優(yōu)化排樣模型中,其決策變量為θi、Δxi、Δyi、ti。

排樣問題的求解包括排序方法和定位規(guī)則兩個(gè)方面,目前研究的算法主要分為三類:精確算法、啟發(fā)式算法和元啟發(fā)式算法(meta-heurisic methods)。精確算法如樹搜索、分枝定界法等[2-3],算法的計(jì)算復(fù)雜度太高、耗時(shí)較大,對(duì)于排樣規(guī)模也有局限;而啟發(fā)式算法源于數(shù)值計(jì)算理論的有效性,可在合理的時(shí)間范圍內(nèi)獲得近似較好的解而得到廣泛運(yùn)用,典型的啟發(fā)式定位算法如表1所示。

隨著智能優(yōu)化算法,如模擬退火算法(Simulated Annealing, SA)、遺傳算法(Genetic Algorithm, GA)、人工神經(jīng)網(wǎng)絡(luò)(Artificial Neural Network, ANN)、粒子群優(yōu)化(Particle Swarm Optimization, PSO)及蟻群優(yōu)化(Ant Colony Optimization, ACO)算法等方法的日益成熟,元啟發(fā)式算法則是利用智能算法實(shí)現(xiàn)排樣次序的優(yōu)化,并結(jié)合基本啟發(fā)式算法來求解Packing問題。如Jiang等[16]結(jié)合遺傳算法提出了GA+底部左齊擇優(yōu)匹配(Lowest-Level Left Align Best Fit, LLABF)算法，Liu等[17]提出了GA+IBL(Improved Bottom Left)算法,二者都是在BL算法的基礎(chǔ)上對(duì)其進(jìn)行改進(jìn);基于最小浪費(fèi)的思想,Zhang等[18]提出了GA+IHR(Improved Heuristic Recursive)算法;Hopper等[19]將BLF與GA和SA等智能算法相結(jié)合,提出了GA+BLF、SA+BLF等算法,也都是基于BL算法所進(jìn)行的優(yōu)化;基于BF(Best Fit)的思想,Burke等[20]分別結(jié)合禁忌搜索(Tabu Search, TS)、SA和GA算法,實(shí)現(xiàn)并比較了BF+TS、BF+SA和BF+GA這三種算法的性能,取得了比BF算法更好的結(jié)果,同時(shí)發(fā)現(xiàn),BF+SA可以取得最好的效果;Borfeldt[21]結(jié)合遺傳算法給出了基于層的該問題的SPGAL(Strip Packing Genetic Algorithm based on Layer)。

表1 啟發(fā)式排樣算法

上述啟發(fā)式算法在求解矩形件Packing問題中大都取得不錯(cuò)的結(jié)果,特別是LSBF算法[15]和LLABF算法[16]均采用了擇優(yōu)匹配的定位方法,并通過枚舉建立矩形匹配的適應(yīng)度評(píng)價(jià)值,獲得部分Benchmark的完美排樣。但兩種算法的匹配優(yōu)先原則都側(cè)重于完全匹配(Full Fit, FF)和部分匹配類型,如寬度匹配(Width Fit, WF)、高度匹配(Height Fit, HF)和組合匹配(Joint Fit,JF),而對(duì)于可能出現(xiàn)的多種可排入匹配(Placeable Fit, PF)的一般情形,由于缺乏排入匹配的評(píng)價(jià)機(jī)制,對(duì)全局排樣布局將產(chǎn)生不同的影響。文獻(xiàn)[10]的砌墻啟發(fā)式算法中通過設(shè)定絕對(duì)基準(zhǔn)磚高度來約束每層的排樣空間,可有效控制最低排樣高度,但該算法與擇優(yōu)匹配思想存在一定矛盾。

綜合以上算法的優(yōu)劣,本文基于多目標(biāo)寬容分層規(guī)劃思想,提出一種寬容分層的啟發(fā)式算法(Forbearing Stratified Heuristic Algorithm, FSHA),該算法構(gòu)造擇優(yōu)匹配優(yōu)化模型及評(píng)價(jià)函數(shù),以此來設(shè)計(jì)排放矩形的優(yōu)先規(guī)則,并針對(duì)一般排放情況,引入寬容參數(shù),實(shí)現(xiàn)矩形定位的優(yōu)化過程。

1 FSHA模型

1.1 問題的描述及定義

Packing問題的最優(yōu)求解是尋求諸多幾何體在不能重疊和超出邊界的約束下在給定板材區(qū)域中的最優(yōu)圖形組合,以獲得最小排樣高度或最大排樣密度。在矩形排樣中,假設(shè)初始板材區(qū)域?qū)挾葹閃,高度為H,待排n個(gè)矩形表示為pj(xj,yj,wj,hj),j∈{1,2,…,n}。其中:(xj,yj)表示pj的左下角坐標(biāo);(wj,hj)表示的寬度和高度。建立笛卡兒坐標(biāo)系,相關(guān)定義如下:

1)排樣空間。表示當(dāng)前m個(gè)空閑矩形區(qū)域,可表示為Si(sxi,syi,swi,shli,shri),i∈{1,2,…,m},其中(sxi,syi)為該空間左下角坐標(biāo),swi為該空間的寬度,(shli,shri)分別表示該空間左壁和右壁的高度。若空間左壁(或右壁)為板材邊界,則shli=H或shri=H,如圖1所示。

2)可行空間。若存在待排矩形,使得wj≤swi,則該空間為可行空間；否則為不可行空間。

3)合并空間。當(dāng)存在不可行空間,該空間則與相鄰空間進(jìn)行合并產(chǎn)生新的空間。

圖1 排樣空間的定義

排樣矩形與排樣空間建立參數(shù)匹配關(guān)系,并以此設(shè)計(jì)矩形放置規(guī)則,定義如下:

1)寬度匹配值fwij，表征可行空間Si的寬度與排入矩形pj的寬度的匹配程度,其中當(dāng)swi=wj時(shí),寬度匹配最佳。計(jì)算公式如下:

(5)

2)高度匹配值fhij表征可行空間的高度與排入矩形高度的匹配程度,其中,當(dāng)Δhlij=0(左平齊)或Δhrij=0(右平齊),則fhij=1,高度匹配為最佳。計(jì)算公式如下:

(6)

基于以上排樣空間的劃分及匹配值的定義,選定最低排樣空間,遍歷所有待排矩形與該空間進(jìn)行匹配排放。圖2為不同的匹配類型,基本涵蓋了待排矩形的全部可排放情景,其中假設(shè)shr≤shl;反之情況類似。

圖2 不同匹配值

1.2 匹配函數(shù)模型及適應(yīng)度

當(dāng)前矩形的匹配擇優(yōu)過程可視為寬度匹配值和高度匹配值最大化的多目標(biāo)優(yōu)化問題,優(yōu)化函數(shù)的數(shù)學(xué)模型表示如下:

V-maxFij=max [fwij,fhij]

(7)

s.twj≤swi

hj≤H

從圖2的4種匹配類型中,只有完全匹配為多目標(biāo)目標(biāo)函數(shù)的當(dāng)前最優(yōu)解,其他匹配情形均無法獲得最優(yōu),因此可根據(jù)不同匹配情況,設(shè)計(jì)其目標(biāo)函數(shù)(或稱匹配適應(yīng)度)的計(jì)算方法及排放規(guī)則:

1)完全匹配。待排矩形的寬度等于可排空間寬度即fwij=1,且高度等于可排空間高度(包括左高平或右高平)即fhij=1。匹配適應(yīng)度值Fij=fwij+fhij=2,為最佳匹配。若存在多個(gè)完全匹配情形時(shí),矩形高度hj小者優(yōu)先入排。

2)部分匹配。只滿足寬度匹配或高度匹配即fwij=1,fhij<1或fwij<1,fhij=1,匹配適應(yīng)度值Fij=max(fwij,fhij)=1,排入規(guī)則:

① 若多個(gè)矩形同時(shí)符合寬度匹配或高度匹配,以入排次序進(jìn)行排放;

② 若多個(gè)矩形僅符合寬度匹配,矩形hj小者優(yōu)先入排;

③ 若多個(gè)矩形僅符合高度匹配時(shí),矩形寬度小者優(yōu)先且向高度平齊一方靠接排放。

3)可排入匹配。待排矩形的寬度小于可排空間寬度即fwij<1,且高度與可排空間高度不相等即fhij<1,匹配適應(yīng)度值為Fij=c1fwij+c2fhij,其中c1、c2(c1,c2∈(0,0.5])分別為寬度和高度寬容值,即當(dāng)存在多個(gè)矩形同時(shí)滿足可排入匹配時(shí),兩個(gè)寬容值決定寬度和高度匹配的選擇權(quán)重(在起始階段,初始空間通常對(duì)于所有矩形均為可排入匹配,且H視為無限高,第一個(gè)入排矩形的選擇根據(jù)排放序列確定)。設(shè)置寬容值旨在對(duì)兩個(gè)匹配分目標(biāo)的實(shí)現(xiàn)分層優(yōu)化策略。注意:當(dāng)排樣空間左(或右)邊為板材邊界時(shí),則采用占角規(guī)則[14]。

可見,最優(yōu)化匹配適應(yīng)度函數(shù)取決于排樣空間三個(gè)匹配參數(shù)的關(guān)系,即:Δw為排樣區(qū)域?qū)挾扰c入排矩形寬度的絕對(duì)差值;Δhl為排樣區(qū)域的左邊(壁)高度與入排矩形高度的絕對(duì)差值;Δhr為排樣區(qū)域的左邊(壁)高度與入排矩形高度的絕對(duì)差值。表2給出匹配適應(yīng)度及參數(shù)關(guān)系說明。

表2 匹配適應(yīng)度評(píng)價(jià)及參數(shù)說明

注:匹配類型可通過矩形旋轉(zhuǎn)實(shí)現(xiàn)擇優(yōu)匹配。

2 FSHA流程

FSHA是依據(jù)匹配適應(yīng)度值和擇優(yōu)匹配優(yōu)先原則實(shí)現(xiàn)分層定位布局的啟發(fā)式算法,其算法設(shè)計(jì)如下。

輸入 板材的寬度W和高度H(無限高),n個(gè)待排矩形pj(xj,yj,wj,hj),j∈{1,2,…,n}。

輸出 排樣高度或排樣密度,其中

FSHA()

{

for(j=1;j<=n;j++) initialize (RectList[]);

//初始化矩形入排序列

設(shè)置寬容參數(shù)c1,c2

for(i=0;i<可行排樣空間數(shù)目,i++){

for(j=1;j<=n;j++) {

if (S(i)為不可行空間); break;

//選擇下一個(gè)最低空間

Function_FitType(i,j)

//判斷匹配類型

if (Δw=0, Δh=0,)Fij=2 break;

//完全匹配類型

Else if(Δw=0, Δh>0)Fij=1;

//寬度匹配類型

Select(min(hj));

//選擇高度最低矩形

Else if(Δw>0, Δh=0)Fij=1;

//高度匹配類型

Select(min(wj));

//選擇寬度最小矩形

Else if(Δw>0, Δh>0) {

可排入匹配類型,計(jì)算當(dāng)前匹配適應(yīng)度Fij

Select(max(Fij));

//選擇適應(yīng)度最大矩形

}

}

Pack(i,j); 在空間i排入矩形RectList[j]

更新排樣空間S(i),并以空間最低原則排序

}

計(jì)算輸出排樣適應(yīng)度(排樣高度或排樣密度)

}

基于以上算法的實(shí)現(xiàn)過程,FSHA的流程示意如圖3所示。

圖3 FSHA流程

3 FSHA應(yīng)用舉例

算例1 給定5個(gè)待排矩形,如不考慮旋轉(zhuǎn),可存在4種最優(yōu)排樣布局,其排樣高度均為最優(yōu)高度,排樣密度達(dá)到100%,如圖4所示。要獲得一個(gè)最優(yōu)布局(以圖4(a)為例),對(duì)于序列模式{1,2,*,*,*} (“*”表示未列出的矩形編號(hào)),LLABF、LSBF及砌墻式算法得到排樣布局都出現(xiàn)空洞現(xiàn)象,如圖5所示。

圖4 算例1的最優(yōu)排樣結(jié)果

圖5 LLABF、LSBF及砌墻式算法的排樣布局

采用FSHA匹配原理及評(píng)價(jià)方法,只要矩形1為第一個(gè)入排矩形,均可獲得如圖4(a)的最優(yōu)排樣布局,算法步驟如下:

1)初始化排樣空間和參考位置原點(diǎn),初始空間為S0(0,0,W,H)。

2)起始階段,所有零件均屬于可排入匹配情況,直接入排矩形1,選擇最低空間S。

3)依照算法的匹配規(guī)則,矩形2為當(dāng)前最低空間S唯一可排入矩形,且滿足寬度匹配,F=1,寬度匹配不受排樣高度約束,故排入2,更新最低空間S。

4)遍歷未排矩形,矩形4和5都滿足高度匹配,maxF=1,依據(jù)寬度小者優(yōu)先和匹配邊靠接原則,選擇4排入。

5)依次類推,可依次排入矩形3和5,構(gòu)成最佳排樣布局,如圖6所示。

可以看出, FSHA對(duì)于排序模式{2,*,*,*,*}、{5,*,*,*,*}、{3,*,*,*,*},也均可獲得其他最優(yōu)布局如圖4(b)、(c)和(d)。

圖6 算例1的排樣過程

算例2 假設(shè)板材寬度W=100,高度H不限,取6個(gè)矩形,并任意給定各矩形的寬度和高度,矩形序列P可表示為{p1(42,30),p2(40,18),p3(40,26),p4(40,10),p5(16,44),p6(44,8)},如圖7(a)所示。可以發(fā)現(xiàn),無論怎樣排放均無法獲得理想的最優(yōu)布局,此為大規(guī)模排樣中常見的一般情形,因此,快速尋求較好的有效解是設(shè)計(jì)排樣算法的關(guān)鍵。

以{1,*,*,*,*}排入模式為例(暫不考慮旋轉(zhuǎn)),根據(jù)本文算法規(guī)則首先排入矩形1,確定最低空間S,由于不存在完全匹配和部分匹配,按照式(5)～(6)分別計(jì)算剩余待排矩形{p2,p3,p4,p5,p6}與S的匹配適應(yīng)度,Fi=c1fwi+c2fhi。取c1=c2=0.5,可得:F2=0.644 8,F3=0.778 2,F4=0.511 5,F5=0.404 6,F6=0.512 6。若調(diào)整寬容參數(shù)為c1=0.5,c2=0,1,可得F2=0.404 8,F3=0.431 5,F4=0.378 1,F5=0.191 2,F6=0.406 0?？芍猰axF=F3,故選擇矩形3排入。依次類推,排完所有待排矩形,可得到排放序列{1,3,5,2,6,4},排樣高度Hpack=48,排樣密度為93.25%,此為較好的有效解,如圖7(g)所示。對(duì)于排入模式{1,2,3,4,5},LLABF和砌墻式算法,得到排樣結(jié)果如圖7(h)和(i)所示。若要獲得更好解,還需進(jìn)行排序優(yōu)化。

4 GA+FSHA

FSHA的匹配規(guī)則雖對(duì)排序進(jìn)行了局部?jī)?yōu)化,但隨排樣規(guī)模的增加仍依賴于矩形序列的全局尋優(yōu),本文采用遺傳算法GA與FSHA結(jié)合方式來求解二維矩形條排樣優(yōu)化問題。由GA確定種群規(guī)模、編碼方式并隨機(jī)生成初始矩形集合的排序,利用FSHA決定矩形的排放規(guī)則,通過遺傳操作和適應(yīng)度評(píng)價(jià)來實(shí)現(xiàn)矩形排樣的最優(yōu)化過程。

4.1 編碼及適應(yīng)度函數(shù)

對(duì)于矩形Packing問題,通常采用序號(hào)編碼方式進(jìn)行編碼設(shè)計(jì),個(gè)體染色體序號(hào)編碼可表示為Ek={1,2,…,n}。編碼中序號(hào)對(duì)應(yīng)入排零件,正負(fù)表示矩形旋轉(zhuǎn)與否。例如編碼{1,3,-2,4,-5},表示矩形排入順序?yàn)?3 245,其中矩形2和5需旋轉(zhuǎn)90°。

設(shè)給定板材的規(guī)格尺寸(寬度W和高度H為定值),個(gè)體的適應(yīng)度評(píng)價(jià)分兩種情況:

1)如果所有待排矩形均可排入,優(yōu)化目標(biāo)為最低排樣高度或最大排樣密度,個(gè)體適應(yīng)度函數(shù)表示為Fit=1/Hpack,其中Hpack為個(gè)體的矩形排樣高度。

2)如果所有待排矩形不可能全部排入,根據(jù)匹配適應(yīng)值和個(gè)體排序的不同,可導(dǎo)致即使同一塊板材,多次排樣結(jié)果所包含的零件數(shù)量和種類亦不相同。因此,排樣目標(biāo)為每個(gè)入排矩形匹配值求和的最大值,個(gè)體適應(yīng)度函數(shù)如下表示:

(8)

4.2 遺傳操作

1)選擇運(yùn)算。對(duì)種群中所有個(gè)體的適應(yīng)度值從大到小排序,優(yōu)選首位基因不同的m個(gè)最優(yōu)個(gè)體(視種群規(guī)模而定)直接作為下一代個(gè)體,其余n-m個(gè)體以輪盤賭方式[18]進(jìn)行選擇。該選擇方法是基于匹配定位規(guī)則的局部排序優(yōu)化,實(shí)現(xiàn)個(gè)體的最優(yōu)保存和種群多樣性策略。

2)交叉運(yùn)算。本文采用兩點(diǎn)交叉,以一定的概率pc交換兩個(gè)體的基因片斷而產(chǎn)生新個(gè)體的過程。即在區(qū)間[1,n]內(nèi)生成兩個(gè)不等的隨機(jī)數(shù)p和q作為交叉位,設(shè)p

3)變異運(yùn)算。采用雙變異方式,即按照變異概率pm對(duì)個(gè)體的排序和旋轉(zhuǎn)進(jìn)行操作。其中排序變異是對(duì)隨機(jī)產(chǎn)出的兩變異點(diǎn)(α1,α2)的矩形互換位置;旋轉(zhuǎn)變異則是對(duì)變異點(diǎn)r的矩形旋轉(zhuǎn)角度90°。如:選擇個(gè)體為{1,2,3,4,5},變異點(diǎn)(α1,α2)=(3,5),r=4,經(jīng)過變異操作后產(chǎn)生的新個(gè)體表示為{1,2,5,-4,3}。

5 實(shí)驗(yàn)與分析

本文開發(fā)環(huán)境為VB 6.0+SQL Server 2000,實(shí)驗(yàn)平臺(tái)為Intel CPU 2.4 GHz, 4 GB RAM, Windows 10。設(shè)定種群規(guī)模為20,預(yù)設(shè)寬容系數(shù)c1=c2=0.5,交叉概率pc=0.8,變異概率pm=0.5。

實(shí)驗(yàn)1 對(duì)兩組理想排樣布局進(jìn)行算法測(cè)試,其中一組以200×200的板材隨機(jī)劃分生成算例數(shù)據(jù),如表3所示。另一組來自文獻(xiàn)[19]的C1P1(Category1 Problem1)問題(W×H=20×20, 16 items),運(yùn)用FSHA運(yùn)行10次,均獲得最優(yōu)排樣布局如圖8所示。

表3 隨機(jī)算例的測(cè)試數(shù)據(jù)

圖8 實(shí)驗(yàn)1的最優(yōu)排樣布局

實(shí)驗(yàn)2 為驗(yàn)證算法的有效性,根據(jù)問題規(guī)模的不同,本文對(duì)benchmark的7類數(shù)據(jù)[19]分別進(jìn)行測(cè)試,不同算法的實(shí)驗(yàn)對(duì)比結(jié)果如表4所示。

表4 算例的測(cè)試數(shù)據(jù)的 Gap 值 %

表4中:Gap表示為排樣的相對(duì)高度,即Gap=(Hpack-H*)/H*,其中H*為理想高度?？梢钥闯?本文算法對(duì)于小規(guī)模問題均可獲得滿意的最優(yōu)解,隨著問題規(guī)模的增加,相對(duì)于A1及LLABS算法,Gap的平均值降低了2%。注意:以上測(cè)試結(jié)果在FSHA求解中,是通過隨機(jī)調(diào)整不同的寬容值c1和c2而獲得的最優(yōu)結(jié)果。實(shí)驗(yàn)發(fā)現(xiàn),寬容系數(shù)c1和c2的不同取值對(duì)實(shí)驗(yàn)結(jié)果具有一定的影響:c1越大,寬度匹配越優(yōu)先于高度匹配，反之亦然；其大小的選擇往往隨著排樣問題和排樣規(guī)模的不同而需測(cè)試調(diào)整。

實(shí)驗(yàn)3 針對(duì)不同矩形類型入排的一般情況,本文從benchmark的7類數(shù)據(jù)中隨機(jī)選擇兩組數(shù)據(jù)進(jìn)行測(cè)試,GA迭代次數(shù)為50,最優(yōu)排樣結(jié)果如圖9所示。其中,一組數(shù)據(jù)取自C1P1+C3P1中的33個(gè)矩形,設(shè)置板材寬度為20,高度不限(水平方向),計(jì)算排樣高度為24,排樣密度為93.35%;另一組數(shù)據(jù)從C2～C7中任選66個(gè)矩形,設(shè)置板材寬度為100,高度不限,計(jì)算排樣高度為339,排樣密度為91.28%。

圖9 實(shí)驗(yàn)3的最優(yōu)排樣布局

實(shí)驗(yàn)4 FSHA方法也可應(yīng)用于異形件排樣,數(shù)據(jù)取自某船舶零件,設(shè)置板材規(guī)格W*H=2 000*6 000。排樣過程采用了異形件的矩形化包絡(luò)和組合填充的預(yù)處理操作,在每個(gè)包絡(luò)零件排入后再進(jìn)行正交靠接。圖10為不經(jīng)過排序優(yōu)化由初始序列一次得到排樣結(jié)果,可排入65個(gè)零件,排樣密度達(dá)到87.37%,其中排樣密度為排入零件的面積之和與板材面積的比率。排樣結(jié)果的板材利用率雖不算太高,但可以說明該算法在異形件排樣過程中的有效性。基于異形零件圖形的不規(guī)則特征,可結(jié)合相關(guān)不規(guī)則件排樣算法進(jìn)行研究探索。

圖10 異形件的排樣布局

6 結(jié)語

本文針對(duì)二維矩形Packing問題,提出了基于寬容分層規(guī)則及匹配函數(shù)評(píng)估的優(yōu)化算法FSHA,并給出了算法的思想、模型，以及具體實(shí)現(xiàn)方法。實(shí)驗(yàn)結(jié)果表明,該算法的定位寬容分層匹配策略明確了不同匹配類型的劃分和優(yōu)先放置規(guī)則,可有效優(yōu)化排樣結(jié)果,并可結(jié)合碰靠算法應(yīng)用于異形件packing問題的求解。由于寬容值的大小設(shè)定直接影響排樣定位規(guī)則和最優(yōu)布局,寬容參數(shù)的取值決定了寬度匹配和高度匹配的優(yōu)先程度,如何將其與排放矩形和排樣空間的圖形屬性建立關(guān)系,將是下一步研究的重點(diǎn)。

參考文獻(xiàn)(References)

[1] LODI A, MARTELLO S, MONACI M. Two-dimensional packing problems: a survey[J]. European Journal of Operational Research, 2002, 141(2): 241-252.

[2] LESH N, MARKS J, MAHON A, et al. Exhaustive approaches to 2D-rectangular perfect packings[J]. Information Processing Letters, 2004, 90(1): 7-14.

[3] MARTELLO S, MONACI M, VIGO D. An exact approach to the strip-packing problem [J]. INFORMS Journal of Computing, 2003, 15(3): 310-319.

[4] BAKER B, COFFMAN E, RIVEST L. Orthogonal packings in two dimensions [J]. SIAM Journal on Computing, 1980, 9(4): 846-855.

[5] CHAZELLE B. The bottom left bin packing heuristic: an efficient implementation [J]. IEEE Transactions on Computers, 1983, C-32(8): 697-707.

[6] HOPPER E, TURTON B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research, 2001, 128(1): 34-57.

[7] LESH N, MITZENMACHER M. BubbleSearch: a simple heuristic for improving priority-based greedy algorithms [J]. Information rocessing Letters, 2006, 97(4): 161-169.

[8] BURKE E, KENDALL G, WHITWELL G. A new placement heuristic for the orthogonal stock-cutting problem[J]. Operations Research, 2004, 52(4): 655-671.

[9] BORTFELDT A, GEHRING H. New large benchmark instances for the two-dimensional strip-packing problem with rectangular pieces[C]// Proceedings of the 39th Hawaii International Conference on Systems Sciences. Washington, DC: IEEE Computer Society, 2006: 30.

[10] 張德富, 韓水華, 葉衛(wèi)國.求解矩形Packing問題的砌墻式啟發(fā)式算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(3) : 509-515.(ZHANG D F, HAN S H, YE W G. A bricklaying heuristic algorithm for the orthogonal rectangular packing problem[J]. Chinese Journal of Computers, 2008, 31(3): 509-515.)

[11] 姚怡, 吳金波, 賴朝安. 采用分層搜索填充策略的啟發(fā)式帶排樣算法[J]. 武漢大學(xué)學(xué)報(bào)(工學(xué)版), 2014, 47(6): 854-859.(YAO Y, WU J B, LAI C A. Heuristics for rectangular strip packing problem based on hierarchical search filled strategy[J]. Engineering Journal of Wuhan University, 2014, 47(6) : 854-859.)

[12] 何琨, 姬朋立. 求解二維矩形Packing面積最小化問題的動(dòng)態(tài)規(guī)約算法[J]. 軟件學(xué)報(bào), 2013, 24(9): 2078-2087.(HE K, JI P L. Heuristics for solving the 2D rectangle packing area minimization problem basing on a dynamic reduction method[J]. Journal of Software, 2013, 24(9): 2078-2087.)

[13] HUANG W, CHEN D, XU R. A new heuristic algorithm for rectangle packing[J]. Computer & Operations Research, 2007, 34(11): 3270-3280.

[14] CHEN M, HUANG W. A two-level search algorithm for 2D rectangular packing problem[J]. Computer & Industrial Engineering, 2007, 53(1): 123-136.

[15] 張懷宇, 楊根科, 白杰. 二維Strip Packing問題的嵌套啟發(fā)式算法[J]. 系統(tǒng)仿真學(xué)報(bào), 2012, 24(8): 1601-1605, 1623.(ZHANG H Y, YANG G K, BAI J. Nested heuristic algorithm for two-dimensional strip packing problem[J]. Journal of System Simulation, 2012, 24(8) : 1601-1605, 1623.)

[16] JIANG X, LU X, LIU C. Lowest-level left align best-fit algorithm for the 2D rectangular strip packing problem[J]. Journal of Software, 2009, 20(6): 1528-1538.

[17] LIU D, TENG H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles[J]. European Journal of Operation Research, 2006, 172(3): 814-837.

[18] ZHANG D, CHEN S, LIU Y. An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem[J]. Acta Automatica Sinica, 2007, 33(9): 911-916.

[19] HOPPER E, TURTON B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research, 2001, 128(1): 34-57.

[20] BURKE E, KENDALL G, WHITWELL G. Metaheuristic enhancements of the best-fit heuristic for the orthogonal stocking cutting problem: NOTTCS-TR-2006-3[R]. Nottingham: University of Nottingham, 2006.

[21] BORTFELDT A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces[J]. European Journal of Operational Research, 2006, 172(3): 814-837.

This work is partially supported by the National Natural Science Foundation of China (51576001).