矩形毛坯最優層排樣方式的動態規劃算法
2010-01-01 00:00:00王曉慶李尚芳崔耀東
計算機應用研究 2010年6期
摘 要:討論矩形毛坯無約束二維剪切排樣問題，提出層排樣方式的動態規劃算法，使板材所含毛坯總價值最大。排樣時使用一組平行的剪切線將板材分割為多個層，層的長度等于板材的長度或寬度，寬度等于最左邊主毛坯的高度。通過動態規劃算法確定所有可能尺寸層的最大價值和板材中層的最優組合。實驗結果表明，該算法在滿足實際應用要求的同時，板材利用率和計算時間兩方面都較有效。
關鍵詞:兩維切割; 剪切; 層排樣方式; 動態規劃
中圖分類號:TP301.6文獻標志碼:A
文章編號: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，價值為vi(1≤i≤m)，對每種毛坯在板材中出現的次數無約束，排樣的目標是使板材所含毛坯的總價值最大。
UTDC算法的作用是與線性規劃相結合，解決二維下料問題(two-dimensional cutting stock problem，TDCS)[2]。在TDCS中，使用板材L×W切出m種毛坯，第i種毛坯尺寸為li×wi，需求量為di，i=1，…，m，排樣的目標是滿足對全部毛坯的需求所需要的板材總面積最小。采用好的UTDC算法，有效提高下料利用率、降低產品成本。
很多文獻對UTDC進行了研究，文獻[3，4]采用動態規劃算法生成二階段排樣方式如圖1(a)所示，通過兩個階段將板材切成毛坯，在同一階段內剪切線方向一致，相鄰階段剪切線方向垂直，同規則生成三階段排樣方式。文獻[5]采用遞歸算法生成二段排樣方式如圖1(b)所示，將板材分成兩段，同一段中條帶的長度和方向均相同，兩段的條帶方向平行或垂直。文獻[6]采用遞歸算法生成簡單塊排樣方式如圖1(c)所示，將毛坯放入當前塊時，按價值最大原則選擇水平或豎直分割塊。但企業下料環節影響排樣的因素很多，隨著生產的發展，這些因素在不斷變化，具有新特性的排樣問題不斷出現。例如，部分企業采用雙時段下料工藝，第一時段利用具有多把平行刀具的自動機床將尺寸較大的板材分割為多個板塊，第二時段使用普通設備將尺寸較小的板塊分割為毛坯。在這種下料工藝中使用兩階段排樣方式，可充分發揮自動機床的效率(可同時使用多把刀具)，但板材利用率較低。使用二段、三階段或塊排樣方式，板材利用率可以提高，但有可能不能充分發揮第一時段自動機床的效率，從而大大增加第二時段人工操作的工作量。如圖1(b)和(c)所示的情況，在第一時段均無法同時使用多刀具切割。本文提出層排樣方式的動態規劃算法，在保證板材利用率的同時，可以充分發揮自動機床的效率，減少人工操作量，為生產實踐提供更多的選擇。
1 板材層排樣方式
圖2為兩種層排樣方式，數字表示毛坯序號，箭頭所示水平線將板材分成層，層寬度等于左邊主毛坯的高度。圖2(a)所示X向方式，板材水平放置，層的主毛坯分別為5、7和44號毛坯，層長度等于板材長度;圖2(b)所示Y向方式，板材90°旋轉放置，層的主毛坯分別為43、25、25、25、25和27號毛坯，層長度等于板材寬度。
板材中的矩形區域分別稱為段或塊，整張板材也看做一個段。層排樣方式的生成規則如下[7]:如果當前區域為段，選擇毛坯R放在其左下角作為層的主毛坯，用水平線將空白區域分割成塊A和段B，如圖3所示，如果當前區域為塊，選擇毛坯S放在其左下角，按價值最大的原則選擇按圖4(a)將空白區域水平分割成塊A1和A2，或按圖4(b)豎直分割成塊A1和A2。
2 算法原理及其實現
動態規劃算法的基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解，而分解得到的子問題往往不是相互獨立的[8]。
2.1 運用動態規劃原理生成塊的價值
設板材、毛坯方向可90°旋轉，F(x，y)為塊x×y的最大價值。層排樣方式是一種剪切方式，利用多刀具自動機床將板材分割成層，再用普通設備將每層分割為毛坯。算法1為生成塊最大價值的動態規劃遞歸式。其中，Voi是將毛坯i水平放置在塊x×y的左下角得到的最大價值，VRi是將毛坯90°旋轉放置得到的最大價值，i=1，…，m。
算法1 生成塊最大價值F(x，y)的動態規劃遞歸式塊
1 ifx
2 elseVoi=vi+max{F(x，y-wi)+F(x-li，wi)，F(li，y-wi)+F(x-li，y)}
3 ifx 4 elseVRi=vi+max{F(x，y-li)+F(x-wi，li)，F(wi，y-li)+F(x-wi，y)} 5 F(x，y)=maxi{Voi，VRi} 行2是將毛坯水平放入塊，按價值最大原則選擇水平(圖4(a))或豎直(圖4(b))分割塊。圖4中，(a)中兩個空白塊所含毛坯的最大價值為F(x，y-wi)+F(x-li，wi)，(b)中兩個空白塊所含毛坯的最大價值為F(li，y-wi)+F(x-li，y)。行4是將毛坯90°旋轉放入塊。 算法2是生成所有可能尺寸塊x×y的最大價值F(x，y)的動態規劃算法。其中，τ=mini(li，wi)，所有塊的最大長度xmax=max(L，W)-τ，最大寬度ymax=maxi(li，wi)。行1是對所有可能尺寸塊x×y初始化，行4~6判斷如果當前塊能將毛坯i水平放入，按價值最大的原則選擇水平或豎直分割塊，并更新塊的最大價值F(x，y)。行7~9判斷如果當前塊能將毛坯i按90°旋轉放入，同理更新塊的最大價值F(x，y)。 算法2 生成塊最大價值F(x，y)的動態規劃算法 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(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(wi，y-li)+F(x-wi，y)} 9 if VRi>F(x，y)then let F(x，y)=VRi 2.2 生成層的價值 若板材水平放置，主毛坯i水平或90°旋轉放置會生成兩個不同的水平層，如圖5(a)(b)所示，層價值記為Vjv(1≤j≤2m);若板材90°旋轉放置，如圖5(c)(d)所示，層價值記為Vjh(1≤j≤2m)。下列代碼生成所有層價值，其中行1～4是當1≤j≤m時，主毛坯i水平放置;行5~8是當m+1≤j≤2m時，主毛坯i按90°旋轉放置;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 生成層排樣方式 運用動態規劃原理求解一維背包問題，確定板材中層的最優組合，得到板材所含毛坯的最大價值。當板材水平放置時， maxV1max=∑2mj=1Vjvyj; ∑2mj=1hjyj≤W(1) 其中:yj是非負整數，j表示排樣方式中高度為hj的層出現的次數，j=1，2，…，2m。 運用動態規劃原理，通過函數bagVal(vjv，W)求解式(1)，得到層排樣方式所含毛坯的最大價值V1max。下面為模型(1)的求解過程，V1max=bagVal(Vjv，W)=f(W)。其中f(h)為長L寬h的板塊中所含毛坯的最大價值。同理可得到板材90°旋轉時層排樣方式所含毛坯的最大價值V2max=bagVal(Vjh，L)。由此板材層排樣方式所含毛坯所能達到的最大價值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 板材層排樣方式算法 根據動態規劃原理，綜合2.1~2.3節所述，本文排樣算法步驟如下: a)輸入板材與各毛坯數據。 b)通過動態規劃算法求解所有可能尺寸塊x×y的最大價值F(x，y)。 c)(a)求解板材水平放置時，所有層的最大價值Vjv(1≤j≤2m)。 (b)求解板材90°旋轉放置時，所有層的最大價值Vjh(1≤j≤2m)。 d)通過動態規劃原理求解一維背包問題。 (a)得到板材水平放置時，層排樣方式所含毛坯的最大價值V1max; (b)得到板材90°旋轉放置時，層排樣方式所含毛坯的最大價值V2max; (c)得到板材層排樣方式所含毛坯最大價值V=max(V1max，V2max); e)根據板材排樣過程反向追蹤，得到層排樣方式中毛坯布局。 3 實驗結果 用Intel Core 2 CPU，主頻為2.20 GHz、內存為1 GB的計算機進行測試。 3.1 不同排樣方式的比較 采用文獻[3]中的例題，可以通過http://www.laria.u-picardie.fr/hifi/OR-Benchmark/下載。毛坯的價值等于其面積。該文獻生成經典二階段、三階段排樣方式，這里用V2STAGE、V3STAGE表示文獻中得到的二階段、三階段排樣方式板材所含毛坯的總價值;V表示本文算法得到的層排樣方式板材所含毛坯的總價值;T2STAGE、T3STAGE、T分別表示計算時間。 表1為對例題采用不同排樣方式的結果。分析表1，從板材利用率來看，15道題目中15題均有V≥V2STAGE。其中7題V>V2STAGE，8題V=V2STAGE，說明二階段排樣方式雖然能充分發揮自動機床的效率，但板材利用率較低。與三階段方式相比較，8題V=V3STAGE，另7題V 表1 不同排樣方式結果(15個例題) 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 平均值(板材利用率、計算時間)98.86%98.55%98.71%210.396.991.91 表1說明層排樣方式的動態規劃算法在更適合實際應用的同時，板材利用率和計算時間兩方面都較有效。兩段排樣式與三階段排樣方式同理，由于文獻[5]中毛坯不能旋轉，本文不作比較。 3.2 大規模數據測試 采用文獻[6]中的10組例題(APT10~APT19)，可通過3.1節中網站下載。這些例題板材尺寸在1 500~3 000間，每題毛坯種數m在30~60間，每種毛坯的價值等于其面積。表2為計算結果。其中VSB為文獻[6]通過遞歸算法得到的板材所含毛坯最大價值，TSB為計算時間，V為本文算法得到的板材所含毛坯最大價值，T為計算時間，usage為本文算法得到的板材利用率。 表2 與簡單塊排樣方式比較 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 平均值(板材利用率、計算時間)99.95399.91228.696.05 分析表2，從板材利用率來看，雖然只有APT17可以與簡單塊排樣方式持平，但兩種排樣方式板材平均利用率之差僅為0.04%，且利用率均達到99.9%左右。簡單塊排樣方式板材利用率稍高，但如圖1(c)所示情況，在第一時段可能只有一條剪切線(使用一把刀具)，不能充分發揮自動機床多刀具的效率。從計算時間來看，10組數據層排樣方式所需平均計算時間明顯減少。圖2中，(a)為例題APT15的X向層排樣方式圖，板材所含毛坯總價值為6 048 942;(b)為Y向層排樣方式圖，板材所含毛坯總價值6 054 955。最終選擇Y向層排樣方式作為排樣結果。 4 結束語 與其他類型的排樣方式相比，層排樣方式在保證板材利用率的同時，能夠充分發揮自動機床的效率，減少人工操作量。本文提出的動態規劃算法設計簡單，所需計算時間短。將本文算法與線性規劃算法結合用于解決二維下料問題，為生產實踐提供更多的選擇，可作為本文的后續研究內容。 參考文獻: [1]崔耀東，黃健民，張顯全.矩形毛坯無約束二維剪切排樣的遞歸算法[J].計算機輔助設計與圖形學學報，2006，18(7):948-951. [2]崔耀東.計算機排樣及應用[M].北京:機械工業出版社，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]何冬黎，崔耀東.一種卷材填充分層遞歸排樣的優化算法[J].計算機應用，2008，28(6):1632-1634. [8]王曉東.計算機算法設計與分析[M].3版.北京:電子工業出版社，2007:48-49.
