鋼構(gòu)件的優(yōu)化排料問題(共21頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上鋼構(gòu)件的優(yōu)化排料問題1、 問題的重述1.1 背景在當(dāng)今激烈的市場競爭中, 降低生產(chǎn)成本、提高生產(chǎn)效率和增強(qiáng)對市場的應(yīng)變能力, 是企業(yè)保持競爭力的主要實現(xiàn)手段。在鋼構(gòu)件制造產(chǎn)品的生產(chǎn)過程中，依照產(chǎn)品零件尺寸從板料中截取大小適當(dāng)?shù)牧慵^程稱之為排料，也稱之為下料。排料是鋼構(gòu)件制造的第一道工序。在這道工序中，不同的排料方案具有不同的材料利用率，而原材料的利用率直接影響產(chǎn)品的成本。材料費(fèi)用是制造企業(yè)主要的生產(chǎn)成本, 一般占總成本的 60% 80% , 在大批量生產(chǎn)中, 材料的利用率即使提高 1% , 所創(chuàng)造的經(jīng)濟(jì)效益也相當(dāng)可觀。據(jù)調(diào)查,優(yōu)化下料后,制造企業(yè)材料利用率可平均提高

2、 5% 10%。另外由于切割工藝的要求，切割只能實行“一刀切”的工藝（在整料或余料中，從一邊的某點到另外一邊某點的連線一次切割，但可以在切割下來的板料中再次切割）。板材的利用率就是所有零件面積之和與在一刀切工藝后繼續(xù)切割的那部分板材面積的比值。1.2 問題對于第一問，對1張板料和若干規(guī)則形狀零件，求如何在板料中擺放零件使其板料的利用率最高。規(guī)則形狀零件即指矩形零件。其描述一般只需用矩形的長和寬。規(guī)則形狀零件的排料問題的實質(zhì)是研究如何組合零件擺放問題，使得在整個原料上擺放大量的不同長和寬的零件產(chǎn)生的廢料最少、整料和余料的利用率最高。排放時，其零件間的搭接關(guān)系的處理相對容易，只需考慮長、寬兩個因素

3、（含預(yù)留的損耗量）。板材大小:2350*900【1張】。表1是九個規(guī)則形狀零件的具體規(guī)格。 表1零件一二三四五長（mm）350350500500500寬（mm）300200240210350個數(shù)22222零件六七八九長（mm）300250500500寬（mm）250200400200個數(shù)2222對于第二問，對1張板料和若干不規(guī)則形狀零件，如何在板料中擺放零件使其板料的利用率最高。與第一問類似，但是此時需要切割出來的零件不具有矩形般對邊平行的條件，切割較為麻煩，同時可能會造成更多邊角料的產(chǎn)生，降低板料的利用率。圖1和表2是題目要求的兩種不規(guī)則零件的具體形狀和規(guī)格。板材大小:2380*1630 【

4、1張】。 表2零件一二個數(shù)1414 圖1零件一 零件二對于第三問，考慮到實際的切割過程中，一張板料并不能滿足所有零件的生產(chǎn)需求，故而要求設(shè)計對2張板料和若干規(guī)則形狀零件，如何在板料中擺放零件使其板料的利用率最高。還有一點與問題一不同，即各零件要求生產(chǎn)的個數(shù)有所改變。板材大小:4550*1630 【2張】。具體見下表3。 表3零件一二三四五個數(shù)40566零件六七八九個數(shù)42242、符號規(guī)定與模型假設(shè)2.1 符號規(guī)定符號表示意義L板材的長度W板材的寬度hi矩形件的長，i=1，2，3 w矩形件的寬，i=1，2，3 ni矩形件的數(shù)量，i=1，2，3 板材利用率Ri零件的種類，i=1，2，3 2.2 模

