李海生

(廣西民族師范學院 物理與電子工程學院, 廣西 崇左 532200)

遞歸算法在單一矩形毛坯無約束最優(yōu)排樣中的應用

李海生

(廣西民族師范學院 物理與電子工程學院, 廣西 崇左 532200)

優(yōu)化排樣問題屬于典型的非確定型NP問題，需要借助計算機輔助排樣選出材料利用率最大化和排樣下料效率最高的排樣方案，以解決企業(yè)對排樣的實際需求。討論了單一矩形毛坯無約束剪切排樣優(yōu)化處理問題，基于剪切沖裁相結(jié)合的下料工藝、以條帶數(shù)衡量排樣方式的復雜性，應用遞歸算法通過枚舉搜索法遍歷所有可能的更優(yōu)的排樣方案，在保證毛坯數(shù)最優(yōu)的前提下選出條帶數(shù)最少的排樣方案。實驗計算結(jié)果表明所述算法有效。

計算機輔助；遞歸算法；優(yōu)化排樣；矩形毛坯

Abstract: Optimal layout problem is a typical non-deterministic NP problem that needs the help of Computer Aided Nesting to select the layout scheme with material utilization ratio maximization and cutting patterns efficiency highest. In order to solve the actual demand of enterprise to the layout, the optimization problem of unconstrained cutting patterns for single rectangular blank is discussed. Through the two stages of cutting and blanking stock, with the complexity of cutting patterns measured by the number of strips, using a recursive algorithm search by enumeration method to traverse layout for all possible better, on the premise of guarantee blank for optimal, we choose the layout scheme of the minimum number strip. The calculation results show that the algorithm is effective.

Keywords: computer-aided; recursive algorithm; optimal layout; rectangle blanks

優(yōu)化排樣問題屬于典型的非確定型NP問題[1]，傳統(tǒng)的人工排樣受到多方面因素的影響和制約，降低了生產(chǎn)效率，增加了成產(chǎn)成本。因此，應用計算機輔助排樣(computer aidde nesting,CAN)來解決實際排樣問題是生產(chǎn)力發(fā)展的需要[2]，可充分利用計算機的高速和精確的運算能力以及計算機編程技術(shù)，在短時間內(nèi)遍歷所有可能的更優(yōu)的排樣方案，選出材料利用率最大化和排樣下料效率最高的排樣方案，以達到降低材料成本和排樣下料環(huán)節(jié)勞動成本的目的。

隨著計算機技術(shù)的發(fā)展和深入應用，計算機輔助排樣軟件[3]得到了較好地發(fā)展和應用。由于單一矩形毛坯排樣可以靈活組織下料，同時具有極大的通用性，在涉及到材料切割排樣的行業(yè)中具有現(xiàn)實應用需求，因此深入研究單一矩形毛坯排樣問題具有重要價值。對于單一矩形毛坯排樣問題的求解，文獻[4～5]提出的算法能實現(xiàn)毛坯數(shù)最優(yōu)，但沒有考慮切割工藝的復雜性問題；文獻[6]提出的算法能減少條帶數(shù)，但不能保證條帶數(shù)最優(yōu)；文獻[7]提出的算法能實現(xiàn)毛坯數(shù)和切割工藝最優(yōu)，但算法復雜。本文應用遞歸算法對單一矩形毛坯在矩形板材上進行無約束[8]優(yōu)化排樣，基于規(guī)范多級方式轉(zhuǎn)換定理[9]，以條帶數(shù)衡量單一矩形毛坯剪切排樣方式切割工藝的復雜性，通過枚舉法搜索在實現(xiàn)毛坯數(shù)最優(yōu)的前提下生成條帶數(shù)最優(yōu)的排樣方式，同時算法具有簡單、易于實現(xiàn)軟件開發(fā)的優(yōu)點。

1 遞歸的基本設計思想

基于剪沖工藝的下料方式，在剪切階段每一刀將從當前尺寸為x×y的板材中切出一根條帶(條帶的寬度為毛坯的長度l，其尺寸為x×l或y×l)，依此處理方式直到剩余板材不能切出一個毛坯為止。依次考察當前板材及其相應的剩余板材(從當前板材切出一根條帶后其尺寸為x×(y-l)或(x-l)×y)的排樣方式，發(fā)現(xiàn)具有如下特征：

