潘衛(wèi)平, 樊治平, 黃 敏

(1. 東北大學(xué) 工商管理學(xué)院, 遼寧 沈陽 110169; 2. 東北大學(xué) 信息科學(xué)與工程學(xué)院, 遼寧 沈陽 110819; 3.東北大學(xué) 流程工業(yè)綜合自動化國家重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽 110819)

制造業(yè)每年消耗大量硅鋼板材來生產(chǎn)電動機(jī)的定子和轉(zhuǎn)子.對于一個普通的電動機(jī)制造企業(yè),一年可能消耗幾千噸硅鋼板材[1].優(yōu)化下料方案對提高板材利用率具有重要意義[2-4].一般而言,定子和轉(zhuǎn)子屬于圓形件，經(jīng)常使用剪沖工藝將這些圓形件從硅鋼板材上切割下來.剪沖工藝包括剪切和沖壓兩個階段,在剪切階段用剪床將板材剪成條帶;在沖壓階段用沖床將條帶沖出圓形件.由于設(shè)備的限制,沖壓工藝要求條帶中圓形件按行排放,且只排放一種圓形件[5-6].

本文討論圓形件二維板材剪沖下料問題:采用剪沖工藝將原料板材切割出若干種已知尺寸和數(shù)量的圓形件,在滿足圓形件的需求量前提下使得消耗的板材總面積最小.

針對二維板材剪切下料問題,目前多數(shù)文獻(xiàn)研究的是零件為矩形的情形[7-10],對零件為圓形的情形研究相對較少.對零件為圓形的情形,文獻(xiàn)[1]提出了應(yīng)用T型排樣方式的下料方案,這種排樣方式將板材分成兩個段,一個段中排放水平條帶,另一個段中排放豎直條帶.構(gòu)造背包算法生成條帶在段上的布局方式,按照板材排樣價值最大原則確定板材的兩段劃分.采用列生成算法調(diào)用上述排樣方法擇優(yōu)選擇一組排樣方式構(gòu)成下料方案.文獻(xiàn)[2]提出了應(yīng)用直切排樣方式的順序啟發(fā)式算法.文獻(xiàn)[4]提出了一種基于四塊排樣方式的求解算法,這種排樣方式將板材分成四個塊,塊中排放方向和長度均相同的條帶.采用動態(tài)規(guī)劃生成條帶在塊中的布局方式,采用窮舉法確定板材的最優(yōu)四塊劃分.最后將上述排樣算法與列生成相結(jié)合求解下料方案.上述文獻(xiàn)下料算法的板材利用率和計(jì)算速度有待進(jìn)一步提高.文獻(xiàn)[11]將四塊排樣方式和順序價值修正啟發(fā)式相結(jié)合,提出了啟發(fā)式排樣算法.

本文提出一種新的基于四塊排樣方式的下料算法,采用遞歸技術(shù)確定圓形件在單張板材上的排樣方式,同時運(yùn)用隱式枚舉剔除不必要的分支;采用列生成算法調(diào)用該排樣算法生成下料方案,對小數(shù)解進(jìn)行圓整操作得到更加精確的下料方案.采用文獻(xiàn)例題和實(shí)際生產(chǎn)實(shí)例測試本文算法,并與文獻(xiàn)算法進(jìn)行對比,驗(yàn)證本文算法的有效性.

本文的創(chuàng)新點(diǎn)主要有:①構(gòu)造了四塊排樣方式的遞歸生成算法；②提出了規(guī)范尺寸概念,在排樣時候只需考察規(guī)范尺寸的塊,可大幅提高排樣算法的計(jì)算速度；③在生成下料方案時對下料方案的小數(shù)解進(jìn)行了圓整操作,可進(jìn)一步減少板材使用量.

1 問題描述和四塊排樣方式

1.1 問題描述和模型

