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