① 從排樣問題的求解規(guī)模來看，剩余板材的尺寸相對于當前板材的尺寸小，可知剩余板材排樣問題的計算求解規(guī)模相對于當前板材來說其計算求解規(guī)模更小。

② 從排樣問題的求解性質(zhì)來看，當前板材和剩余板材的求解性質(zhì)是相同的，都是在保證毛坯數(shù)最大化的前提下生成條帶數(shù)最少的排樣方式。

③ 從板材所有可能的尺寸來看，在剪切過程中每一刀剪切出一根豎直條帶或垂直條帶，可見對于兩兩相鄰的板材來說具有非常緊密的聯(lián)系，在尺寸上后一個板材的輸入是前一個板材的輸出，因此前一個板材的解依賴于后一個板材的解。

④ 從板材的整個剪切階段來看，所有一系列剩余板材的問題求解規(guī)模和尺寸都是按照一定的條件有規(guī)律地遞減，從而使整個單一矩形毛坯無約束排樣問題逐漸趨向于結(jié)束而得到直接解。當剩余板材不能再剪切出任何一個毛坯時，那么當前排樣方式的求解過程結(jié)束。

綜合①～④來看，單一尺寸矩形毛坯排樣問題的求解過程具有遞歸需要的遞推前進段、回退返回段和邊界條件，滿足遞歸求解排樣問題的條件。對于兩兩相鄰的板材，后一個板材的排樣問題是前一個板材排樣問題的子問題，對所有可能尺寸的板材可應用遞歸算法[10]進行求解。通過搜索遍歷所有的遞歸排樣分支，即可找到毛坯數(shù)最優(yōu)和條帶數(shù)最優(yōu)的規(guī)范多級排樣方式。

2 遞歸剪切排樣算法設計

設毛坯尺寸為l×w(l>w，l為毛坯長度，w為毛坯寬度)，板材初始尺寸為L×W(L>W，L為板材長度，W為板材寬度)。對于尺寸為x×y的當前板材，令M(x,y)和N(x,y)分別表示從當前板材剪切出的條帶數(shù)量和從條帶沖裁出的毛坯數(shù)量。令D(x,y)用于記錄從當前板材x×y剪切出第1根條帶的切割方向。令M0(x,y)和N0(x,y)分別表示當前板材x×y其最優(yōu)排樣方式剪切出的條帶數(shù)量和從條帶沖裁出的毛坯數(shù)量。令Mx和Nx分別表示對當前板材x×y進行橫切時，對應的遞歸排樣分支剪切出的條帶數(shù)和所含毛坯數(shù)。令My和Ny分別表示對當前板材x×y進行豎切時，對應的遞歸排樣分支剪切出的條帶數(shù)和所含毛坯數(shù)。令M(L,W)和N(L,W)分別表示當前排樣方式剪切出的條帶數(shù)和沖裁出的毛坯數(shù)。一維數(shù)組D用來記錄當前排樣方式中所含條帶的切割方向。M0(L,W)和N0(L,W)表示當前最優(yōu)排樣方切割出的條帶數(shù)量和從條帶沖裁出的毛坯數(shù)量。一維數(shù)組D0記錄當前最好排樣方式各根條帶的剪切方向。

2.1 遞歸的方程式

基于規(guī)范多級排樣方式，從當前板材(x,y)剪切出條帶，每一刀剪切方向只能是橫切或豎切。

1) 橫切

如圖1所示，從當前板材的上邊剪切出1根X向條帶，條帶的尺寸是x×l，令條帶x×l可以沖裁出的毛坯數(shù)用Num(x) 表示，則有Num(x)=int(x/w)。剪切出1根X向條帶后剩余板材的尺寸是x×(y-l)，令其可以剪切出的毛坯數(shù)量為N(x,y-l)，條帶數(shù)為M(x,y-l)。令D(x,y)=0表示當前板材x×y第1刀的切割方向為豎切。按此切割方式，可得到如下關(guān)系式：