二維板材圓形件剪沖下料問題:用剪沖工藝將尺寸為L×W(L為長,W為寬)的板材剪沖出m種圓形件,其中第i種圓形件的直徑為di,需求量為ri,i=1,…,m;問題目標(biāo)為在滿足所有圓形件的需求量前提下使得消耗的板材總面積最小.

令A(yù)為下料方案耗費(fèi)的板材總面積;下料方案包含α種排樣方式;Q=[q1,…,qα],其中qj為第j個排樣方式對應(yīng)的板材的面積;P為m行α列矩陣,其中元素pij表示第j種排樣方式包含第i種圓形件的個數(shù);R=[r1,…,rm]T為圓形件的需求量向量,元素ri表示第i種圓形件的需求量;X=[x1,…,xα]T,其中xj表示按照第j種排樣方式切割的板材張數(shù);N為正整數(shù)集合.則該問題的數(shù)學(xué)模型為

(1)

模型(1)優(yōu)化目標(biāo)為下料方案切割的板材總面積最小.

1.2 條 帶

條帶中排放一行或多行同種圓形件[1].圖1給出了沖壓階段所需的條帶的幾何特征,其中D

圖1 條帶幾何特征

為圓形件的直徑,g為沖壓余量.連接三個相鄰的圓形件的圓心組成一個等邊三角形,其邊長為D+g.本文不妨令g=0,這不影響本文算法的通用性,如果g>0,可以在排樣時將圓形件的直徑設(shè)為D+g,不影響排樣方式的質(zhì)量.

1.3 塊

塊中排放一組具有相同方向和長度的條帶.稱排放水平條帶的塊為X向塊,排放豎直條帶的塊為Y向塊.

塊的價值為塊中排放的條帶的價值之和.設(shè)f(x,y)為塊x×y(長為x,寬為y)的價值,其中x≤L,y≤W.當(dāng)塊為X向塊時,設(shè)其價值為fX(x,y);當(dāng)塊為Y向塊時,設(shè)其價值為fY(x,y).通過如下遞歸模型[13-15]計(jì)算塊的價值.

(2)

(3)

f(x,y)=max{fX(x,y),fY(x,y)}.

(4)

1.4 四塊方式

四塊排樣方式由四個矩形塊組成[18],每個塊中排放具有相同長度和方向的條帶,每根條帶中按行排放一種圓形件.剪沖過程:首先用剪床將板材剪成四個塊,然后將塊剪成條帶,最后用沖床將條帶沖壓出所需要的圓形件.四塊劃分過程：首先用一條父分界線將板材劃分為2個子板,然后用兩條垂直于父分界線的子分界線將2個子板劃分為4個塊.如圖2所示,當(dāng)父分界線為豎直方向時,稱這種四塊方式為X向四塊方式;當(dāng)父分界線為水平方向時,稱這種四塊方式為Y向四塊方式.

設(shè)V為四塊排樣方式的價值,VX和VY分別為X向四塊排樣方式和Y向四塊排樣方式的價值.則有

(5)

(6)

V=max(VX,VY).

(7)

式(5)、式(6)通過枚舉父分界線和子分界線的位置,得到所有可能的四塊組合,選擇排樣價值最大的一個作為最優(yōu)四塊方式.選擇X向四塊方式和Y向四塊方式價值較大者作為最終的四塊排樣方式.式(5)中x為父分界線位置,y1和y2分別為兩條子分界線的位置,如圖2a所示.同理,式(6)中y為父分界線位置,x1和x2分別為兩條子分界線的位置,如圖2b所示.

2 遞歸和隱式枚舉排樣算法

2.1 規(guī)范尺寸

對于包含第i種圓形件長度為x,寬度為sj的條帶,如果v(x,sj)>v(x-1,sj),則稱x為該條帶的規(guī)范長度.如果條帶只包含一行圓形件,則條帶的規(guī)范長度為qdi,其中0≤q≤?max(L,W)/di」.如果條帶中包含的圓形件行數(shù)不止一行,則條帶的規(guī)范長度為qdi和「(q+0.5)di?,其中「(q+0.5)di?≤max(L,W).稱具有規(guī)范長度的條帶為規(guī)范條帶.

