李 華， 崔耀東， 王嚴欣

(廣西大學計算機與電子信息學院，廣西 南寧 530004)

雙排多段排樣方式及其生成算法

李 華， 崔耀東， 王嚴欣

(廣西大學計算機與電子信息學院，廣西 南寧 530004)

為解決大規(guī)模矩形毛坯無約束的二維剪切排樣問題，提出雙排多段排樣方式及其生成算法。排樣時采用一條剪切線將板材切分為兩段，用一組剪切線將每段切分成一系列的塊，每個塊由一組水平方向的同質(zhì)條帶構成。采用枚舉法確定兩段分界線的最優(yōu)位置，通過求解背包模型確定所有可能尺寸的塊的最大價值和塊在段中的最優(yōu)布局。利用文獻中的2組基準測題對所述算法進行測試，實驗結果表明，該算法能在合理的計算時間內(nèi)取得較好的優(yōu)化結果。

無約束二維切割；下料；雙排多段排樣方式；背包問題

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

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

其中：zi∈N；i= 1,…,m；P滿足一定的切割工藝的要求。

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

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

文獻[5]和[12]均采用遞歸算法分別生成最優(yōu)兩段布局方式和同質(zhì)三塊布局方式。以上兩種布局方式，都是先將板材切分成兩段，然后再在段上進行條帶的布局排樣。另外，在文獻[5]的基礎上，對文獻[12]布局方式添加一條垂直于段分界線的輔助分界線，將板材切分成任意三塊。分析以上兩種布局方式的幾何性質(zhì)可以得出：兩段布局方式?同質(zhì)三塊布局方式。故同質(zhì)三塊布局方式理論上的排樣價值優(yōu)于兩段布局方式的價值。

本文研究特定類型的排樣方式，對文獻[12]進行擴展提出雙排多段排樣方式(double-rows and multi segment，DMS)及其生成算法，即在文獻[12]的基礎上，將輔助分界線由一條擴展到多條，將板材切成若干塊。故理論上DMS排樣價值優(yōu)于三塊布局方式的價值是確定的；在切割工藝方面，DMS排樣方式還可應用于求解生產(chǎn)中滾剪下料問題，簡化切割過程，減少人工工作量。

本文詳細介紹了 DMS排樣方式及其生成算法，并通過兩組實驗測題驗證了算法的有效性，實驗結果將在第 3節(jié)詳細列出。下文中的敘述表明DMS算法優(yōu)于經(jīng)典兩段、啟發(fā)式TABU500算法和同質(zhì)三塊排樣算法，且計算時間合理。

1 雙排多段排樣方式中的概念

在DMS排樣方式中，用一條剪切線將板材分為兩段，采用若干條輔助分界線將段劃分成一系列的塊，每個塊僅含方向固定的同質(zhì)條帶。下面分別介紹相關概念。

1.1 同質(zhì)條帶

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

圖1 條帶

1.2 塊

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

圖2 塊

1.3 段

一個段由一系列的塊組合而成，段長度與板材長度或?qū)挾认嗟?。若一系列塊從左到右按水平方向排列，則稱X向段，如圖3 (a)所示；若一系列塊自頂向下按豎直方向排列，則稱Y向段，如圖3 (b)所示。圖3中，箭頭指示相鄰塊之間分割線的位置。

1.4 DMS排樣方式

DMS排樣方式由兩排塊組成，可分2個階段將板材切分成一系列塊：①將板材切分成兩段；②將每段切分成若干個塊。圖4為DMS排樣的兩種類型：若兩段之間分割線的方向為 X向，稱為X-DMS排樣，如圖4(a)所示，水平箭頭指示上下兩段分割線的位置，豎直箭頭指示相鄰塊之間剪切線的位置；若兩段之間分割線的方向為 Y向，稱為Y-DMS排樣，如圖4(b)所示，豎直箭頭指示兩段分割線的位置，水平箭頭指示相鄰塊之間剪切線的位置。圖4(a)與圖4(b)均包含5個塊。

圖3 段

圖4 DMS排樣方式

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

設板材L×W和毛坯的尺寸均為整數(shù)，毛坯的方向固定?，F(xiàn)只介紹生成X-DMS最優(yōu)排樣的方法，主要包含以下4個步驟：①求解X向帶最大價值；②確定不同尺寸的最優(yōu)塊排樣；③確定塊在段上的最優(yōu)排樣；④生成DMS的最優(yōu)排樣方式。如果同時交換板材的長度與寬度、毛坯的長度與寬度，然后調(diào)用X-DMS排樣方式算法，就可以生成Y-DMS排樣方式。

2.1 求解條帶價值

記條帶的寬度向量為 W =［w1,w2,…,wm］，i=1,…,m，對矩形毛坯li×wi，ci為第i種毛坯的單價，wmin為全部毛坯的最小寬度，即，條帶長度為x時的價值向量為，可由如下公式?jīng)Q定：

2.2 生成最優(yōu)塊