(1)

圖1 條帶橫切

2) 豎切

如圖2所示，從當前板材的左邊剪切出1根Y向條帶，條帶的尺寸是y×l，令條帶y×l可以沖裁出的毛坯數(shù)用Num(y) 表示，則有Num(y)=int(y/w)。剪切出1根Y向條帶后剩余板材的尺寸是(x-l)×y，令其可以剪切出的毛坯數(shù)量為N(x-l,y)，條帶數(shù)為M(x-l,y)。令D(x,y)=1表示當前板材x×y第1刀的切割方向為豎切。按此切割方式，可得到如下關(guān)系式：

(2)

圖2 豎切

2.2 毛坯數(shù)和條帶數(shù)的優(yōu)化

1) 毛坯數(shù)優(yōu)化

根據(jù)規(guī)范多級排樣方式和剪切沖裁下料工藝，從板材中剪切出條帶時只能是橫切和豎切兩種方式。對于尺寸為x×y的當前板材，若第1刀的剪切方向選擇橫切，那么當前板材遞歸排樣到底部時生成的條帶數(shù)和毛坯數(shù)是由剩余板材x×(y-l)和當前產(chǎn)生的水平條帶x×l來決定的。若第1刀的剪切方向選擇豎切，那么當前板材遞歸排樣到底部時生成的條帶數(shù)和毛坯數(shù)是由剩余板材(x-l)×y和當前產(chǎn)生的垂直條帶y×l來決定的。對于每一刀剪切方向的選擇，是以當前板材最終可生成的毛坯數(shù)及其產(chǎn)生的條帶數(shù)作為選擇依據(jù)的。首先考慮板材的最大利用率，即毛坯數(shù)最優(yōu)的切割方式，在板材利用率相同的情況下，選擇切割工藝最優(yōu)的切割方式。毛坯數(shù)的優(yōu)化處理方式如下：

