一種求解圓形下料問題的快速算法

本文研究圓形件優(yōu)化排樣算法，目的是提高材料利用率。本文提出了一種新的放置算法（圓弧搜索算法，ASA），與文獻中算法相比，ASA在較短的時間內(nèi)產(chǎn)生了可以和排樣領(lǐng)域著名的法國學者Hifi在SCI和EI檢索刊物中提出的較復(fù)雜方法GA-BH在利用率方面相媲美的效果；對隨機生成例題的計算結(jié)果表明，本文算法的計算時間可以滿足一般實踐應(yīng)用的要求，所得排樣方案的材料利用率較高。
優(yōu)化排樣是研究如何下料使得原材料利用率最高，在實際生產(chǎn)中應(yīng)用廣泛。提高原材
料利用率問題是一個系統(tǒng)工程問題，需要從生產(chǎn)管理、優(yōu)化下料、決策支持等方面提供完備的一體化解決方案。這些環(huán)節(jié)中優(yōu)化下料方案是提高原材料利用率最直接的方法，而優(yōu)化下料方案的關(guān)鍵是構(gòu)造有效的優(yōu)化排樣算法。本文研究的是圓形件排樣問題，是二維下料問題的一個分支。國內(nèi)外對二維下料問題的矩形和二維不規(guī)則性毛坯的排樣問題研究較多，而對圓形排樣問題的研究較少。
本文研究的圓形件排樣問題指將卷材切成若干圓形毛坯，使所產(chǎn)生的廢料盡可能地少。
由于卷材長度遠遠大于毛坯直徑，在算法設(shè)計時可以將其作為無限長處理。所排零件包括多種尺寸的圓形件，需求必須精確滿足。該問題已經(jīng)被證明屬于相當困難的NP完全問題[1][2]。
本文提出一種新的排樣算法（Arc Search Algorithm，簡稱ASA），按指定的順序，依次
將圓形毛坯排列到卷材上。ASA 算法在較短的時間內(nèi)產(chǎn)生了可以與文獻中的GA-BH方法[3]相媲美的利用率結(jié)果。