令H={h1,…,hβ}為所有條帶的寬度和規(guī)范長度集合,其中β為集合的元素個數(shù).令A(yù)為塊的規(guī)范長度集合,B為塊的規(guī)范寬度集合,ni為非負(fù)整數(shù),其中i=1,…,β.定義A和B:

(8)

(9)

即塊的規(guī)范長度為條帶的寬度和條帶的規(guī)范長度的線性組合加上0,L兩個元素.塊的規(guī)范寬度為條帶的寬度和條帶的規(guī)范長度的線性組合加上0,W兩個元素.將規(guī)范尺寸按照升序排列,即A={a1,…,a|A|},B={b1,…,b|B|},其中|A|為集合A的元素個數(shù),|B|為集合B的元素個數(shù), 0=a1<…

由于對稱性,在生成X向四塊排樣方式過程中,父分界線的位置x只需從0隱式枚舉到「L/2?,子分界線位置y1和y2只需從0隱式枚舉到「W/2?.記ar為板材規(guī)范長度集合的樞紐元素,bt為板材規(guī)范寬度集合的樞紐元素,它們滿足如下條件:ar>「L/2?且ar-1<「L/2?,其中1「W/2?且bt-1<「W/2?,其中1

2.2 塊生成算法

X向塊包含具有相同長度和方向的水平條帶,Y向塊包含具有相同長度和方向的豎直條帶.塊生成算法確定塊中條帶的優(yōu)化布局,得到價值最大的塊,即最優(yōu)塊.生成最優(yōu)塊的算法步驟:

步驟1 令i=0.

步驟2 令x=ai.采用遞歸模型(2),一次性求出所有長度等于x的X向塊的價值fX(x,y),其中y∈B.

步驟3 令i=i+1.如果i≤|A|,則轉(zhuǎn)步驟2.

步驟4 令j=0.

步驟5 令y=bj.采用遞歸模型(3),一次性求出所有寬度等于y的Y向塊的價值fY(x,y),其中x∈A.

步驟6 令j=j+1.如果j≤|B|,則轉(zhuǎn)步驟5.

步驟7 令i=0.

步驟8 令j=0.

步驟9 令x=ai,y=bj.如果fX(x,y)>fY(x,y),則令f(x,y)=fX(x,y),否則令f(x,y)=fY(x,y).

步驟10 令j=j+1.如果j≤|B|,則轉(zhuǎn)步驟9.

步驟11 令i=i+1.如果i≤|A|,則轉(zhuǎn)步驟8.

步驟12 輸出所有尺寸的最優(yōu)塊的價值f(x,y),其中x∈A,y∈B.

算法的終止條件為j=|B|+1且i=|A|+1.步驟1～步驟3求出所有尺寸的X向塊的價值;步驟4～步驟6求出所有尺寸的Y向塊的價值;步驟7～步驟11,比較相同尺寸的X向塊和Y向塊的價值,選擇價值較大者作為最優(yōu)塊.

2.3 四塊方式生成算法

本節(jié)僅考慮X向四塊方式的生成;對于Y向四塊方式,可將板材的長度和寬度對換,變成X向四塊方式進(jìn)行處理.生成最優(yōu)X向四塊方式的算法步驟如下:

步驟1 令VX=0,V1=0,V2=0.

步驟2 令i=0.

步驟3 令x=ai.

步驟4 令j1=0.

步驟5 令y1=bj1.令U1=f(x,B(W-y1))+f(x,y1),如果V1

步驟6 令j1=j1+1,如果j1≤t,則轉(zhuǎn)步驟5.

步驟7 令j2=0.

步驟8 令y2=bj2.令U2=f(A(L-x),B(W-y2))+f(A(L-x),y2),如果V2

步驟9 令j2=j2+1,如果j2≤t,則轉(zhuǎn)步驟8.

步驟10 令UX=V1+V2,如果VX