N0(x,y)={max(N0(x,y-l)+Num(x),

max(N0(x-l,y)+Num(y)}

(3)

2) 條帶數(shù)優(yōu)化

保證在毛坯數(shù)最優(yōu)的前提下，為保證切割工藝最優(yōu)，需要從減少條帶數(shù)對單一尺寸矩形排樣進行優(yōu)化。

初始尺寸為L×W的板材，在不斷地剪切出豎值條帶或垂直條帶后，當剩余板材最終不能沖裁出一個毛坯時，說明遞歸排樣到了底部，生成一種新的排樣方案(當前排樣方式)。為實現(xiàn)在毛坯數(shù)最大化的前提下，得到條帶數(shù)最少的優(yōu)化排樣方式，每當遞歸排樣到了底部時(即N(x,y)=0)，依照如下處理方式進行優(yōu)化：

① 當N(L,W)>N0(L,W)時，令N0(L,W)=N(L,W)，M0(L,W)=M(L,W)，D0(L,W)=D(L,W)。

② 當N(L,W)

①和②表示當前最優(yōu)排樣方式與當前排樣方式生成的毛坯數(shù)不相同時，則優(yōu)選毛坯數(shù)多的排樣方式作為當前最優(yōu)排樣方式，即以毛坯數(shù)最優(yōu)為一級優(yōu)化目標，實現(xiàn)材料利用率的最大化。

③ 當N(L,W)=N0(L,W)且M0(L,W)>M(L,W)時，令N0(L,W)=N(L,W)，M0(L,W)=M(L,W)，D0(L,W)=D(L,W)。表示當前最優(yōu)排樣方式與當前排樣方式生成的毛坯數(shù)相同時，則優(yōu)選條帶數(shù)少的排樣方式作為當前最優(yōu)排樣方式，即保證在毛坯數(shù)最優(yōu)的前提下以減少條帶數(shù)為二級目標，簡化切割工藝提高排樣效率。

根據(jù)①～③得到如下表達式：

(4)

根據(jù)上述可知，如果當前排樣方式相對當前最優(yōu)排樣方式不能引起解的改善，將直接返回上一層遞歸調(diào)用；否則把當前排樣方式置為當前最優(yōu)排樣方式，然后再返回到上一層遞歸調(diào)用，繼續(xù)執(zhí)行指定的遞歸操作，直到遍歷所有的遞歸分支，搜索得到毛坯數(shù)和條帶數(shù)最優(yōu)的排樣方式。

2.3 遞歸函數(shù)的構(gòu)建

設遞歸函數(shù)RecFun(x,y,NP,MP,D)用于求解板材尺寸為L×W、毛坯尺寸為l×w的排樣方式最優(yōu)毛坯數(shù)，其中：參數(shù)NP表示剪切到當前板材尺寸為x×y時已經(jīng)切出的毛坯數(shù)量；參數(shù)MP表示剪切到當前板材尺寸為x×y時已經(jīng)切下的條帶數(shù)量；參數(shù)D表示一維數(shù)組D用于記錄條帶切割的方向，“0”表示條帶方向為豎直切割，“1”表示條帶方向為水平切割。

當前最優(yōu)排樣方式的毛坯數(shù)(N0(L,W))和條帶數(shù)(M0(L,W))的初始值為N0(L,W)=M0(L,W)=0。根據(jù)式(1)～(4)，遞歸函數(shù)RecFun(x,y,NP,MP,D)為：

Setp1If(min(x,y)

If((NP>N0(L,W) or (NP=N0(L,W) andMP

letN0(L,W)=NP;

M0(L,W)=MP;

D0=D;

N0(x,y)=M0(x,y)=0;

Return 0;

Setp2If(y≥landx≥w) then

letD(MP+1)=1;

Nx=RecFun(x,y-l,NP+Num(x),MP+1,D)+Num(x);

Mx=1+M(x,y-l);

Setp3If(x≥landy≥w) then

letD(MP+1)=0;

Ny=RecFun(x-l,y,NP+Num(y),MP+1,D)+Num(y);

My=1+M(x-l,y);

Setp4If(Nx>Ny) then letN0(x,y)=Nx,M0(x,y)=Mx;

If(Nx

If(Nx=Ny) then letN0(x,y)=NxorN0(x,y)=Ny,M0(x,y)=min(Mx,My);

Setp5ReturnN0(x,y)。

2.4 求解步驟

基于Win 32位系統(tǒng)平臺，應用 C++面向?qū)ο缶幊陶Z言開發(fā)了單一尺寸矩形毛坯排樣系統(tǒng)，以測試驗證本文所述算法的有效性。初始調(diào)用遞歸函數(shù)RecFun()時，實參板材尺寸為L×W、形式參數(shù)NP和MP對應的實參值均為0，即RecFun(L,W,0,0,D)，具體求解過程如下：

步驟1 輸入毛坯l×w和板材L×W的尺寸值。

步驟2 令N0(L,W)=M0(L,W)=0。

步驟3 調(diào)用遞歸函數(shù)RecFun(L,W,0,0,D)進行優(yōu)化排樣，求出N0(L,W)、M0(L,W)及D0。

步驟4 根據(jù)板材L×W、毛坯l×w和D0中前M0(L,W)個元素，畫出排樣圖。

3 實驗計算分析

3.1 毛坯數(shù)實驗計算分析

1) 應用例題

毛坯尺寸l×w為3×2、板材尺寸L×W為8×6，如圖3所示，應用遞歸算法進行排樣。

圖3 毛坯和板材尺寸

2) 例題求解

初始條件：x=8，y=6；N0(L,W)=M0(L,W)=0。

遞歸結(jié)束條件： Min(x,y)<2 OR Max(x,y)<3。

通過調(diào)用遞歸函數(shù)RecFun(8,6,0,0,D)進行優(yōu)化排樣，整個遞歸調(diào)用排樣過程，如圖4所示。

圖4 遞歸排樣執(zhí)行過程示意圖

3) 排樣分析

根據(jù)圖4可知：本例題所有可能的排樣方式為D、E、G、J、K、L共6種，對應毛坯數(shù)、板材利用率如表1所示。

表1 本例題所有可能的排樣方式

根據(jù)圖4和表1可知：如果只考慮板材的利用率，最優(yōu)的排樣方式為D、L，板材利用率均為100%，而E、G、J、K這4種排樣方式的板材利用率僅為87.5%。在材料分割領域，利用排樣方式為D、L進行下料可以最大化提高材料的利用價值，顯然優(yōu)于E、G、J、K這4種排樣方式，可見在下料的過程中考慮毛坯數(shù)、利用計算機輔助排樣提高材料利用率具有重要的價值和意義。排樣方式L的條帶數(shù)2優(yōu)于條帶數(shù)為4的排樣方式D，利用本文算法同時考慮毛坯數(shù)和條帶數(shù)，確定最優(yōu)排樣方式為L。

3.2 條帶數(shù)實驗計算分析

3.2.1 實驗數(shù)據(jù)

如表2所示，板材和毛坯的尺寸范圍基本涵蓋了實際生產(chǎn)中的板材和毛坯的尺寸比例。在實際生產(chǎn)中，若板材和毛坯的尺寸含有小數(shù)，可通過等比例轉(zhuǎn)換成整數(shù)。根據(jù)表2，使用程序隨機生成20道例題，如表3所示?；诒疚乃惴?，在保證材料利用率最大化的前提下，生成條帶數(shù)最少的排樣方式(即遞歸算法)和條帶數(shù)最多的排樣方式(在遞歸算法的基礎上進行改進，在保證毛坯數(shù)最優(yōu)的情況下，生成條帶數(shù)最多的排樣方式，即帶數(shù)最多算法)，以便進行對比分析。

表2 板材和毛坯的尺寸范圍 mm

表3 隨機生成的20道例題

3.2.2 實驗結(jié)果及其分析

1) 實驗結(jié)果

表4的實驗結(jié)果是通過單一矩形毛坯排樣系統(tǒng)計算獲得。實驗數(shù)據(jù)符號的含義：N11、S11分別表示運用本文遞歸算法求解得到的毛坯數(shù)、條帶數(shù)；N21、S21分別表示基于本文所述算法的帶數(shù)最多算法排樣求解得到的毛坯數(shù)、條帶數(shù)。

表4 排樣實驗結(jié)果

2) 實驗結(jié)果分析