對長為x寬為y的塊，設含第j種X向帶zj根，結合2.1節(jié)給出的求解X向帶的最大價值方法，根據(jù)文獻[9]動態(tài)規(guī)劃的算法思想，可確定組成X向段的塊中所含條帶的總價值 FX(x,y)，x≤L,y≤W，遞推公式如下：

式(3)為最大化一定尺寸塊價值的背包問題，可采用文獻[13]中的動態(tài)規(guī)劃算法求解。為減少計算時間，在求解過程中利用如下技術減少塊中考慮拼接條帶的數(shù)目：

(1) 將塊x×y排樣初始化為塊 x×(y-1)和塊(x-1)×y中較好者。

(2) 若x/wj≤(x-1)/wj，可令zj= 0，因為，當vj(x,wj)出現(xiàn)在塊中時，可用較短的條帶代替，而不影響解的質(zhì)量。

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

根據(jù)1.3節(jié)段的定義可知：X向段由一系列水平排列高度均相同的塊構成，記 B(L,Y)為X向段L×Y最大價值，Y=1,…,W，則有如下公式：

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

2.4 最優(yōu)DMS方式

設最優(yōu)X-DMS排樣方式的價值為VX-DMS，對應水平分割線的位置為Ymax，則：

2.5 生成DMS方式算法步驟

步驟1.按式(2)確定各種尺寸的條帶的價值。

步驟2.按式(3)確定各種尺寸的塊的價值。

步驟3.求解式(4)，得到各種尺寸的段的價值。

步驟4.按式(5)確定X-DMS排樣方式的價值。

步驟5.交換板材的長與寬，交換每種毛坯的長與寬，調(diào)用步驟1～4確定Y-DMS排樣方式的價值。

步驟6.選取X-DMS和Y-DMS兩個排樣方式中價值較大者作為最優(yōu)DMS排樣方式。

2.6 算法的時間復雜度

(1) 式(2)確定條帶價值的復雜度為 O(mL)。

(2) 式(3)確定塊價值FX(x,y)的復雜度為O(mWL)。

(3) 式(4)確定高度一定段價值 B(L,Y)的復雜度為 O(L2W)。

(4) 式(5)確定最優(yōu) X-DMS排樣價值 Vx-DMS的復雜度為 O(W)。

由于m＜＜L，綜上所述，X-DMS排樣算法的時間復雜度為O(L2W)，同理可得Y-DMS排樣算法的時間復雜度為O(LW2)，則DMS算法總的時間復雜度為O(LW(L+W))。

3 實驗計算結果

實驗所使用計算機為 Pentium(R) Dual-Core CPU，主頻3.0 GHz，內(nèi)存2.0 GB。采用文獻中的兩組基準測題，將本文DMS算法與多種文獻算法相比較。

3.1 第一組基準測題

將 DMS算法與同質(zhì)條帶兩段布局算法[5]和同質(zhì)條帶三塊布局算法[12]相比較。三者均采用同質(zhì)條帶。采用文獻[5]中表4詳細描述的6個例題為實驗數(shù)據(jù)，其中板材尺寸3000×1500(單位均為mm)，每題 30種毛坯，毛坯的單價和面積相等。計算結果如表 1所示，其中 ID表示題號， VT-2SECTION、VT-3BLOCK和VDMS分別為文獻[5]、文獻[12]和DMS3種算法所得解值，每題的最好解(解值最大者)以黑體表示。所獲得的最好解的數(shù)量，對于DMS算法為6個，文獻[5]算法為1個，文獻[12]算法為2個，說明DMS算法對于提高解的質(zhì)量最為有效。usage 為 DMS算法所得各題的材料利用率，平均值為99.70%。DMS算法平均每題的計算時間為0.24 s，在實際應用中合理。圖5為本文算法生成的測題1的排樣方式圖。

表1 第一組基準測題的實驗結果

圖5 測題1的排樣方式圖

3.2 第二組基準測題

將DMS算法分別與文獻[3]的TABU500和文獻[12]的算法相比較。采用文獻[3]中表 10報道的20個例題，其中，每題毛坯種數(shù)在區(qū)間[10，60]中，板材長度和寬度在[1500，3000]中，毛坯長度在[0.05 L，0.4L]中，毛坯寬度在[0.05W，0.4W]中。前10題(APT10-APT19)中，毛坯的價值和面積相等；后10題(APT20-APT29)中，毛坯的價值和面積不相等。具體計算結果如表2所示，其中ID為例題標識，VTABU500、VT-3BLOCK和VDMS分別表示、文獻[3]算法、文獻[12]算法和DMS算法的解值，每題的最好解以黑體表示。所得最好解的數(shù)量，對于 DMS算法為19個，文獻[3]算法為5個，文獻[12]算法為7個，DMS的求解結果均優(yōu)于兩個對比算法，說明DMS算法對于提高解的質(zhì)量最為有效。DMS算法平均每題的計算時間為0.39 s，能滿足應用需求。圖6給出了DMS算法生成的測題APT16和APT22的排樣方式圖。

