陳 燕， 劉 詠， 謝琪琦， 崔耀東

(1. 廣西大學(xué)計算機(jī)與電子信息學(xué)院，廣西 南寧 530004；2. 華南理工大學(xué)工商管理學(xué)院，廣東 廣州 510640)

基于梯形和平行四邊形的圓片剪沖下料算法設(shè)計與實現(xiàn)

陳 燕1,2， 劉 詠1， 謝琪琦1， 崔耀東1

(1. 廣西大學(xué)計算機(jī)與電子信息學(xué)院，廣西 南寧 530004；2. 華南理工大學(xué)工商管理學(xué)院，廣東 廣州 510640)

提出一種在矩形板材上引入梯形條帶來進(jìn)行排樣的方法，首先用兩條平行的分界線將板材分為兩個大小一致的直角梯形段和一個平行四邊形段，分別采用遞歸算法和動態(tài)規(guī)劃算法確定梯形段和平行四邊形段中條帶的最優(yōu)組合，從而確定最優(yōu)排樣方式；再結(jié)合線性規(guī)劃算法解決圓片下料問題，使得整個下料方案的材料利用率最大化。最后采用大量隨機(jī)生成的例題進(jìn)行實驗，實驗結(jié)果表明該算法能有效提高材料利用率。

圓片排樣；剪沖下料；平行四邊形條帶；梯形條帶

隨著資源和能源危機(jī)的出現(xiàn)，要求各企業(yè)不斷提高原材料利用率、減少切割能源消耗，于是研究下料利用率高且切割工藝簡單的布局優(yōu)化算法，切割與裝填布局(cutting and packing, C&P)[1]問題越來越受到各制造企業(yè)的關(guān)注。特別地，圓片下料問題廣泛存在機(jī)械制造、電機(jī)、船舶、航空航天等行業(yè)中，例如：電機(jī)定子和轉(zhuǎn)子鐵心是用硅鋼圓片制作而成；家居的鍋、壺、盆是用不

銹鋼圓片制作的，等等。這些行業(yè)每年消耗的金屬板材量達(dá)千萬噸，且原材料費用占生產(chǎn)成本的60%以上，因此提高材料利用率能夠為企業(yè)帶來非?？捎^的經(jīng)濟(jì)效益。將圓片下料技術(shù)應(yīng)用于企業(yè)生產(chǎn)實踐，能有效地提高下料利用率、節(jié)省原材料、提高企業(yè)在同行中的競爭力[2]。

近年來，針對圓片條帶剪沖下料問題的方法研究，主要有矩形條帶進(jìn)行排樣的方法[3-8]和采用平行四邊形條帶進(jìn)行排樣的方法[9]等。文獻(xiàn)中有關(guān)矩形條帶進(jìn)行排樣的方式也各有不同，其中：文獻(xiàn)[3]采用動態(tài)規(guī)劃算法在精確算法的基礎(chǔ)上，選取規(guī)范長度和規(guī)范寬度的子集進(jìn)行計算，解決剪切階段的無約束排樣問題。文獻(xiàn)[4]利用動態(tài)規(guī)劃算法生成T形排樣的方式；文獻(xiàn)[5]采用動態(tài)規(guī)劃算法生成多段排樣的方式；文獻(xiàn)[6]采用動態(tài)規(guī)劃算法與枚舉法結(jié)合生成三塊結(jié)構(gòu)的排樣方式。文獻(xiàn)[7] 和[8]均采用生成四塊結(jié)構(gòu)的排樣方式，文獻(xiàn)[7]的算法是先求解一維背包問題生成塊里面的條帶最優(yōu)布局，然后用隱式枚舉三條分界線位置得到所有可能的四塊組合，選擇排樣價值最大的四塊組合生成最優(yōu)的四塊排樣方式；而文獻(xiàn)[8]同時使用條帶直切排樣方式和 T型排樣方式，先采用動態(tài)規(guī)劃技術(shù)生成排樣方式，然后采用基于列生成的線性規(guī)劃技術(shù)迭代調(diào)用排樣方式生成下料方案。文獻(xiàn)[9]基于卷材首次采用平行四邊形條帶進(jìn)行排樣，通過不斷地重復(fù)最優(yōu)的x段和y段，使排樣達(dá)到全局最優(yōu)，同時驗證了相對于矩形條帶排樣平行四邊形條帶排樣可以獲得更高的材料利用率。卷材的特點是材料長度不受限，根據(jù)對多家企業(yè)包括寶鋼、武鋼的板材加工配送中心調(diào)查研究，目前實際生產(chǎn)剪裁下料中各企業(yè)使用的材料絕大部分是相對固定大小的板材[10]。