根據(jù)表3和表4可知：條帶數(shù)相同的例題為1、4、8、10、13、15，而例題2、3、5、6、7、9、11、12、14、16、17、18、19、20條帶數(shù)互不相同，具體如圖5所示。

圖5 基于遞歸算法和帶數(shù)最多算法排樣條帶數(shù)比較

如果N11=N21、S11=S21，說明在實現(xiàn)毛坯數(shù)最優(yōu)的前提下其排樣方式的條帶數(shù)也是最優(yōu)的(切割工藝最優(yōu))；如果N11=N21、S11≠S21，說明能實現(xiàn)毛坯數(shù)最優(yōu)的排樣方式，其條帶數(shù)未必是最優(yōu)的，即存在條帶數(shù)不一樣的排樣方式。根據(jù)表4和圖5可知：對于任何一道例題均有N11=N21、S11≤S21，說明應用本文的遞歸算法可以在保證毛坯數(shù)最優(yōu)的前提下實現(xiàn)條帶數(shù)最少，即使切割工藝最優(yōu)。表5為遞歸算法和帶數(shù)最多算法的條帶數(shù)平均值。

表5 條帶數(shù)平均值

根據(jù)表4中遞歸算法和帶數(shù)最多算法排樣結(jié)果，各道例題條帶數(shù)的差值范圍為0～14。根據(jù)表5實驗數(shù)據(jù)，這兩種算法的條帶數(shù)平均值的差值為3.65?；诩魶_工藝，單一尺寸矩形毛坯下料工作量主要取決于從板材中剪出所有條帶的時間開銷。由于切割工藝的復雜性與板材剪切出的條帶數(shù)近似成正比，若條帶數(shù)越多那么相應地下料工作量也就越大，排樣效率就越低。根據(jù)表4條帶數(shù)差值范圍和表5條帶數(shù)平均值差值，表明在單一矩形毛坯無約束排樣中對條帶數(shù)進行優(yōu)化是必要的，在材料利用率最大化的前提下盡可能地減少條帶數(shù)以簡化切割工藝具有重要的現(xiàn)實意義。

