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

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

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

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

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

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

提出一種在矩形板材上引入梯形條帶來進(jìn)行排樣的方法，首先用兩條平行的分界線將板材分為兩個(gè)大小一致的直角梯形段和一個(gè)平行四邊形段，分別采用遞歸算法和動(dòng)態(tài)規(guī)劃算法確定梯形段和平行四邊形段中條帶的最優(yōu)組合，從而確定最優(yōu)排樣方式；再結(jié)合線性規(guī)劃算法解決圓片下料問題，使得整個(gè)下料方案的材料利用率最大化。最后采用大量隨機(jī)生成的例題進(jìn)行實(shí)驗(yàn)，實(shí)驗(yà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á)千萬噸，且原材料費(fèi)用占生產(chǎn)成本的60%以上，因此提高材料利用率能夠?yàn)槠髽I(yè)帶來非常可觀的經(jīng)濟(jì)效益。將圓片下料技術(shù)應(yīng)用于企業(yè)生產(chǎn)實(shí)踐，能有效地提高下料利用率、節(jié)省原材料、提高企業(yè)在同行中的競爭力[2]。

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

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

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

1.1 相關(guān)概念

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

本文算法在矩形板材上同時(shí)應(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 條帶寬度和價(jià)值

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

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

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

由幾何規(guī)則可知

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

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

圖5 梯形條帶初始長度

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

圖6 板材切割示意圖

1.2.1 梯形排樣算法

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

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

步驟2. 令Ft(x,h)=0，i=1，得到當(dāng)前梯形條帶當(dāng)前價(jià)值向量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可分別計(jì)算出平行四邊形中的條帶寬度向量PS和價(jià)值向量PT，平行四邊形段的最大價(jià)值由以下數(shù)學(xué)模型求解

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

該模型是一個(gè)背包問題，可通過下面的背包函數(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得到梯形段最大價(jià)值ZT(bl,W)。

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

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

2 下料方案生成算法

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

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

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

其中，C為板材的價(jià)值向量，C=[c1,c2,··,cn]，n為排樣方案包含排樣方式的個(gè)數(shù)，若下料時(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為其中一種下料方案所消耗的板材的總價(jià)值；B=[b1,b2,··,bk]為毛坯的需求數(shù)量的列向量；A 為k行n列的記錄各種排樣方式的矩陣，其元素aij(i=1,2,··,k，j=1,2,··,n)表示第 j種排樣方式中包含第i種毛坯的個(gè)數(shù)。矩陣中每一個(gè)列向量即記錄一種排樣方式中用到的各毛坯的數(shù)量。

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

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

(2) 修改毛坯的當(dāng)前毛坯價(jià)值向量 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 圓片下料方案的算法實(shí)現(xiàn)

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

Begin

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

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

令value=L×W+1；

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

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

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

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

將X中的元素向上取整；

End

3 實(shí)驗(yàn)結(jié)果

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

3.1 算法對(duì)材料利用率的提高

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

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

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

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

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

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

3.3 求解一個(gè)真實(shí)的下料案例

板材大小為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。程序求解耗時(shí)43.23 s，下料方案如圖7所示，總共消耗了483塊板材，一共有8種排樣方式，材料利用率為73.68%。

圖7 下料方案圖例

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

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

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

4 結(jié) 論

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

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

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

[3] 楊 劍, 黃少麗, 侯桂玉, 等. 圓片剪沖下料排樣算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 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ì)算機(jī)工程, 2009, 35(14): 195-197.

[7] 王 巖, 潘衛(wèi)平, 胡 鋼. 生成圓形片最優(yōu)四塊排樣方式的確定性算法[J]. 機(jī)械設(shè)計(jì)與制造, 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é)基金項(xiàng)目(61363026，71371058)

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

E-mail：gxcy@foxmail.com