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

李華

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

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

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

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

（1）

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

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

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

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

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

1多段排樣方式中的概念

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

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

2算法原理及實現

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

2.1求解條帶價值

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

，可由如下公式決定：

，?，.?（2）

2.2生成最優塊。對長寬的塊，設含第種X向帶根，結合2.1節給出的求解X向帶的最大價值方法，根據文獻[9]動態規劃的算法思想，可確定組成X向段的塊中所含條帶的總價值，，遞推公式如下：

（3）

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

2.3塊在段上的最優排樣

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

，，

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

2.5算法步驟

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

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

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

2.6算法的時間復雜度

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

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

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

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