步驟11 令i=i+1,如果i≤r,則轉(zhuǎn)步驟3.

步驟12 輸出X向四塊方式的價值VX.

算法的終止條件為i=r+1.

2.4 四塊排樣方式生成算法

本文排樣算法,首先得到條帶的規(guī)范長度和寬度以及條帶的價值,然后得到塊的規(guī)范尺寸并確定條帶在塊中的優(yōu)化布局,最后確定板材的最優(yōu)四塊劃分.算法步驟:

步驟1 根據(jù)2.1節(jié)求出條帶的規(guī)范長度.

步驟2 根據(jù)1.2節(jié)得到條帶的寬度集合S={s1,…,sM},求出所有規(guī)范條帶x×si的價值v(x,si),其中x=0,…,max(L,W),1≤i≤M.

步驟3 根據(jù)2.1節(jié)得到塊的規(guī)范長度集合A和規(guī)范寬度集合B.

步驟4 調(diào)用X向四塊方式生成算法生成最優(yōu)X向四塊方式,并得到其價值VX.

步驟5 調(diào)用Y向四塊方式生成算法生成最優(yōu)Y向四塊方式,并得到其價值VY.

步驟6 選擇X向四塊方式和Y向四塊方式中的價值較大者作為最優(yōu)四塊排樣方式,并得到其價值V=max(VX,VY).

步驟1至步驟3時間復(fù)雜度為O(m(|A|+|B|)),空間復(fù)雜度為O(|A|+|B|);步驟4至步驟5時間復(fù)雜度為O(m|A‖B|),空間復(fù)雜度為O(|A‖B|);步驟6時間復(fù)雜度為O(|A‖B|),空間復(fù)雜度為O(1).故算法總的時間復(fù)雜度為O(m|A‖B|),空間復(fù)雜度為O(|A‖B|).

3 列生成下料算法

上節(jié)排樣算法可與列生成算法相結(jié)合構(gòu)成下料算法[8-10].本文下料問題的線性規(guī)劃模型為

(10)

模型(10)中,Z為下料方案耗費(fèi)的板材總面積;Q=[q1,…,qm],其中qj為第j個排樣方式對應(yīng)的板材的面積;U為m行m列矩陣,其中元素uij表示第j種排樣方式包含第i種圓形件的個數(shù);R=[r1,…,rm]T為圓形件的需求量向量,元素ri表示第i種圓形件的需求量;X=[x1,…,xm]T,其中xj表示按照第j種排樣方式切割的板材張數(shù).

采用如下步驟求解上述模型.

步驟1 確定初始可行解.令矩陣U為單位矩陣,則初始可行解X=R,即第j(j=1,…,m)種排樣方式只包含一個第j種圓形件,不包含其他圓形件.

步驟2 計(jì)算圓形件的當(dāng)前價值向量.令V=QU-1=[v1,…,vm]為圓形件的當(dāng)前價值向量.

步驟3 尋找能改善目標(biāo)函數(shù)的下料方案.用P=[p1,…,pm]T表征當(dāng)前考察的排樣方式,其中元素pi表示排樣方式P中包含圓形件i的個數(shù).設(shè)排樣方式P對應(yīng)的板材的面積為q.由線性規(guī)劃理論可知,如果q-VP<0,則當(dāng)前排樣方式P能改善下料方案(P可通過2.4節(jié)排樣算法求得),用P替換矩陣A的第k(k由單純型法確定)列,令qk=q,轉(zhuǎn)步驟2.否則,不存在能改善模型(10)目標(biāo)函數(shù)的排樣方式,當(dāng)前下料方案即為最優(yōu)下料方案,按照每種排樣方式切割的板材張數(shù)向量為X=[x1,…,xm]T=U-1R.

步驟4 令xi=「xi?,i=1,…,m.

步驟5 令i=1.

步驟6 令xi=?xi」,如果UX

步驟7 令i=i+1,如果i≤m,則轉(zhuǎn)步驟6.

