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