本文基于平行四邊形排樣以獲取更高的材料利用率，同時可避免在矩形板材上切割平行四邊而產(chǎn)生直角三角形的廢料，創(chuàng)新性地引入了梯形條帶排樣方式。首先在固定大小的矩形板材上用兩條平行的分界線將板材切割成兩個大小一致的直角梯形段和一個平行四邊形段，然后應(yīng)用平行四邊形條帶及梯形條帶組合排樣的三段排樣方式。本文算法能保證在整板上切割兩刀即可產(chǎn)生最優(yōu)的平行四邊形條帶和梯形條帶，從而對降低總的生產(chǎn)成本、減少板材大面積損耗概率提供保障。首先分別采用遞歸算法和動態(tài)規(guī)劃算法確定梯形條帶和平行四邊形段中條帶的最優(yōu)組合，從而確定當(dāng)前的最優(yōu)排樣方式；然后應(yīng)用線性規(guī)劃(linear programming, LP)方法求解圓片剪沖下料問題 (cutting stock problem of circular blanks, CSPCB)，使得整個下料方案的材料利用率接近最優(yōu)；最后通過與其他采用固定大小板材進(jìn)行排樣的算法實驗說明本文算法對板材利用率的提高，同時分析條帶中排入毛坯行數(shù)對材料利用率的影響，還分析了算法的時間復(fù)雜度和計算產(chǎn)生最優(yōu)排樣方案所消耗的時間。實驗數(shù)據(jù)表明，本文算法是有效性的、計算時間是可接受的。

1 排樣方式算法原理及其實現(xiàn)

1.1 相關(guān)概念

1.1.1 毛坯在條帶上的排列、條帶方向和長度

本文算法在矩形板材上同時應(yīng)用平行四邊形條帶和直角梯形條帶進(jìn)行排樣，平行四邊形條帶可以是X向或Y向，梯形條帶只允許X向條帶。如圖1(a)中的箭頭方向表示該條帶是X向，圖1(b)中的箭頭方向表示該條帶是Y向，X向條帶中毛坯是從左至右依次排放；Y向條帶中毛坯是從下至上依次排放。平行四邊形Y向條帶可由平行四邊形X向條帶旋轉(zhuǎn)60°得到。

圖1 條帶方向及毛坯排列

每根條帶包含一排或者多排直徑相同的圓片，如圖2所示，d為圓片直徑，相鄰圓片邊界距離為w，即為工藝余量，圓片離條帶邊界的距離為w/2，相鄰兩排圓片間的距離為，平行四邊形條帶和梯形條帶的底角均為60°。

圖2 雙排條帶

圖3(a)為平行四邊形條帶排列示意圖，sh為平行四邊形中與條帶方向垂直的高度，ps為平行四邊形中不與條帶方向平行的底邊長度。圖3(b)所示為梯形條帶排列示意圖，其中bt表示梯形條帶下底邊的長度，ut表示上底邊的長度，ts表示條帶的高，毛坯在條帶中的排列是從斜邊底部開始，依次向直角邊進(jìn)行排放。

圖3 平行四邊形條帶及梯形條帶

1.1.2 條帶寬度和價值

平行四邊形條帶的寬度是與條帶底邊方向成60°的的長度，即圖3(a)中ps邊長；梯形條帶的寬度是梯形的高，即圖3(b)中ts邊長。記gi(若無說明i取值范圍均為1≤i≤k，k為需求毛坯種數(shù))為第i種毛坯的條帶中允許的最大排數(shù)，其中第j(若無說明j取值范圍均為1≤j≤gi)種條帶包含有j排毛坯。

(1) 平行四邊形條帶的價值計算。由圖 2及圖3(a)可得，則平行四邊形條帶寬度：，記vi為第i種毛坯的單個毛坯價值，條帶的價值即是條帶中所有毛坯的價值總和。如圖4所示，pd是平行四邊形條帶能包含至少一個毛坯的條帶長度。當(dāng)?shù)?i種毛坯的條帶長度為x時，若其中包含有j排毛坯，根據(jù)以下步驟計算平行四邊形條帶價值：

圖4 平行四邊形條帶初始長度

由幾何規(guī)則可知

條帶中第m排毛坯的個數(shù)

若x＜td，條帶中毛坯個數(shù)n=0；若x≥td，條帶中毛坯個數(shù)，所以梯形條帶價值為tt=nvi。