5、型假設(shè)1. 切割機(jī)垂直切割，不考慮料板的厚度，即將問題轉(zhuǎn)化為二維平面問題；2. 切割不會導(dǎo)致料板的長度或?qū)挾葴p小，忽略切割損耗；3. 切割方式為一刀切，即在整料或余料中，從一邊的某點到另外一邊某點的連線一次切割；4. 忽略切割效率，本文著眼點在于料板利用率的提高；5. 對于問題二中的六邊形，可看作是矩形一角刪去一個150150的正方形，而這一步驟利用一刀切不可能實現(xiàn)，故而假設(shè)六邊形ABCDEF當(dāng)作五邊形ABCDE對待（圖2），該零件的后續(xù)加工后文不予考慮。 圖23、問題分析本題目三個問題所研究的是一刀切下料, 問題一和問題三屬于二維規(guī)則圖形的優(yōu)化排料問題，問題二屬于二維不規(guī)則圖形的優(yōu)化排料問題

6、。排料問題是典型的優(yōu)化組合問題，具有很高的計算復(fù)雜性，屬于NP完全問題?！耙坏肚小钡膶嶋H現(xiàn)象給了本問題一個最基礎(chǔ)的約束，使得排樣有了一個這樣一個基礎(chǔ)：每次切割都將板材一分為二。圖 3 給出了一刀切下料與非一刀切下料的比較。圖3問題一和問題三要求制作的零件規(guī)格有9種, 因此屬于多零件下料問題。多種零件, 需要解決如何選擇將零件合理高效的布置在板材上。本文的研究目的是在這些約束條件下實現(xiàn)優(yōu)化排樣, 提高板材利用率。排樣目標(biāo)為: 盡可能提高一塊板的利用率。排料需要滿足的基本約束條件有：零件之間互不重疊；零件的排布不得超出板材邊緣；滿足一刀切條件。4、模型建立4.1 模型的準(zhǔn)備由于問題一和二要求在一張

7、料板上規(guī)劃，問題三要求在兩張規(guī)格相同的料板上規(guī)劃，故而在料板數(shù)量上簡化模型，僅考慮在一張規(guī)格已知的料板進(jìn)行排料規(guī)劃。對于二維排料問題，排料方式要滿足零件長，寬方向上的套裁。將N個零件記為R1、R2、Rn合理的排布在板材A中，其中滿足： Max（畏）=Max（j=0NSprA*100%） （1.1） 且滿足： （1）RrA j=1,2N,（2）RjRk= （jk ， j k=1,2N） (1.2)其中畏為排料的材料利用率，應(yīng)滿足畏最大的原則。Spj為第j個板材Rj的零件面積，A為第一次一刀切后繼續(xù)用于一刀切的原料板材的面積，也即布局板材所消耗的原料面積，一般有A=A0+A1+A2 （其中A0=r

8、=0NSpr，A1為工藝廢料，A2為結(jié)構(gòu)廢料）。從式（1.1）中可以看出，理論上若廢料（包括工藝廢料和結(jié)構(gòu)廢料）面積減至0，材料的利用率能夠接近1，但該理論值在實際生產(chǎn)中無法達(dá)到。工藝廢料由行業(yè)的工藝要求產(chǎn)生，如切割損耗和余料，本題在建模過程中暫不考慮實際生產(chǎn)中的切割損耗。結(jié)構(gòu)廢料由具體板材的結(jié)構(gòu)形狀所決定。在生產(chǎn)中結(jié)構(gòu)廢料無法控制，要提高材料的利用率只有從減少工藝廢料入手，通過采用更合理的排料方案，減少余料（工藝廢料）。4.2 模型的建立4.2.1問題一模型的建立設(shè)共有M張面積大小都為A的板材，N類目標(biāo)零件板材。記板材的集合為：（X=Wi，H i iM，零件集合為：Y=wj，hj jN j類

