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

李海生

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

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

李海生

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

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

計(jì)算機(jī)輔助；遞歸算法；優(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)成本。因此，應(yīng)用計(jì)算機(jī)輔助排樣(computer aidde nesting,CAN)來解決實(shí)際排樣問題是生產(chǎn)力發(fā)展的需要[2]，可充分利用計(jì)算機(jī)的高速和精確的運(yùn)算能力以及計(jì)算機(jī)編程技術(shù)，在短時(shí)間內(nèi)遍歷所有可能的更優(yōu)的排樣方案，選出材料利用率最大化和排樣下料效率最高的排樣方案，以達(dá)到降低材料成本和排樣下料環(huán)節(jié)勞動(dòng)成本的目的。

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

1 遞歸的基本設(shè)計(jì)思想

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

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

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

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

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

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

2 遞歸剪切排樣算法設(shè)計(jì)

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

2.1 遞歸的方程式

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

1) 橫切

如圖1所示，從當(dāng)前板材的上邊剪切出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表示當(dāng)前板材x×y第1刀的切割方向?yàn)樨Q切。按此切割方式，可得到如下關(guān)系式：

(1)

圖1 條帶橫切

2) 豎切

如圖2所示，從當(dāng)前板材的左邊剪切出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表示當(dāng)前板材x×y第1刀的切割方向?yàn)樨Q切。按此切割方式，可得到如下關(guān)系式：

(2)

圖2 豎切

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

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

根據(jù)規(guī)范多級(jí)排樣方式和剪切沖裁下料工藝，從板材中剪切出條帶時(shí)只能是橫切和豎切兩種方式。對(duì)于尺寸為x×y的當(dāng)前板材，若第1刀的剪切方向選擇橫切，那么當(dāng)前板材遞歸排樣到底部時(shí)生成的條帶數(shù)和毛坯數(shù)是由剩余板材x×(y-l)和當(dāng)前產(chǎn)生的水平條帶x×l來決定的。若第1刀的剪切方向選擇豎切，那么當(dāng)前板材遞歸排樣到底部時(shí)生成的條帶數(shù)和毛坯數(shù)是由剩余板材(x-l)×y和當(dāng)前產(chǎn)生的垂直條帶y×l來決定的。對(duì)于每一刀剪切方向的選擇，是以當(dāng)前板材最終可生成的毛坯數(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ù)對(duì)單一尺寸矩形排樣進(jìn)行優(yōu)化。

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

① 當(dāng)N(L,W)>N0(L,W)時(shí)，令N0(L,W)=N(L,W)，M0(L,W)=M(L,W)，D0(L,W)=D(L,W)。

② 當(dāng)N(L,W)

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

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

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

(4)

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

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

設(shè)遞歸函數(shù)RecFun(x,y,NP,MP,D)用于求解板材尺寸為L(zhǎng)×W、毛坯尺寸為l×w的排樣方式最優(yōu)毛坯數(shù)，其中：參數(shù)NP表示剪切到當(dāng)前板材尺寸為x×y時(shí)已經(jīng)切出的毛坯數(shù)量；參數(shù)MP表示剪切到當(dāng)前板材尺寸為x×y時(shí)已經(jīng)切下的條帶數(shù)量；參數(shù)D表示一維數(shù)組D用于記錄條帶切割的方向，“0”表示條帶方向?yàn)樨Q直切割，“1”表示條帶方向?yàn)樗角懈睢?/p>

當(dāng)前最優(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)平臺(tái)，應(yīng)用 C++面向?qū)ο缶幊陶Z言開發(fā)了單一尺寸矩形毛坯排樣系統(tǒng)，以測(cè)試驗(yàn)證本文所述算法的有效性。初始調(diào)用遞歸函數(shù)RecFun()時(shí)，實(shí)參板材尺寸為L(zhǎng)×W、形式參數(shù)NP和MP對(duì)應(yīng)的實(shí)參值均為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)進(jìn)行優(yōu)化排樣，求出N0(L,W)、M0(L,W)及D0。

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

3 實(shí)驗(yàn)計(jì)算分析

3.1 毛坯數(shù)實(shí)驗(yàn)計(jì)算分析

1) 應(yīng)用例題

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

圖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)進(jìn)行優(yōu)化排樣，整個(gè)遞歸調(diào)用排樣過程，如圖4所示。

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

3) 排樣分析

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

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

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

3.2 條帶數(shù)實(shí)驗(yàn)計(jì)算分析

3.2.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

表3 隨機(jī)生成的20道例題

3.2.2 實(shí)驗(yàn)結(jié)果及其分析

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

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

表4 排樣實(shí)驗(yàn)結(jié)果

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

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

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

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

4 結(jié)束語

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

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

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

[3] 田雙.基于Sigma Nest的板材下料問題研究[J].現(xiàn)代機(jī)械,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].廣西大學(xué)學(xué)報(bào),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]工程設(shè)計(jì)學(xué)報(bào),2014,21(3):212-216.

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

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

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

(責(zé)任編輯陳 艷)

RecursiveAlgorithmAppliedStudyonaSingleRectangleBlanksUnconstrainedOptimalLayout

LI Haisheng

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

2017-05-04

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

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

李海生.遞歸算法在單一矩形毛坯無約束最優(yōu)排樣中的應(yīng)用[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，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