從實驗結(jié)果可知：本文遞歸算法能在保證毛坯數(shù)最優(yōu)的前提下實現(xiàn)切割工藝最優(yōu)。

4 結(jié)束語

采用本文提出的遞歸算法對單一尺寸矩形毛坯排樣問題進行求解，能同時實現(xiàn)毛坯數(shù)最優(yōu)和切割工藝最優(yōu)。相對于其他算法，一方面本文算法實現(xiàn)較簡單，在開發(fā)排樣系統(tǒng)的過程中軟件工程師將算法轉(zhuǎn)化為對應代碼很容易，這點在工程應用中比較重要；另一方面該算法屬于枚舉搜索法，能得到條帶數(shù)最小的解，保證解的最優(yōu)性。在涉及二維下料的制造行業(yè)中，通常會涉及到二維矩形板材的選購，若有多種尺寸不同、厚度和材質(zhì)相同的板材提供選擇，企業(yè)可以利用本文算法進行計算分析，優(yōu)選利用率最大化的板材尺寸。企業(yè)在下料環(huán)節(jié)，則應用該算法在板材利用率最大的所有排樣方案中選擇切割工藝最優(yōu)的排樣方式，以有效降低原材料成本和減少人工成本。

[1] 李秋蓉.考慮切割刀數(shù)的板材下料算法研究[D].南寧:廣西大學,2013.

[2] 王曉慶.基于層排樣方式的矩形毛坯下料算法[D].南寧:廣西師范大學,2011.

[3] 田雙.基于Sigma Nest的板材下料問題研究[J].現(xiàn)代機械,2014 (4):25-27,31.

[4] ARSLANOV M Z.Continued fractions in optimal cutting of a rectangular sheet into equal small rectangles[J].European Journal of Operational Research,2000,125:239-248.

[5] 潘衛(wèi)平,陳秋蓮,崔耀東.考慮切割刀數(shù)的最優(yōu)兩段排樣算法研究[J].廣西大學學報,2014,39(3):687-692.

[6] CUI Y,GU T,HU W.Recursive algorithms for the optimum cutting of equal rectangles[J].International Journal of Computers and Applications,2011,33(2):103-107.

[7] 王桂蘭,成亞云,朱龍彪,朱志松.滿足“一刀切”要求的木工板排樣優(yōu)化研究[J]工程設計學報,2014,21(3):212-216.

[8] 秦旭輝.圓形件剪切下料的排樣研究[D].長春:吉林大學,2014.

[9] 陳奇.數(shù)控切割下料與排程優(yōu)化技術(shù)及應用研究[M].武漢:華中科技大學,2012.

[10] 鄭文.基于多線程求解一維下料問題的遞歸算法[D].南寧:廣西大學,2011.

(責任編輯陳 艷)

RecursiveAlgorithmAppliedStudyonaSingleRectangleBlanksUnconstrainedOptimalLayout

LI Haisheng

(College of Physics and Electronic Engineering, Guangxi Normal University for Nationalities, Chongzuo 532200, China)

2017-05-04

國家自然科學基金資助項目(61363026)；廣西民族師范學院校級科研項目(2016YB037)

李海生(1980—)，男，廣西扶綏人，碩士，講師，主要從事網(wǎng)絡技術(shù)和排樣計算方面的研究，E-mail：lihsmsy@126.com。

李海生.遞歸算法在單一矩形毛坯無約束最優(yōu)排樣中的應用[J].重慶理工大學學報(自然科學)，2017(9):125-131.

formatLI Haisheng.Recursive Algorithm Applied Study on a Single Rectangle Blanks Unconstrained Optimal Layout[J].Journal of Chongqing University of Technology(Natural Science)，2017(9):125-131.

10.3969/j.issn.1674-8425(z).2017.09.020

TP399

A

1674-8425(2017)09-0125-07