步驟8 得到整數(shù)解X.

算法的終止條件為i=m+1.步驟1～步驟3得到的下料問題的解為小數(shù)解,即按照每種排樣方式切割的板材張數(shù)可能為小數(shù)不滿足實(shí)際生產(chǎn)要求.步驟4～步驟8對小數(shù)解進(jìn)行圓整操作,得到整數(shù)解.

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

用C#實(shí)現(xiàn)本文算法,實(shí)驗(yàn)所用計(jì)算機(jī)為CPU 主頻2.4 GHz,內(nèi)存4 GB.通過文獻(xiàn)隨機(jī)例題和實(shí)際生產(chǎn)實(shí)例將本文算法與4種文獻(xiàn)算法進(jìn)行對比.

4.1 隨機(jī)例題測試

采用文獻(xiàn)[1]的20道隨機(jī)例題.板材尺寸為2 000 mm×1 000 mm,剪沖工藝的沖壓余量為8 mm,每根條帶中最多允許排放3行圓形件.文獻(xiàn)[1]算法和文獻(xiàn)[4]算法平均每道例題耗費(fèi)的計(jì)算時間分別為0.73 s和0.96 s.本文算法平均每道例題耗時0.31 s.文獻(xiàn)[1]算法、文獻(xiàn)[4]算法和本文算法下料方案的平均板材利用率分別為71.73%,71.90%和72.22%.本文算法下料方案板材利用率比文獻(xiàn)[1]算法和文獻(xiàn)[4]算法分別高0.49%和0.32%.

4.2 實(shí)例1

采用文獻(xiàn)[11]的電機(jī)制造廠實(shí)例,板材尺寸為3 000 mm×1 500 mm,圓形件為8種,剪沖工藝余量為6 mm,每根條帶中最多允許排放3行圓形件,每種圓形件的尺寸在區(qū)間[253 mm, 403 mm]取值,需求量(單位:個)在區(qū)間[1 000, 2 600]取值,具體可參見文獻(xiàn)[11]的表2.文獻(xiàn)[2]算法、文獻(xiàn)[11]算法和本文算法的下料方案板材利用率分別為69.62%,74.16%和75.66%.可見本文算法比文獻(xiàn)[2]算法和文獻(xiàn)[11]算法分別高6.04%和1.50%.

4.3 實(shí)例2

某電動機(jī)廠需要用尺寸為2 440 mm×1 220 mm的板材剪沖出15種圓形件,沖壓工藝余量為0,每根條帶中最多允許排放3行圓形件.圓形件的直徑(單位:mm)分別為:180,205,226,260,280,320,342,360,375,390,400,420,440,455,485;圓形件的需求量(單位：個)分別為:50 000,10 000,11 000,7 000,20 000,45 000,30 000,8 000,9 000,50 000,30 000,10 000,5 000,10 000,10 000.

文獻(xiàn)[1]算法和文獻(xiàn)[4]算法計(jì)算時間分別為2.69 s和3.47 s,下料方案板材利用率分別為76.05%和76.83%.本文算法求解該實(shí)例,算法計(jì)算時間為1.35 s,共使用板材11 780張,板材利用率為77.54%.

5 結(jié) 語

構(gòu)造了圓形件條帶在塊中布局的遞歸算法,給出了塊的規(guī)范尺寸用以減少算法計(jì)算量.然后用列生成算法迭代調(diào)用上述排樣算法生成下料方案,并對小數(shù)解進(jìn)行圓整操作得到更加精確的下料方案.實(shí)驗(yàn)結(jié)果表明,所提下料算法在計(jì)算時間和提高板材利用率方面均有效.本文下料算法的框架是將單張板材上圓形件數(shù)量無約束的剪沖排樣算法與列生成算法相結(jié)合.設(shè)計(jì)單張板材上圓形件數(shù)量有約束的剪沖排樣算法,并將其與順序啟發(fā)式算法相結(jié)合形成下料算法可作為今后的研究內(nèi)容.