矩形毛坯最優(yōu)層排樣方式的動(dòng)態(tài)規(guī)劃算法
2010-01-01 00:00:00王曉慶李尚芳崔耀東
計(jì)算機(jī)應(yīng)用研究 2010年6期
摘 要:討論矩形毛坯無約束二維剪切排樣問題，提出層排樣方式的動(dòng)態(tài)規(guī)劃算法，使板材所含毛坯總價(jià)值最大。排樣時(shí)使用一組平行的剪切線將板材分割為多個(gè)層，層的長(zhǎng)度等于板材的長(zhǎng)度或?qū)挾龋瑢挾鹊扔谧钭筮呏髅鞯母叨取Ｍㄟ^動(dòng)態(tài)規(guī)劃算法確定所有可能尺寸層的最大價(jià)值和板材中層的最優(yōu)組合。實(shí)驗(yàn)結(jié)果表明，該算法在滿足實(shí)際應(yīng)用要求的同時(shí)，板材利用率和計(jì)算時(shí)間兩方面都較有效。
關(guān)鍵詞:兩維切割; 剪切; 層排樣方式; 動(dòng)態(tài)規(guī)劃
中圖分類號(hào):TP301.6文獻(xiàn)標(biāo)志碼:A
文章編號(hào):1001-3695(2010)06-2040-03
doi:10.3969/j.issn.1001-3695.2010.06.012
Dynamic programming algorithm for generating optimal layer patterns of rectangular blanks
WANG Xiao-qing， LI Shang-fang， CUI Yao-dong
(School of Computer Science Information Engineering， Guangxi Normal University， Guilin Guangxi 541004， China)
Abstract:Focusing on the unconstrained two-dimensional guillotine cutting problem of rectangular blanks， this paper proposed a dynamic programming algorithm to generate layer patterns， making the total value of the blanks included in the plant reach its maximum. The algorithm divided the plate into layers with horizontal cuts. The length of the cuts was equal to the length or width of the plate， the width was the same as the height of the leftmost blank in the layer. The dynamic programming algorithm determined the optimal value of all the layers and the optimal combination of the layers included in the plate. The computational results indicate that the algorithm can satisfy the requirement of actual application and is efficient both in material utilization and in computation time.
Key words:two-dimensional cutting; guillotine cutting; layer pattern; dynamic programming
0 引言
討論矩形毛坯無約束二維剪切排樣問題(unconstrained two-dimensional cutting problem，UTDC)[1]:將板材L×W切成m種毛坯，第i種毛坯尺寸為li×wi，價(jià)值為vi(1≤i≤m)，對(duì)每種毛坯在板材中出現(xiàn)的次數(shù)無約束，排樣的目標(biāo)是使板材所含毛坯的總價(jià)值最大。
UTDC算法的作用是與線性規(guī)劃相結(jié)合，解決二維下料問題(two-dimensional cutting stock problem，TDCS)[2]。在TDCS中，使用板材L×W切出m種毛坯，第i種毛坯尺寸為li×wi，需求量為di，i=1，…，m，排樣的目標(biāo)是滿足對(duì)全部毛坯的需求所需要的板材總面積最小。采用好的UTDC算法，有效提高下料利用率、降低產(chǎn)品成本。
很多文獻(xiàn)對(duì)UTDC進(jìn)行了研究，文獻(xiàn)[3，4]采用動(dòng)態(tài)規(guī)劃算法生成二階段排樣方式如圖1(a)所示，通過兩個(gè)階段將板材切成毛坯，在同一階段內(nèi)剪切線方向一致，相鄰階段剪切線方向垂直，同規(guī)則生成三階段排樣方式。文獻(xiàn)[5]采用遞歸算法生成二段排樣方式如圖1(b)所示，將板材分成兩段，同一段中條帶的長(zhǎng)度和方向均相同，兩段的條帶方向平行或垂直。文獻(xiàn)[6]采用遞歸算法生成簡(jiǎn)單塊排樣方式如圖1(c)所示，將毛坯放入當(dāng)前塊時(shí)，按價(jià)值最大原則選擇水平或豎直分割塊。但企業(yè)下料環(huán)節(jié)影響排樣的因素很多，隨著生產(chǎn)的發(fā)展，這些因素在不斷變化，具有新特性的排樣問題不斷出現(xiàn)。例如，部分企業(yè)采用雙時(shí)段下料工藝，第一時(shí)段利用具有多把平行刀具的自動(dòng)機(jī)床將尺寸較大的板材分割為多個(gè)板塊，第二時(shí)段使用普通設(shè)備將尺寸較小的板塊分割為毛坯。在這種下料工藝中使用兩階段排樣方式，可充分發(fā)揮自動(dòng)機(jī)床的效率(可同時(shí)使用多把刀具)，但板材利用率較低。使用二段、三階段或塊排樣方式，板材利用率可以提高，但有可能不能充分發(fā)揮第一時(shí)段自動(dòng)機(jī)床的效率，從而大大增加第二時(shí)段人工操作的工作量。如圖1(b)和(c)所示的情況，在第一時(shí)段均無法同時(shí)使用多刀具切割。本文提出層排樣方式的動(dòng)態(tài)規(guī)劃算法，在保證板材利用率的同時(shí)，可以充分發(fā)揮自動(dòng)機(jī)床的效率，減少人工操作量，為生產(chǎn)實(shí)踐提供更多的選擇。
1 板材層排樣方式
圖2為兩種層排樣方式，數(shù)字表示毛坯序號(hào)，箭頭所示水平線將板材分成層，層寬度等于左邊主毛坯的高度。圖2(a)所示X向方式，板材水平放置，層的主毛坯分別為5、7和44號(hào)毛坯，層長(zhǎng)度等于板材長(zhǎng)度;圖2(b)所示Y向方式，板材90°旋轉(zhuǎn)放置，層的主毛坯分別為43、25、25、25、25和27號(hào)毛坯，層長(zhǎng)度等于板材寬度。
板材中的矩形區(qū)域分別稱為段或塊，整張板材也看做一個(gè)段。層排樣方式的生成規(guī)則如下[7]:如果當(dāng)前區(qū)域?yàn)槎危x擇毛坯R放在其左下角作為層的主毛坯，用水平線將空白區(qū)域分割成塊A和段B，如圖3所示，如果當(dāng)前區(qū)域?yàn)閴K，選擇毛坯S放在其左下角，按價(jià)值最大的原則選擇按圖4(a)將空白區(qū)域水平分割成塊A1和A2，或按圖4(b)豎直分割成塊A1和A2。
2 算法原理及其實(shí)現(xiàn)
動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解，而分解得到的子問題往往不是相互獨(dú)立的[8]。
2.1 運(yùn)用動(dòng)態(tài)規(guī)劃原理生成塊的價(jià)值
設(shè)板材、毛坯方向可90°旋轉(zhuǎn)，F(xiàn)(x，y)為塊x×y的最大價(jià)值。層排樣方式是一種剪切方式，利用多刀具自動(dòng)機(jī)床將板材分割成層，再用普通設(shè)備將每層分割為毛坯。算法1為生成塊最大價(jià)值的動(dòng)態(tài)規(guī)劃遞歸式。其中，Voi是將毛坯i水平放置在塊x×y的左下角得到的最大價(jià)值，VRi是將毛坯90°旋轉(zhuǎn)放置得到的最大價(jià)值，i=1，…，m。
算法1 生成塊最大價(jià)值F(x，y)的動(dòng)態(tài)規(guī)劃遞歸式塊
1 ifx
2 elseVoi=vi+max{F(x，y-wi)+F(x-li，wi)，F(xiàn)(li，y-wi)+F(x-li，y)}
3 ifx 4 elseVRi=vi+max{F(x，y-li)+F(x-wi，li)，F(xiàn)(wi，y-li)+F(x-wi，y)} 5 F(x，y)=maxi{Voi，VRi} 行2是將毛坯水平放入塊，按價(jià)值最大原則選擇水平(圖4(a))或豎直(圖4(b))分割塊。圖4中，(a)中兩個(gè)空白塊所含毛坯的最大價(jià)值為F(x，y-wi)+F(x-li，wi)，(b)中兩個(gè)空白塊所含毛坯的最大價(jià)值為F(li，y-wi)+F(x-li，y)。行4是將毛坯90°旋轉(zhuǎn)放入塊。 算法2是生成所有可能尺寸塊x×y的最大價(jià)值F(x，y)的動(dòng)態(tài)規(guī)劃算法。其中，τ=mini(li，wi)，所有塊的最大長(zhǎng)度xmax=max(L，W)-τ，最大寬度ymax=maxi(li，wi)。行1是對(duì)所有可能尺寸塊x×y初始化，行4~6判斷如果當(dāng)前塊能將毛坯i水平放入，按價(jià)值最大的原則選擇水平或豎直分割塊，并更新塊的最大價(jià)值F(x，y)。行7~9判斷如果當(dāng)前塊能將毛坯i按90°旋轉(zhuǎn)放入，同理更新塊的最大價(jià)值F(x，y)。 算法2 生成塊最大價(jià)值F(x，y)的動(dòng)態(tài)規(guī)劃算法 1 fory=0 to ymax:let F(x，y)=0 2 forx=τtoxmax 3fory=τtoymax 4 if(x≥liandy≥wi) 5 Voi=vi+max{F(x，y-wi)+F(x-li，wi)，F(xiàn)(li，y-wi)+F(x-li，y)} 6 ifVoi>F(x，y)then letF(x，y)=Voi 7 if(x≥wiandy≥li) 8 VRi=vi+max{F(x，y-li)+F(x-wi，li)，F(xiàn)(wi，y-li)+F(x-wi，y)} 9 if VRi>F(x，y)then let F(x，y)=VRi 2.2 生成層的價(jià)值 若板材水平放置，主毛坯i水平或90°旋轉(zhuǎn)放置會(huì)生成兩個(gè)不同的水平層，如圖5(a)(b)所示，層價(jià)值記為Vjv(1≤j≤2m);若板材90°旋轉(zhuǎn)放置，如圖5(c)(d)所示，層價(jià)值記為Vjh(1≤j≤2m)。下列代碼生成所有層價(jià)值，其中行1～4是當(dāng)1≤j≤m時(shí)，主毛坯i水平放置;行5~8是當(dāng)m+1≤j≤2m時(shí)，主毛坯i按90°旋轉(zhuǎn)放置;hj表示層j的高度。 1for j=1 to m 2i=j;hj=wi; 3Vjv=vi+F(L-li，wi); 4Vjh=vi+F(W-li，wi); 5for j=m+1 to 2m 6i=i-m;hj=li; 7Vjv=vi+F(L-wi，li); 8Vjh=vi+F(W-wi，li) 2.3 生成層排樣方式 運(yùn)用動(dòng)態(tài)規(guī)劃原理求解一維背包問題，確定板材中層的最優(yōu)組合，得到板材所含毛坯的最大價(jià)值。當(dāng)板材水平放置時(shí)， maxV1max=∑2mj=1Vjvyj; ∑2mj=1hjyj≤W(1) 其中:yj是非負(fù)整數(shù)，j表示排樣方式中高度為hj的層出現(xiàn)的次數(shù)，j=1，2，…，2m。 運(yùn)用動(dòng)態(tài)規(guī)劃原理，通過函數(shù)bagVal(vjv，W)求解式(1)，得到層排樣方式所含毛坯的最大價(jià)值V1max。下面為模型(1)的求解過程，V1max=bagVal(Vjv，W)=f(W)。其中f(h)為長(zhǎng)L寬h的板塊中所含毛坯的最大價(jià)值。同理可得到板材90°旋轉(zhuǎn)時(shí)層排樣方式所含毛坯的最大價(jià)值V2max=bagVal(Vjh，L)。由此板材層排樣方式所含毛坯所能達(dá)到的最大價(jià)值V=max(V1max，V2max)。 1 for h=0 to τ:let f(h)=0 2 for h=τ to W 3for j=1 to 2m 4if(h 5let v=Vjv+f(h-hj) 6if v>f(i) then let f(i)=v 7 return f(W) 2.4 板材層排樣方式算法 根據(jù)動(dòng)態(tài)規(guī)劃原理，綜合2.1~2.3節(jié)所述，本文排樣算法步驟如下: a)輸入板材與各毛坯數(shù)據(jù)。 b)通過動(dòng)態(tài)規(guī)劃算法求解所有可能尺寸塊x×y的最大價(jià)值F(x，y)。 c)(a)求解板材水平放置時(shí)，所有層的最大價(jià)值Vjv(1≤j≤2m)。 (b)求解板材90°旋轉(zhuǎn)放置時(shí)，所有層的最大價(jià)值Vjh(1≤j≤2m)。 d)通過動(dòng)態(tài)規(guī)劃原理求解一維背包問題。 (a)得到板材水平放置時(shí)，層排樣方式所含毛坯的最大價(jià)值V1max; (b)得到板材90°旋轉(zhuǎn)放置時(shí)，層排樣方式所含毛坯的最大價(jià)值V2max; (c)得到板材層排樣方式所含毛坯最大價(jià)值V=max(V1max，V2max); e)根據(jù)板材排樣過程反向追蹤，得到層排樣方式中毛坯布局。 3 實(shí)驗(yàn)結(jié)果 用Intel Core 2 CPU，主頻為2.20 GHz、內(nèi)存為1 GB的計(jì)算機(jī)進(jìn)行測(cè)試。 3.1 不同排樣方式的比較 采用文獻(xiàn)[3]中的例題，可以通過http://www.laria.u-picardie.fr/hifi/OR-Benchmark/下載。毛坯的價(jià)值等于其面積。該文獻(xiàn)生成經(jīng)典二階段、三階段排樣方式，這里用V2STAGE、V3STAGE表示文獻(xiàn)中得到的二階段、三階段排樣方式板材所含毛坯的總價(jià)值;V表示本文算法得到的層排樣方式板材所含毛坯的總價(jià)值;T2STAGE、T3STAGE、T分別表示計(jì)算時(shí)間。 表1為對(duì)例題采用不同排樣方式的結(jié)果。分析表1，從板材利用率來看，15道題目中15題均有V≥V2STAGE。其中7題V>V2STAGE，8題V=V2STAGE，說明二階段排樣方式雖然能充分發(fā)揮自動(dòng)機(jī)床的效率，但板材利用率較低。與三階段方式相比較，8題V=V3STAGE，另7題V 表1 不同排樣方式結(jié)果(15個(gè)例題) IDL×MmV3STAGEV2STAGEVT3STAGET2STAGET M1100×156101546815468154681.760.070.14 M2253×294107308072172725327.460.200.15 M3318×473101470541469951469955.660.310.17 M4501×556102739912739912739919.000.320.18 M5750×8061058687957788257793016.600.490.21 B3000×30003290000008997780900000087.827.0311 UU1500×5002524604624604624604617.270.800.20 UU2750×8003059565559325659528849.001.470.34 UU31100×10002510893081082504108711242.461.610.43 UU41000×120038118863811886381188638186.472.790.85 UU51450×130050187825318782531878253352.174.401.60 UU62050×145738295120229512022951202262.864.602.65 UU71465×202450294904329358342947961942.386.073.82 UU82000×200055397482839593523974828444.476.602.70 UU92500×256060611044261084276108427739.718.914.18 平均值(板材利用率、計(jì)算時(shí)間)98.86%98.55%98.71%210.396.991.91 表1說明層排樣方式的動(dòng)態(tài)規(guī)劃算法在更適合實(shí)際應(yīng)用的同時(shí)，板材利用率和計(jì)算時(shí)間兩方面都較有效。兩段排樣式與三階段排樣方式同理，由于文獻(xiàn)[5]中毛坯不能旋轉(zhuǎn)，本文不作比較。 3.2 大規(guī)模數(shù)據(jù)測(cè)試 采用文獻(xiàn)[6]中的10組例題(APT10~APT19)，可通過3.1節(jié)中網(wǎng)站下載。這些例題板材尺寸在1 500~3 000間，每題毛坯種數(shù)m在30~60間，每種毛坯的價(jià)值等于其面積。表2為計(jì)算結(jié)果。其中VSB為文獻(xiàn)[6]通過遞歸算法得到的板材所含毛坯最大價(jià)值，TSB為計(jì)算時(shí)間，V為本文算法得到的板材所含毛坯最大價(jià)值，T為計(jì)算時(shí)間，usage為本文算法得到的板材利用率。 表2 與簡(jiǎn)單塊排樣方式比較 IDL×WmVSBVusage/%TSBT APT102097×1713513591980359178399.98919.334.79 APT112600×1612584190479418859999.93826.4510.25 APT122662×1941355162097515615399.79120.885.00 APT131674×2090543498302349677399.94619.805.12 APT142090×2138424466844446609899.94820.993.05 APT152726×2222496054955605102799.89939.007.07 APT162899×2614537573172756702799.85554.037.84 APT172313×1962594537842453784299.99432.756.54 APT182775×2105315835996583451699.88323.134.42 APT192284×2994356831801683062399.87930.586.37 平均值(板材利用率、計(jì)算時(shí)間)99.95399.91228.696.05 分析表2，從板材利用率來看，雖然只有APT17可以與簡(jiǎn)單塊排樣方式持平，但兩種排樣方式板材平均利用率之差僅為0.04%，且利用率均達(dá)到99.9%左右。簡(jiǎn)單塊排樣方式板材利用率稍高，但如圖1(c)所示情況，在第一時(shí)段可能只有一條剪切線(使用一把刀具)，不能充分發(fā)揮自動(dòng)機(jī)床多刀具的效率。從計(jì)算時(shí)間來看，10組數(shù)據(jù)層排樣方式所需平均計(jì)算時(shí)間明顯減少。圖2中，(a)為例題APT15的X向?qū)优艠臃绞綀D，板材所含毛坯總價(jià)值為6 048 942;(b)為Y向?qū)优艠臃绞綀D，板材所含毛坯總價(jià)值6 054 955。最終選擇Y向?qū)优艠臃绞阶鳛榕艠咏Y(jié)果。 4 結(jié)束語(yǔ) 與其他類型的排樣方式相比，層排樣方式在保證板材利用率的同時(shí)，能夠充分發(fā)揮自動(dòng)機(jī)床的效率，減少人工操作量。本文提出的動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)簡(jiǎn)單，所需計(jì)算時(shí)間短。將本文算法與線性規(guī)劃算法結(jié)合用于解決二維下料問題，為生產(chǎn)實(shí)踐提供更多的選擇，可作為本文的后續(xù)研究?jī)?nèi)容。 參考文獻(xiàn): [1]崔耀東，黃健民，張顯全.矩形毛坯無約束二維剪切排樣的遞歸算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18(7):948-951. [2]崔耀東.計(jì)算機(jī)排樣及應(yīng)用[M].北京:機(jī)械工業(yè)出版社，2004:90-92. [3]HIFI M. Exact algorithms for large-scale unconstrained two and three staged cutting problems [J].Computational Optimization and Applications，2001，18(1):63-88. [4]CUI Yao-dong， WANG Z， LI J. Exact and heuristic algorithms for staged cutting problems [J]. Journal of Engineering Manufacture，2005，219(B2):201-208. [5]CUI Yao-dong， HE Dong-li， SONG Xiao-xia. Generating optimal two-section cutting patterns for rectangular blanks[J]. Computers and Operations Research，2006，33:1505-1520. [6]CUI Yao-dong. Simple block patterns for the two-dimensional cutting problem[J]. Mathematical and Computer Modelling，2007，45(7-8):943-953. [7]何冬黎，崔耀東.一種卷材填充分層遞歸排樣的優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2008，28(6):1632-1634. [8]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].3版.北京:電子工業(yè)出版社，2007:48-49.