圖5 梯形條帶初始長度

如圖6所示，兩條與底邊成60°的切割線將板材分為 3個部分，兩個梯形段大小一致，中間部分是平行四邊形段。切割起點距板材寬的距離為y的切割線，且稱之為分隔線y。每個段中的條帶方向都是一致的，梯形段中的條帶都是 X向，平行四邊形段中的條帶是X向或Y向。記排入梯形段中所有毛坯價值總和的最大值為 ZT(bl,W )，其中W 是板材的寬度，bl為梯形段底邊的長度，可由計算得出。記排入平行四邊形段中所有毛坯價值總和的最大值為 ZP(pl,p w)，其中，同時稱相對應(yīng)的平行四邊形為pl×pw。由幾何規(guī)則可知y的取值范圍為。若排入平行四邊形段的條帶方向是 X向，則此時該段的最大價值為Zx(pl,p w)；若排入的條帶方向是y向，此時該段的最大價值為 Zy(pl, pw)，因此平行四邊形段的最大價值。整個板材中毛坯的最大價值 z(y) =2 ZT(bl,W)+ ZP(pl, pw)，若對于所有的y，都有 z(y0)≥ z(y)，則記y0為最優(yōu)分割線。

圖6 板材切割示意圖

1.2.1 梯形排樣算法

設(shè)遞歸函數(shù)Rec(bl,W)返回下底長為bl高為W的梯形段的最大價值，其步驟如下：

步驟1. 如果Ft(x,h)≥0，轉(zhuǎn)向步驟6；否則轉(zhuǎn)步驟2。

步驟2. 令Ft(x,h)=0，i=1，得到當(dāng)前梯形條帶當(dāng)前價值向量TT。

步驟3. 如果 h＜tsi，轉(zhuǎn)步驟5；否則，令ut= q(x,t si)，令 V =tti+ Rec(ut,h -tsi)。

步驟 4. 如果 V≤Ft(x,h)，轉(zhuǎn)步驟 5；否則令Ft(x,h)=V。

步驟5. 令i=i+1。如果i≤M，轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟6。

步驟6. 返回Ft(x,h)。

1.2.2 平行四邊形排樣算法

在圖6的平行四邊形段pl×pw中，假定條帶方向和pl方向一致，根據(jù)1.1可分別計算出平行四邊形中的條帶寬度向量PS和價值向量PT，平行四邊形段的最大價值由以下數(shù)學(xué)模型求解

其中，ni為正整數(shù)，i=1,2,··,M

該模型是一個背包問題，可通過下面的背包函數(shù)求得問題的解

同理可求得 Zy(pl,pw) ，令 ZP(pl,p w)= max{Zx(p l,p w),Zy(p l,p w) }。

1.2.3 板材最優(yōu)排樣方式生成算法

步驟1. 根據(jù)板材大小L×W得到y(tǒng)max及pw的值，初始化PS、TS，令i=0。

步驟2. 根據(jù)i得到bl、pl的值，得到PT。

步驟3. 根據(jù)1.2.1得到梯形段最大價值ZT(bl,W)。

步驟4. 根據(jù)1.2.2得到平行四邊形段最大價值ZP(pl, pw)。

步驟6. 令i=i+1，若 i≤ymax，轉(zhuǎn)步驟2；否則輸出y0、z0及當(dāng)前排樣P。

2 下料方案生成算法

2.1 圓片下料問題的線性規(guī)劃模型

圓片剪沖下料問題CSPCB可描述為：對庫存板材進(jìn)行剪沖下料，以滿足k種圓片毛坯的需求，其中第i種毛坯的需求量為bi，i=1,2,··,k。問題求解要求確定一種最優(yōu)下料方案，使得在滿足所有毛坯需求的前提下，所消耗的板材張數(shù)最少。

采用LP方法求解該問題的數(shù)學(xué)模型為

其中，C為板材的價值向量，C=[c1,c2,··,cn]，n為排樣方案包含排樣方式的個數(shù)，若下料時只用到單一規(guī)格的矩形板材，則cj=L×W(j=1,2,··,n)，L和W分別為矩形板材的長度和寬度；X=[x1,x2,··,xn]T，xj(j=1,2,··,n)為下料方案中應(yīng)用每種排樣方式的次數(shù)；z為其中一種下料方案所消耗的板材的總價值；B=[b1,b2,··,bk]為毛坯的需求數(shù)量的列向量；A 為k行n列的記錄各種排樣方式的矩陣，其元素aij(i=1,2,··,k，j=1,2,··,n)表示第 j種排樣方式中包含第i種毛坯的個數(shù)。矩陣中每一個列向量即記錄一種排樣方式中用到的各毛坯的數(shù)量。