9、零件的數(shù)量為nj, 板材i上j 類零件的數(shù)量為nji，已知第k 個j 類零件在板材上的排列位置可以由其左下角坐標(biāo)與右上角坐標(biāo)唯一確定, 可記第k個j 類零件在下料板材i上的左下角坐標(biāo)為(x0jki，y0jki), 右上角坐標(biāo)記為(x1jki，y1jki) 零件k 在0 縱排下料板材i上的排列方式記為pjki= ，目標(biāo)是最大化板材的利用率。 1 橫排根據(jù)以上分析，將多板材下料問題用數(shù)學(xué)模型表示為：Max（畏）=Max（j=0NSprA*100%） （1.3）prA j=1,22N, (1.4）pjpk= （jk j k=1,22N） （1.5）j，kmaxx1jkiWi， （1.6）j，kmax

10、y1jkiHi， （1.7）1Inji=nj （1.8）式(1.3)為目標(biāo)函數(shù)，表示最大板材利用效率；式(1.4)為零件規(guī)格約束；式(1.5)保證零件互不重疊；式(1.6)和式(1.7)為板材規(guī)格約束，式(8)為零件數(shù)量約束。4.2.2 問題二模型的建立該問屬于二維不規(guī)則零件排樣問題2，此類問題的求解主要有兩種思路：一種是對這類問題直接在原材料上進(jìn)行擺放；另一種則是將不規(guī)則零件轉(zhuǎn)化為規(guī)則矩形件，然后按照矩形件進(jìn)行優(yōu)化排樣。4如果將不規(guī)則零件排放在矩形形狀的板材上，其在板材上的位呈由三個參數(shù)決定，這三個參數(shù)是該零件的一個給定點在板材上的坐標(biāo)（x,y）和該零件的排放角度，這三個參數(shù)確定后，該零件的

11、其他各頂點參數(shù)均可通過這三個參數(shù)計算出來。5首先定義以下參數(shù)：排樣零件；排樣零件圖形；排樣零件給定點的坐標(biāo)。零件在板材上的排樣定位過程如下：先將該零件的給定點在板材上平移至，然后再將該零件以為軸作角度為的旋轉(zhuǎn)，這時零件在板材上的方向可表示為。則零件排樣優(yōu)化的模型為：其中L為板材的長，W為板材的寬；N為排樣零件的數(shù)目；為排樣零件的面積；變量表示零件在板材上的排樣狀態(tài)，如果可以排放則取1，不能排放則取0。排樣的約束條件如下：其中第一式約束了任意兩個零件互不重疊；第二，三式約束了零件中任意點的坐標(biāo)都必須在排樣材料范圍內(nèi)，不能超出板材之外。我們對于問題二的求解采用第二種方法，由于問題二給出的五邊形和六

12、邊形并不是特別復(fù)雜的多邊形，同時五邊形具有直角。我們采用窮舉法列出了6種較為常見排列方案，在這里對每種方案的利用率進(jìn)行討論，得出最佳矩形件優(yōu)化方案。矩形面積：利用用率： .5/*100%=82.25% 方案一（圖4）矩形面積：=399*617=利用效率：=/*100%=90.01% 方案二（圖5）矩形面積：=411*558=利用效率：=/*100%=96.41%方案三（圖6）矩形面積：=411*664=利用效率：=/*100%=83.56% 方案四（圖7）矩形面積：=462*519=利用效率：=/*100%=92.21%方案五（圖8）矩形面積：=400*350=利用效率：=/*100%=91.

13、96%方案六（圖9）經(jīng)過綜合分析，我們擬采用方案三和方案六組合切割。至此，將不規(guī)則形狀零件的排料問題簡化為矩形零件的排料問題，可參照問題一模型來求解。4.2.3 問題三模型的建立與前兩問有所不同的是，問題三要求在兩張規(guī)格相同的料板上進(jìn)行排料。經(jīng)過計算得知，故而我們在問題一模型的基礎(chǔ)上，又可分兩種方案進(jìn)行比較：（1）在一張板材上進(jìn)行排板，看是否可以節(jié)省一整張料板；（2）在兩張板材上進(jìn)行排版，排板順序為兩張同時進(jìn)行，以求獲得更大的剩余的料板整體面積。4.3 算法模型4.3.1算法結(jié)構(gòu)框圖 圖104.3.2 排樣算法基本規(guī)則：（1）插入規(guī)則 大邊尺寸，指板材或者零件長度和寬度的較大邊尺寸。 最大零件

14、，指大邊尺寸最大的待處理零件。 最小空穴，指大邊尺寸最小的待下料板材。啟發(fā)式算法6將待下料零件按大邊尺寸降序排序，將原料板材按大邊尺寸升序排序, 并規(guī)定新一輪的下料排樣總是選取待下料零件中的最大零件，搜索空穴列表，從滿足零件下料尺寸的空穴中選擇最小空穴1作為下料板材。(2) 放置規(guī)則靠左靠下在求解初始排樣方案中，對于給定空穴，規(guī)定從待排零件中選擇高度最低、寬度最大的零件靠左靠下放置。(3) 轉(zhuǎn)向規(guī)則整除求余設(shè)空穴小邊為x ( x= min( W，L)，W和L分別為空穴的寬度和長度)，按插入規(guī)則和放置規(guī)則選定的零件寬度為w長度為l，則x與w，l之間滿足以下線性關(guān)系: x= aw + l1 ，x=

15、 bh + d2。若d1 d2 ,則按照w|x的方式放置零件，否則按照l|x的方式放置。（4）切割線替換規(guī)則1對于任意可行解, 若存在另一條切割線滿足第一條切割線的切割條件, 則以這條切割線為第一條切割線所形成的排樣方案與原解相同。證明: 如圖11所示, 已知區(qū)域 O 存在以 x 為第一條切割線的可行解 Ix, 則 O 中存在局部區(qū)域P, 使得P 中以 x 為第一條切割線的解 ioxI,現(xiàn)已經(jīng)找到另外一條滿足性質(zhì) 1 的切割線 y, 需要證明 Iy= Ix 。此時切割線 y 有兩種情況: 一種為 y平行于 x, 另一種為 y 垂直于 x。下面分別就這兩種情況進(jìn)行證明。（1） y平行于x。x 將

16、 O 劃分為 A C 和 B 兩部分, y將O 劃分為 A 和 B C 兩部分。易知iACI且iBI, 同理iAiAC 且 iCiAC , 根據(jù)集合的傳遞性, 有iAI且 iCI 。所以以 y 為第一條切割線所形成的排樣方案與原解相同。（2） y垂直于x。 x 將 O 劃分為 A D 和 B C 兩部分, y 將 O 劃分為 C D和 A B 兩部分。易知： iADI 且 iBCI, 同理iAiAD 且 iDiAD , iBiBC且 iCiBC , 根據(jù)集合的傳遞性, 有 iAI, iBI, iCI, iDI。所以以 y 為第一條切割線所形成的排樣方案與原解相同。切割線替換定理得證。 圖114

17、.3.3排樣優(yōu)化思想：采用二叉樹的生成過程來描述板材的分割過程，則生成的二叉樹就表示一個排樣結(jié)果，即得到一個全局排樣解。用I=N，G|N=nj,G=gj，j=1，2， 表示一個全局排樣解，其中N表示排樣解中各類零件的個數(shù)集合；G表示排樣解中零件的規(guī)格集合。i=Ni，Gi|NiN，GiG是I的局部區(qū)域，則稱i是I的一個局部解。一刀切的切割特點決定了滿足一刀切約束的排樣解具有以下條件:條件1 排樣解中的第一條切割線必須滿足：長度等于分割區(qū)域中與其平行的那條邊的長度，且不影響任意零件的完整性。條件2 設(shè)I為滿足一刀切的全局解，對于I中的任意局部解i，i一定滿足一刀切。條件3 對于任意可行解，若存在另

18、一條切割線滿足第一條切割線的切割條件，則以這條切割線為第一條切割線所形成的排樣方案與原解相同。4.4下料優(yōu)化問題的二叉樹算法的構(gòu)造二叉樹是一種常用的空間數(shù)據(jù)結(jié)構(gòu)，因其結(jié)構(gòu)簡單，操作方便、快速而廣泛應(yīng)用于數(shù)據(jù)的排序和計算內(nèi)部尋址等方面。本文主要基于VC+6. 0開發(fā)平臺，對零件排料涉及到的二叉樹算法進(jìn)行了編寫。在排樣過程中，由于一刀切的特性，1塊矩形區(qū)域劃分后，可得到2塊小的矩形區(qū)域。在這2塊矩形區(qū)域繼續(xù)進(jìn)行排樣，就會得到4塊矩形區(qū)域。不斷進(jìn)行下去，這個排樣過程就是一種二叉樹的結(jié)構(gòu)。本文將二叉樹用于矩形物體布局空間狀態(tài)的表達(dá)，具體應(yīng)用如下:已知一個布局空間的矩形區(qū)域，按權(quán)值從可選布局物體中選擇一

19、個相對于該矩形區(qū)域來說是最優(yōu)的布局物體A，并將其定位于該矩形區(qū)域的左下角。這樣原布局空間變成了一個形區(qū)域。將這個形區(qū)域分成圖12所示2個矩形A1和A2，分別用根結(jié)點的左、右2個子結(jié)點表示。這樣，剩余的布局空間就變成了2個獨立的布局空間，分別對這2個布局空間重復(fù)上述過程，直至沒有可選布局物體滿足要求時停止分解。圖12 其中，每個圓圈和數(shù)字代表二叉樹的節(jié)點，代表在矩形中進(jìn)行了一次子排樣。根節(jié)點1為板材，進(jìn)行一次子排樣后，會生成2塊空白矩形，相應(yīng)產(chǎn)生2個節(jié)點:節(jié)點2和節(jié)點3。節(jié)點2的空白矩形進(jìn)行一次子排樣后，又會產(chǎn)生2個新的節(jié)點:節(jié)點4和節(jié)點5。節(jié)點之間的關(guān)系如圖13所示：圖13二叉樹路徑中的標(biāo)號x

20、i表示空白矩形分割方式。以節(jié)點1為例，定義X1=0時，對節(jié)點1的進(jìn)行子排樣后的空白區(qū)域進(jìn)行橫劃分。X1=1時，對剩余空白區(qū)域的劃分為豎劃分。顯然，當(dāng)x1取值不同時，生成的節(jié)點2, 3中的原始空白矩形也不一樣，更影響了后面的節(jié)點和排樣結(jié)果。具體步驟如下:1. 定義零件，二叉樹節(jié)點的結(jié)構(gòu)體，將板材和零件的長、寬與數(shù)量放置到數(shù)組中,并將零件按照長度從高到低，相同長度按照寬度從寬到窄進(jìn)行排序。如下所示：/定義待排零件struct ORIGINAL_SQUAREint length; /長int width; /寬int num; /數(shù)量;/定義已排零件struct SQUAREint length;

21、/長int width; /寬int num; /數(shù)量;/定義二叉樹節(jié)點struct NODE struct SQUARE blankSquare; /排布前的空白矩形struct SQUARE *filledSquare; /空白矩形內(nèi)排布的一列矩形int fillesSquareNumber; /排布的矩形數(shù)目int originalIndex; /排布的是哪個初始矩形int remainLength; /順著排布方向無法排布的矩形的長int remainWidth; /順著排布方向無法排布的矩形的寬struct NODE *lastNode;/上個節(jié)點的地址;/構(gòu)建數(shù)組，存儲數(shù)據(jù)，冒泡排

22、序#includeusing namespace std;int main(int argc,char *argv)/建立九行三列的二維數(shù)組int row,col;int i,n,k;int* p; /p是一個二維int數(shù)組row=9;col=3;p = new int*row; /創(chuàng)建行指針 for(i=1; i=row;i+)pi = new intcol; /為每一行分配空間 coutn請按順序依次輸入零件的長,寬與數(shù)量,并用空格隔開:n;for(n=1;n=row;n+) for(k=1;kpnk;coutn您輸入的是:n;coutn長度t寬度t數(shù)量n;for(n=1;n=row;n+

23、) for(k=1;k=col;k+) cout pnkt; cout n;cout按照零件長度從高到低,相同長度下寬度從寬到窄排序得:n;for(n=1; n=row; n+) /for循環(huán)進(jìn)行冒泡排序 for(int j = n+1;j =row;j+) if(pn1 pj1) int t = pn1; pn1 = pj1; pj1 = t; int r = pn2; pn2 = pj2; pj2 = r; int w = pn3; pn3 = pj3; pj3 = w; if(pn1 = pj1&pn2 pj2) int t = pn2; pn2 = pj2; pj2 = t; int

24、w = pn3; pn3 = pj3; pj3 = w; coutn長度t寬度t數(shù)量n;for(n=1;n=row;n+) for(k=1;k=col;k+) cout pnkt; cout n; cout endl; return 0;2.一張板材上的每次下料都優(yōu)先選擇長度最長，寬度最寬的零件靠左、靠下排列。此處選擇權(quán)值法，引入權(quán)值公式計算板材的利用率：Int w=1*u+2*t + 3*r+ 4*a其中，u表示單個待排零件占空白區(qū)域比例; t表示一次子排樣下的所有零件面積之和占空白區(qū)域比例; r表示剩余區(qū)域局部矩形的寬度；a表示剩余區(qū)域的面積; 1，2，3，4分別代表u,t,r,a的加權(quán)系

25、數(shù)。 以上的加權(quán)法直接影響的僅僅是一次排樣，但由于全部零件的排樣是由各個零件排樣完成的，因此，通過調(diào)整加權(quán)系數(shù)，可以改變板材中排樣的進(jìn)程。多次調(diào)整權(quán)值并橫向比較。選取總體排樣率最高的權(quán)值，就可以得到較優(yōu)的解。3.在滿足約束條件的情況下建立二叉樹并實現(xiàn)遍歷、搜索等操作：#include#include#includeusing namespace std;/二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)的形式定義/二叉樹結(jié)點typedef struct BiTNodechar data; /數(shù)據(jù)struct BiTNode *lchild,*rchild; /左右孩子指針BiTNode,*BiTree;/二叉樹的創(chuàng)建/按先

26、序序列創(chuàng)建二叉樹int CreateBiTree(BiTree &T)char data;/按先序次序輸入二叉樹中結(jié)點的值（一個字符）,#表示空樹cindata;if(data = #)T = NULL;elseT = (BiTree)malloc(sizeof(BiTNode);/生成根結(jié)點T-data = data;/構(gòu)造左子樹CreateBiTree(T-lchild);/構(gòu)造右子樹CreateBiTree(T-rchild);return 0;/輸出/二叉樹的遍歷/遞歸算法void Visit(BiTree T)if(T-data != #)coutdata;/先序遍歷void Pre

27、Order(BiTree T)if(T != NULL)/訪問根節(jié)點Visit(T);/訪問左子結(jié)點PreOrder(T-lchild);/訪問右子結(jié)點PreOrder(T-rchild);/中序遍歷 void InOrder(BiTree T) if(T != NULL) /訪問左子結(jié)點 InOrder(T-lchild); /訪問根節(jié)點 Visit(T); /訪問右子結(jié)點 InOrder(T-rchild); /后序遍歷void PostOrder(BiTree T)if(T != NULL)/訪問左子結(jié)點PostOrder(T-lchild);/訪問右子結(jié)點PostOrder(T-rch

28、ild);/訪問根節(jié)點Visit(T);int main()BiTree T;CreateBiTree(T);cout”先序遍歷：n”;PreOrder2(T);cout”n”;cout中序遍歷：n;InOrder2(T);cout”n”;cout后序遍歷：n;LevelOrder(T);cout”n”; return 0;4.4.1問題一的輸出結(jié)果圖144.4.2問題二的輸出結(jié)果圖154.4.3問題三的輸出結(jié)果圖165、模型求解5.1 問題一的求解參考問題一的方法，畫出了近似最優(yōu)切法圖使得利用率較大，得到具體切法如圖17：圖17剩料為400300的矩形，故=1nSiS-S余=1nSi2500900-300400=99.94% 5.2 問題二的求解類似問題一，我們畫出了近似最優(yōu)切法圖使得利用率較大，得到具體切法如圖18。根據(jù)附件二和假設(shè)的條件易求得五邊形和六邊形的面積分別為：.5和。而余料為411311的矩形?？汕蟮茫?1nSiS-S余=1nSi23801630-411311=89.3%圖185.3 問題三的求解類似問題一，我們畫出了近似最優(yōu)切法圖使得利用率較大，得到具體切法如圖