摘 要：二維優(yōu)化下料問(wèn)題是一個(gè)NP-復(fù)雜性問(wèn)題，每一種優(yōu)化軟件都是利用近似和啟發(fā)式處理得到下料結(jié)果，不同的優(yōu)化方法及其優(yōu)化軟件對(duì)不同的某些數(shù)據(jù)結(jié)構(gòu)可能效果并不理想，企業(yè)又不可能購(gòu)進(jìn)大量不同的優(yōu)化軟件來(lái)選優(yōu)。針對(duì)以上問(wèn)題本文提出了一種基于Internet的二維優(yōu)化下料解決方法，并給出了該方法的具體實(shí)現(xiàn)技術(shù)。實(shí)驗(yàn)表明，該方法將明顯提高二維優(yōu)化下料的總體優(yōu)化效果。
關(guān)鍵詞：二維優(yōu)化下料；啟發(fā)式算法；Internet
中圖分類號(hào)：TP391.75
廣義地講，節(jié)約原材料，優(yōu)化利用資源是經(jīng)濟(jì)可持續(xù)發(fā)展戰(zhàn)略的重要內(nèi)容之一，也是綠色制造研究的重要組成部分。在當(dāng)今市場(chǎng)經(jīng)濟(jì)條件下，對(duì)某一個(gè)企業(yè)而言，節(jié)約原材料，提高原材料利用率，降低成本，是該企業(yè)在市場(chǎng)經(jīng)濟(jì)競(jìng)爭(zhēng)中取勝的重要條件[1,2]。在某些行業(yè)所需要的原材料中，
板材占有相當(dāng)?shù)谋戎兀鐧C(jī)械、船舶、飛機(jī)、
玻璃、家具、服裝等制造業(yè)。如果單靠人工憑經(jīng)驗(yàn)完成下料工作，原材料利用率和工作效率都很低。隨著計(jì)算機(jī)的出現(xiàn)，計(jì)算機(jī)輔助完成下料工作就顯得尤為必要和重要了[3]。自20世紀(jì)60年代，人們就已經(jīng)開(kāi)始二維優(yōu)化下料方面的理論和計(jì)算機(jī)算法的研究，已有許多公司提供軟件產(chǎn)品，但由于二維優(yōu)化下料應(yīng)用的多樣性和算法的復(fù)雜性，限制了二維優(yōu)化下料技術(shù)更好地發(fā)揮作用。
1 當(dāng)前應(yīng)用中存在的問(wèn)題
1.1 二維優(yōu)化下料的方式繁多，通用性軟件設(shè)計(jì)較難
二維優(yōu)化下料問(wèn)題在許多行業(yè)中廣泛存在，各行業(yè)對(duì)二維優(yōu)化下料的具體要求不同，即使同一行業(yè)、同一單位，由于具體業(yè)務(wù)不一樣，要求也可能不一樣。一般二維下料根據(jù)原材料的種類多少可以劃分為多原材二維優(yōu)化下料和單原材二維優(yōu)化下料；根據(jù)下料零件板材的形狀來(lái)劃分，可以分為兩大類：矩形板材和異形材下料（但原材料一般是指矩形件）；根據(jù)
切割約束的不同可以分為直角切割、Guillotine 切割、兩階段切割、方向性切割、一維切割、非直角切割、異形材切割等。
面對(duì)不同情況的不同要求，做一種通用的效果理想的二維優(yōu)化
下料軟件是非常困難的，因此要根據(jù)不同的應(yīng)用開(kāi)發(fā)相應(yīng)的軟件，而對(duì)使用者而言，買全可能要用到的各種二維優(yōu)化軟件是不太現(xiàn)實(shí)的，這樣制約了二維優(yōu)化技術(shù)的進(jìn)一步推廣應(yīng)用。
1.2 優(yōu)化下料技術(shù)理論復(fù)雜，理想算法的實(shí)現(xiàn)困難[4-7]
優(yōu)化下料技術(shù)的研究理論涉及到線性規(guī)劃（LP）、動(dòng)態(tài)規(guī)劃、啟發(fā)式算法（SHP）以及人工智能（AI）等多種學(xué)術(shù)研究前沿理論，國(guó)內(nèi)外學(xué)者在優(yōu)化下料問(wèn)題上進(jìn)行過(guò)不斷的努力，尋求了各種方法。
Gilmore 和Gomory（1965）把優(yōu)化下料問(wèn)題描述為整數(shù)規(guī)劃問(wèn)題。Dyckhoff（1981）提出了另一種線性規(guī)劃的模型。Christofides和Whitlock（1977）提出了一種解決二維單原材異形材Guillotine下料的樹搜索算法。Albano（1980）則提出了一種人機(jī)交互的二維排樣方法。Albano和Orsini（1980）提出了一種成組排列下料板材的方法來(lái)實(shí)現(xiàn)Guillotine的切割。對(duì)于原材料是矩形件的二維單原材異形材下料，Adamowicz和Albano（1976）以及Haims（1968）提出了兩階段的算法，后來(lái)Albano和Sapuppo（1980），Dagh和Nisaner（1981），Tatoglu（1983），Beasley（1984）以及Fabien Chauny等（1991）對(duì)兩階段法進(jìn)行了改進(jìn)，提出了不同的啟發(fā)式算法，以改進(jìn)對(duì)龐大數(shù)量排樣方式的處理。此后的很多研究基本上是集中于可行啟發(fā)式算法，但是人們發(fā)現(xiàn)在某些情況下，傳統(tǒng)的啟發(fā)式算法是不夠有效的。Dagli和Stacey（1988）根據(jù)下料問(wèn)題和調(diào)度問(wèn)題的相似性，提出了一種集人工智能（AI）和運(yùn)籌學(xué)（OR）的方法來(lái)解決優(yōu)化下料問(wèn)題；后來(lái)（1990）Cihan將這一方法加以改進(jìn)，在求解過(guò)程引入了一種基于知識(shí)的調(diào)度表結(jié)構(gòu)。Morabito R.N.（1992）、Viswanathan K.V.（1993），Daza V.P.（1995）和Arenales M.（1995）等利用AI中的AND\OR圖搜索方法來(lái)研究二維背包問(wèn)題的解法，其分支和計(jì)算量仍然很大。
以上方法都不能很好處理優(yōu)化下料過(guò)程所面對(duì)的近乎無(wú)窮的變量和運(yùn)算。由于下料問(wèn)題需要處理數(shù)量龐大的可行切割方式，是一個(gè)NP-完備問(wèn)題。在一維下料中，可行切割方式的數(shù)量就很容易超過(guò)百萬(wàn)，二維下料問(wèn)題的可行切割數(shù)量更為巨大。無(wú)論對(duì)于整數(shù)規(guī)劃的數(shù)學(xué)模型還是其他的模型都不可能通過(guò)對(duì)所有的可行切割方式一一列舉方法來(lái)規(guī)劃優(yōu)選，因?yàn)榧词故抢矛F(xiàn)在最先進(jìn)的計(jì)算機(jī)處理稍復(fù)雜的下料問(wèn)題也是無(wú)法勝任的。對(duì)于這樣一個(gè)NP-復(fù)雜性問(wèn)題，通常只能用啟發(fā)式方法求解。所以在各種優(yōu)化下料的數(shù)學(xué)模型求解中，幾乎都利用了啟發(fā)式算法來(lái)減少龐大數(shù)量給運(yùn)算結(jié)果帶來(lái)的障礙。
現(xiàn)在已經(jīng)提出來(lái)了很多針對(duì)不同結(jié)果滿意度的啟發(fā)式算法及其改進(jìn)算法，但它們的分支和計(jì)算量仍然很大。對(duì)于各種算法在實(shí)用軟件的實(shí)現(xiàn)過(guò)程中，為了增加搜索速度、減少計(jì)算誤差影響和避免計(jì)算時(shí)間過(guò)長(zhǎng)，提出了一系列處理方法：包括設(shè)置某一閥值因子控制可行切割方式的生成數(shù)量、設(shè)置單一排樣最低的優(yōu)化效率、限制下料零件的組合、設(shè)置消減計(jì)算機(jī)計(jì)算誤差的
精度、設(shè)置各種時(shí)間閥值等等，這一系列的處理包括啟發(fā)式算法本身均會(huì)引起優(yōu)化計(jì)算的結(jié)果偏差。總結(jié)各種優(yōu)化下料程序誤差起因，可以將誤差分為系統(tǒng)誤差、算法誤差和人為誤差三種。系統(tǒng)誤差是指計(jì)算機(jī)本身處理引起的誤差，是不可避免的，卻可以通過(guò)一定消減計(jì)算機(jī)計(jì)算誤差方法加以減少；算法誤差源于算法本身，主要是指處理龐大數(shù)量的排樣方式時(shí)，搜索的深度和廣度而言，相同算法條件下，隨搜索深度和廣度的增加，搜索時(shí)間越長(zhǎng)，所以任何啟發(fā)式函數(shù)的設(shè)置都限制遍歷全部排樣，而引起算法誤差；人為誤差主要是指在軟件設(shè)計(jì)中，人為設(shè)定的各種閥值和因子。算法誤差和人為誤差在實(shí)用程序中也是難以完全避免的。
上一頁(yè)123下一頁(yè)