可用列延遲生成法解上述模型，具體步驟如下：

(1) 確定初始可行解。初始化A為一個單位矩陣，則初始可行解X=B。

(2) 修改毛坯的當(dāng)前毛坯價值向量 V，V=CA–1。

(3) 求解使目標(biāo)函數(shù)改善的排樣方式。根據(jù)1.2.3得到當(dāng)前排樣方式P。若LW–VP＜0，則引入P改善矩陣A，用引入的P替換A中的第q列，q可根據(jù)單純形法求得，并令cq=LW，轉(zhuǎn)步驟2。若LW–VP≥0，則當(dāng)前下料方案已是最優(yōu)，結(jié)束循環(huán)。

2.2 圓片下料方案的算法實現(xiàn)

針對用線性規(guī)劃模型求解CSPCB問題，本文提出以下算法實現(xiàn)解決方案：

Begin

初始化板材大小、毛坯的各參數(shù)及初始可行解X；

確定當(dāng)前毛坯的價值向量V=CA–；

令value=L×W+1；

調(diào)用排樣方式生成算法，value=z0；

記錄當(dāng)前排樣方式P；

根據(jù)單純形法確定q，用P替換A中的第q列；

求解X，重置當(dāng)前毛坯價值向量V=CA-；

將X中的元素向上取整；

End

3 實驗結(jié)果

在Mirosoft visual studio 2013平臺上用C#語言編程實現(xiàn)算法，在主頻為2.60 GHz，內(nèi)存為8 GB的計算機(jī)上進(jìn)行實驗。

3.1 算法對材料利用率的提高

材料利用率 U=(所需毛坯的總面積/消耗板材的總面積)×100%。本文實驗采用文獻(xiàn)[4]的變量取值范圍，如表1所示。隨機(jī)生成500個測試樣例與文獻(xiàn)[4]中的 T形排樣算法作比較，本文算法得到的平均材料利用率為70.81%，而文獻(xiàn)[4]中T形排樣算法得到的平均材料利用率為 68.46%。兩者相比，本文算法的平均材料利用率約高出 2個百分點，說明本文算法更有利于提高生產(chǎn)的經(jīng)濟(jì)效益。

表1 參數(shù)取值范圍

3.2 參數(shù)對材料利用率的影響

本文還對條帶中允許排入毛坯的最大排數(shù)對材料利用率的影響進(jìn)行了研究。參數(shù)的取值范圍參照表 1，其中條帶允許最大排數(shù)分別取為 1，2，··，6，取為1時表明一根條帶中只能有一行毛坯，取為 2時表明一根條帶中可以包含一行毛坯也可以包含兩行毛坯，以此類推。分別用這些參數(shù)各隨機(jī)生成 100個測試樣例，其平均材料利用率的結(jié)果如表2所示。

由實驗結(jié)果可知，增加條帶中允許的毛坯排數(shù)可以提高材料利用率，在排數(shù)小于等于 3時，材料利用率的提高較為明顯；當(dāng)排數(shù)大于 3時，材料利用率的提高不明顯，因此本文算法建議允許的條帶排數(shù)不超過3。

表2 條帶排數(shù)對材料利用率的影響(%)

3.3 求解一個真實的下料案例

板材大小為2000×1000，需求毛坯有8種，其直徑大小分別為362，297，102，153，148，352，198，244，需求數(shù)量分別為2 672，532，2 775，1 034，1 216，1 786，1 515，2 522，工藝余量為8。程序求解耗時43.23 s，下料方案如圖7所示，總共消耗了483塊板材，一共有8種排樣方式，材料利用率為73.68%。

圖7 下料方案圖例

3.4 算法時間復(fù)雜度分析

算法的效率一般用時間復(fù)雜度來衡量，時間復(fù)雜度可以描述算法執(zhí)行基本運(yùn)算的次數(shù)。對于CSPCB問題，基本運(yùn)算可以看成是一個排樣方式的生成。本文用單純形法求解線性規(guī)劃問題，最壞情況下的時間復(fù)雜度是指數(shù)級別的，所以需用排樣方式生成算法的時間復(fù)雜度來判斷算法的優(yōu)劣性。對于算法1.2.1，T(n)=T(n–1)+O(1)=O(n)，則時間復(fù)雜度為O(MW)；對于算法1.2.2，背包體積為L，物品種類個數(shù)為M，則動態(tài)規(guī)劃算法解決該問題的時間復(fù)雜度為 O(ML)。則排樣方式生成算法1.2.3的時間復(fù)雜度為 O(ML2)。在隨機(jī)生成的 500個樣例的實驗中，平均每個問題的計算時間是53.526 s。