表2 第二組基準測題的實驗結果

圖6 測題APT16和APT22的排樣方式圖

4 結 束 語

本文提出一種新型特定排樣方式——DMS排樣方式，并采用DMS算法生成此種排樣方式，通過文獻測題驗證了算法的有效性，證明本文算法總體優(yōu)于經(jīng)典兩段、TABU500算法和同質(zhì)三塊排樣算法。另外，利用該排樣方式的特點，下料過程中可充分發(fā)揮滾剪機的效率，減少人工操作量。排樣過程中采用相關技術減少優(yōu)化時的搜索空間，在保證有效地提高解的質(zhì)量前提下，能夠滿足實際應用對計算時間和切割工藝的要求。將本文DMS算法與線性規(guī)劃算法相結合，設計求解二維下料問題的算法，可以作為后續(xù)研究的內(nèi)容。

[1] Cui Y D, Zhang X Q. Two-stage general block patterns for the two-dimensional cutting problem [J]. Computers & Operations Research, 2007, 34(10): 2882-2893.

[2] Russo M, Sforza A, Sterle C. An exact dynam ic programm ing algorithm for large-scale unconstrained two-dimensional guillotine cutting problems [J]. Computers & Operations Research, 2014, 50: 97-114.

[3] A lvarez-Valdés R, Parajón A, Tamarit J M. A tabu search algorithm for large-scale guillotine (un) constrained two-dimensional cutting problems [J]. Computers & Operations Research, 2002, 29(7): 925-947.

[4] 李 波, 王 石, 施松新, 等. 基于啟發(fā)式動態(tài)分解算法的矩形件優(yōu)化排樣[J]. 計算機應用, 2013, 33(7): 1908-1911.

[5] Cui Y D, He D L, Song X X. Generating optimal two-section cutting patterns for rectangular blanks [J]. Computers & Operations Research, 2006, 33(6): 1505-1520.

[6] Cui Y D. Heuristic for two-dimensional homogeneous two-segment cutting patterns [J]. Engineering Optimization, 2013, 45(1): 89-105.

[7] 崔耀東. 生成矩形毛坯最優(yōu)T形排樣方式的遞歸算法[J].計算機輔助設計與圖形學學報, 2006, 18(1): 125-127.

[8] Smola A J, Sch?lkopf B. A tutorial on support vector regression [J]. Statistics and Computing, 2004, 14(3): 199-222.

[9] Cui Y, Huang L, He D. Generating optimal multiple-segment cutting patterns for rectangular blanks [J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2004, 218(11): 1483-1490.

[10] Cui Y D. A new dynam ic programm ing procedure for three-staged cutting patterns [J]. Journal of Global Optimization, 2013, 55(2): 349-357.

[11] 王曉慶, 李尚芳, 崔耀東. 矩形毛坯最優(yōu)層排樣方式的動態(tài)規(guī)劃算法[J]. 計算機應用研究, 2010, 27(6): 2040-2067.

[12] 潘衛(wèi)平, 陳秋蓮, 崔耀東, 等. 基于勻質(zhì)條帶的矩形件最優(yōu)三塊布局算法[J]. 圖學學報, 2015, 36(1): 7-11.

[13] Kellerer H, Pferschy U, Pisinger D. Knapsack problems (2004) [M]. Berlin: Springer, 2003, 130-131.

An Algorithm for Generating Patterns of Double-Rows and Multi Segments

Li Hua, Cui Yaodong, Wang Yanxin

(College of Computer and Electronic Information, Guangxi University, Nanning Guangxi 530004, China)

To solve large scale unconstrained two-dimensional guillotine-cutting problem of rectangular items, an algorithm for generating the patterns of double-rows and multi segments is proposed, where the plate is divided into two segments by a cut, each of which is then divided into a series of blocks with a set of cuts, and each block contains a group of horizontal strips. The optimal position of the cut that divides the plate into two segments is determ ined through enumeration. Knapsack problems are solved to obtain the maximum values of all possible blocks and the block layouts on the segments. The algorithm is tested on two groups of benchmark problems in the literature. The computational results indicate that the algorithm can obtain better optimization results in a reasonable computation time.

unconstrained two-dimensional cutting; stock packing; double-rows and multi-segments patterns; knapsack problem

TH 164；TP 301.6

10.11996/JG.j.2095-302X.2016030285

A

2095-302X(2016)03-0285-05

2015-07-07；定稿日期：2016-01-18

國家自然科學基金項目(61363026，71371058)；廣西自然科學基金項目(2014GXNSFAA118357)

李 華(1986–)，女，山東濰坊人，碩士研究生。主要研究方向為智能系統(tǒng)與智能CAD。E-mail：lh401281894@126.com

崔耀東(1957–)，男，河南林州人，教授，博士。主要研究方向為智能系統(tǒng)與智能CAD。E-mail：ydcui@263.net