X-向多段排樣方式及其生成算法

李華

摘要：為解決大規(guī)模矩形毛坯無約束的二維剪切排樣問題，提出多段排樣方式及其生成算法。排樣用一組剪切線將每段切分成一系列的塊，每個塊由一組水平方向的同質(zhì)條帶構(gòu)成。實驗結(jié)果表明，該算法能在合理的計算時間內(nèi)取得較好的優(yōu)化結(jié)果。

關(guān)鍵詞：無約束二維切割;下料;多段排樣方式;背包問題

引言：矩形件優(yōu)化排樣問題是指將一組矩形件互不重疊的排放在有限的區(qū)域內(nèi)，并實現(xiàn)資源優(yōu)化利用的布局問題，其研究成果主要應(yīng)用在板材、玻璃加工業(yè)、金屬制品業(yè)等領(lǐng)域。最大限度的提高材料利用率、節(jié)約生產(chǎn)成本，簡化切割工藝、縮短計算時間、提高企業(yè)效率成為增強(qiáng)企業(yè)競爭力的關(guān)鍵。因此，矩形件的優(yōu)化排樣問題一直是國內(nèi)外眾多學(xué)者研究的熱點(diǎn)。

本文討論矩形毛坯無約束的二維剪切排樣（Unconstrained two-dimensional cutting，UTDC）問題：采用剪切方式，將板材（長寬）切成種毛坯，第種毛坯的尺寸為，價值為，對每種毛坯在板材出現(xiàn)的次數(shù)無約束，排樣目標(biāo)是使得板材所含毛坯的總價值最大。令可行的排樣方式中含第種毛坯個，為自然數(shù)的集合，則UTDC的數(shù)學(xué)模型為：

（1）

St. ;;滿足一定的切割工藝的要求。

在生產(chǎn)實踐中，經(jīng)常將UTDC算法和線性規(guī)劃算法相結(jié)合以求解二維下料問題（two-dimensional cutting stock problem，TDCSP）：使用庫存板材剪切出種矩形小毛坯，第種毛坯的尺寸為，需求量為，，要求確定下料方案，在滿足全部毛坯需求的前提下，使得消耗的板材總面積最小。在求解下料方案的過程中，需要反復(fù)調(diào)用UTDC算法。因此，要求UTDC算法能在合理的計算時間內(nèi)給出高質(zhì)量的解。

目前研究的UTDC算法大致可分為三類：第一類是生成普通排樣方式的精確算法[1-2]。第二類是生成普通排樣方式的近似算法[3-4]，該算法由于其收斂性未知，無法保證解的質(zhì)量。第三類是生成具有明確幾何性質(zhì)的排樣方式算法，如兩段[5-6]、T形[7]、兩階段[8-9]、3階段[9-10]、層排樣[11]、同質(zhì)三塊[12]等排樣算法，這類排樣算法的利用率可能略低，但其切割工藝簡單，得到廣泛的應(yīng)用。

本文研究特定類型的排樣方式，提出多段排樣方式及其生成算法，即在文獻(xiàn)[12]的基礎(chǔ)上，將輔助分界線由一條擴(kuò)展到多條，將板材切成若干塊;且在切割工藝方面，排樣方式還可應(yīng)用于求解生產(chǎn)中滾剪下料問題，簡化切割過程，減少人工工作量。

本文詳細(xì)介紹了排樣方式及其生成算法，并通過兩組實驗測題驗證了算法的有效性，實驗結(jié)果的將在第3節(jié)詳細(xì)列出。

1多段排樣方式中的概念

1.1同質(zhì)條帶。條帶由若干個互不重疊、水平（X向）或豎直（Y向）排列的毛坯組成。按照條帶所含毛坯類型，可將其分為單毛坯條帶和多毛坯條帶。單毛坯條帶又稱同質(zhì)條帶，其中僅含尺寸和方向均相同的毛坯。多毛坯條帶又稱普通條帶，其中含多種不同毛坯。本文采用X向同質(zhì)條帶，與采用普通條帶相比利用率雖略低，但切割工藝較為簡單。

1.2塊。塊是指由長度和方向均相同的X向同質(zhì)條帶拼接而成的板材的矩形區(qū)域，如圖2所示，毛坯中的數(shù)字指明毛坯的類型。通過一系列的剪切的過程可將塊切分成若干條X向同質(zhì)條帶，每次切下一根X向條帶，連續(xù)被切下的兩根條帶相互平行。

2算法原理及實現(xiàn)

設(shè)板材和毛坯的尺寸均為整數(shù)，毛坯的方向固定?，F(xiàn)只介紹生成X-向最優(yōu)排樣的方法，主要包含以下幾個步驟：（1）求解X向帶最大價值。（2）確定不同尺寸的最優(yōu)塊排樣。（3）確定塊在段上的最優(yōu)排樣。

2.1求解條帶價值

記條帶的寬度向量為，，對矩形毛坯，為第種毛坯的單價，為全部毛坯的最小寬度，即，條帶長度為時的價值向量為

，可由如下公式?jīng)Q定：

，?，.?（2）

2.2生成最優(yōu)塊。對長寬的塊，設(shè)含第種X向帶根，結(jié)合2.1節(jié)給出的求解X向帶的最大價值方法，根據(jù)文獻(xiàn)[9]動態(tài)規(guī)劃的算法思想，可確定組成X向段的塊中所含條帶的總價值，，遞推公式如下：

（3）

式（3）為最大化一定尺寸塊價值的背包問題，可采用文獻(xiàn)[13]中的動態(tài)規(guī)劃算法求解。為減少計算時間，在求解過程中利用如下技術(shù)減少塊中考慮拼接條帶的數(shù)目：（1）將塊排樣初始化為塊和塊中較好者。（2）若，可令，因為，當(dāng)出現(xiàn)在塊中時，可用較短的條帶代替它，而不影響解的質(zhì)量。

2.3塊在段上的最優(yōu)排樣

根據(jù)2.2節(jié)段的定義可知：X向段由一系列水平排列高度均相同的塊構(gòu)成，記為X向段最大價值，，則有如下公式：??（4）

，，

上述模型是典型的背包問題，可利用文獻(xiàn)[13]中的動態(tài)規(guī)劃算法求解。其中，背包長度為，需要考慮種物品，第個物品的長度為（對應(yīng)于尺寸為的塊），該物品個數(shù)為。

2.5算法步驟

步1：按2.1節(jié)式（2）確定各種尺寸的條帶的價值。

步2：按2.2節(jié)式（3）確定各種尺寸的塊的價值。

步3：求解2.3節(jié)式（4），得到各種尺寸的段的價值。

2.6算法的時間復(fù)雜度

1）式（2）確定條帶價值的復(fù)雜度為。

2）式（3）確定塊價值的復(fù)雜度為。

3）式（4）確定高度一定段價值的復(fù)雜度為。

由于，綜上所述，X-向排樣算法的時間復(fù)雜度為。