CSPCB是一個NP難問題，在有限的時間內(nèi)只能得到一個接近最優(yōu)的解。本文算法相對于其他算法在時間上沒有顯著的改善，但是在材料利用率上有較大的提高。實際生產(chǎn)中，一個生產(chǎn)計劃的下料方案在計算出來之后就不會改變，本文算法所消耗的時間在可接受的范圍之內(nèi)。

4 結(jié) 論

本文提出在矩形板材上引入梯形條帶排樣方式，可以利用平行四邊形排樣以獲取更高的材料利用率，同時又可以利用在矩形板材上切割平行四邊產(chǎn)生的直角三角形廢料。實現(xiàn)了梯形排樣和平行四邊形排樣的算法，用于求解實際的板材下料問題。實驗計算結(jié)果表明，應(yīng)用平行四邊形條帶和梯形條帶組合排樣的算法比 T形排樣算法獲得更高的材料利用率；實驗結(jié)果還證明了毛坯行數(shù)在 3~4行時材料利用率提高得較為明顯，最后通過實驗圖給出一個完整的下料解決方案。

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

[2] 崔耀東. 計算機(jī)排樣技術(shù)及其應(yīng)用[M]. 北京: 機(jī)械工業(yè)出版社, 2004: 82.

[3] 楊 劍, 黃少麗, 侯桂玉, 等. 圓片剪沖下料排樣算法[J]. 計算機(jī)工程與設(shè)計, 2010, 31(23): 5139-5142.

[4] Cui Y D. Generating optimal T-shape cutting patterns for circular blanks [J]. Computers & Operations Research, 2005, 32(1): 143-152.

[5] Cui Y D. Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors [J]. European Journal of Operational Research, 2006, 169(1): 30-40.

[6] 陳 菲, 劉 勇, 劉 睿, 等. 基于3塊方式的圓形片剪沖排樣算法[J]. 計算機(jī)工程, 2009, 35(14): 195-197.

[7] 王 巖, 潘衛(wèi)平, 胡 鋼. 生成圓形片最優(yōu)四塊排樣方式的確定性算法[J]. 機(jī)械設(shè)計與制造, 2014, (9): 152-155.

[8] 王 峰, 張 軍, 胡 鋼. 圓形片剪沖下料問題的一種求解算法[J]. 鍛壓技術(shù), 2015, 40(10): 39-44.

[9] Cui Y D, Song X X. Applying parallelgrammic strips for cutting circles from stainless steel rolls [J]. Journal of Materials Processing Technology, 2008, 205: 138-145.

[10] Cui Y D, Chen Y Y, Wu J L. Selecting the best sheet length for the steel stock used in circular blank production [J]. Iie Transactions, 2006, 38(10): 829-836.

An Algorithm for Circle Cutting Stock Problem Based on Trapezoid and Parallelogram

Chen Yan1,2, Liu Yong1, Xie Qiqi1, Cui Yaodong1

(1. Department of Computer and Electronic Information, Guangxi University, Nanning Guangxi 530004, China; 2. School of Business Administration, South China University of Technology, Guangzhou Guangdong 510640, China)

A pattern of circular cutting in rectangle sheet is proposed by introducing trapezoidal stripes. Plate with two parallel dividing lines will be divided into three segments when the nesting, two segments of the same size right angle trapezoid and one parallelogram segment. Respectively recursive algorithm and dynamic programming algorithm are used to determine the optimal combination of stripes in trapezoidal section and parallelogram section, so as to determine the optimal pattern. Then combine with linear programming algorithm to solve the problem of the two-dimensional cutting pattern problem, making material utilization maximum. Finally, experiment results of a large number of randomly generated problems show the effectiveness of improving material utilization of the algorithm.

circular cutting pattern; shearing and punching; parallelogram stripes; trapezoidal stripes

TH 164

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

A

2095-302X(2016)05-0661-07

2016-01-06；定稿日期：2016-03-20

國家自然科學(xué)基金項目(61363026，71371058)

陳 燕(1975–)，女，廣西北流人，教授，博士研究生。主要研究方向為高性能計算、算法優(yōu)化設(shè)計與實現(xiàn)、計算機(jī)輔助設(shè)計等。

E-mail：gxcy@foxmail.com