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

李 華， 崔耀東， 王嚴(yán)欣

(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

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

李 華， 崔耀東， 王嚴(yán)欣

(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

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

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

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

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

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

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

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

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

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

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

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

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

1.1 同質(zhì)條帶

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

圖1 條帶

1.2 塊

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

圖2 塊

1.3 段

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

1.4 DMS排樣方式

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

圖3 段

圖4 DMS排樣方式

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

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

2.1 求解條帶價(jià)值

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

2.2 生成最優(yōu)塊

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

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

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

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

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

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

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

2.4 最優(yōu)DMS方式

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

2.5 生成DMS方式算法步驟

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)計(jì)算結(jié)果

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

3.1 第一組基準(zhǔn)測(cè)題

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

表1 第一組基準(zhǔn)測(cè)題的實(shí)驗(yàn)結(jié)果

圖5 測(cè)題1的排樣方式圖

3.2 第二組基準(zhǔn)測(cè)題

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

表2 第二組基準(zhǔn)測(cè)題的實(shí)驗(yàn)結(jié)果

圖6 測(cè)題APT16和APT22的排樣方式圖

4 結(jié) 束 語(yǔ)

本文提出一種新型特定排樣方式——DMS排樣方式，并采用DMS算法生成此種排樣方式，通過(guò)文獻(xiàn)測(cè)題驗(yàn)證了算法的有效性，證明本文算法總體優(yōu)于經(jīng)典兩段、TABU500算法和同質(zhì)三塊排樣算法。另外，利用該排樣方式的特點(diǎn)，下料過(guò)程中可充分發(fā)揮滾剪機(jī)的效率，減少人工操作量。排樣過(guò)程中采用相關(guān)技術(shù)減少優(yōu)化時(shí)的搜索空間，在保證有效地提高解的質(zhì)量前提下，能夠滿足實(shí)際應(yīng)用對(duì)計(jì)算時(shí)間和切割工藝的要求。將本文DMS算法與線性規(guī)劃算法相結(jié)合，設(shè)計(jì)求解二維下料問題的算法，可以作為后續(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ā)式動(dòng)態(tài)分解算法的矩形件優(yōu)化排樣[J]. 計(jì)算機(jī)應(yīng)用, 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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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)層排樣方式的動(dòng)態(tài)規(guī)劃算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2010, 27(6): 2040-2067.

[12] 潘衛(wèi)平, 陳秋蓮, 崔耀東, 等. 基于勻質(zhì)條帶的矩形件最優(yōu)三塊布局算法[J]. 圖學(xué)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金項(xiàng)目(61363026，71371058)；廣西自然科學(xué)基金項(xiàng)目(2014GXNSFAA118357)

李 華(1986–)，女，山東濰坊人，碩士研究生。主要研究方向?yàn)橹悄芟到y(tǒng)與智能CAD。E-mail：lh401281894@126.com

崔耀東(1957–)，男，河南林州人，教授，博士。主要研究方向?yàn)橹悄芟到y(tǒng)與智能CAD。E-mail：ydcui@263.net