圓形件下料啟發(fā)式算法.pdf

1、切割下料問題廣泛存在于國民經(jīng)濟生產(chǎn)的各大行業(yè)中，例如機械制造業(yè)、服裝加工業(yè)、家具制造業(yè)、木材加工業(yè)以及皮革制品制造業(yè)等。隨著信息化產(chǎn)業(yè)和計算機技術(shù)的快速發(fā)展，先進的計算機輔助設(shè)計技術(shù)被越來越多的應(yīng)用于優(yōu)化下料過程中，成為提高下料效率和利用率的關(guān)鍵。二維下料問題是指原材料和毛坯維數(shù)都為二維時，考慮如何優(yōu)化切割下料，使得滿足毛坯需求，并且最大限度的提高材料利用率、減少切割損失。二維下料問題是日常生產(chǎn)中廣泛存在的一種下料問題。目前，國內(nèi)外學(xué)者

2、對二維下料問題的研究給予了足夠的重視，特別是針對矩形件和二維不規(guī)則件的排樣問題提出了許多行之有效的算法，比如動態(tài)規(guī)劃算法，分支定界算法，禁忌搜索、模擬退火算法，遺傳算法，神經(jīng)網(wǎng)絡(luò)算法等等。然而，對另一種在實際生產(chǎn)中廣泛存在的二維下料問題——圓形件下料問題研究相對較少，特別是對圓形件下料的有約束排樣算法更是有限。對于排樣算法的研究有兩個方向的分支：有約束排樣算法和無約束排樣算法。無約束排樣算法是指已知要排入毛坯的尺寸和價值，實現(xiàn)其在單張板

3、材上的排樣，使得排入毛坯的總價值最大，這種排樣算法通常與線性規(guī)劃技術(shù)相結(jié)合，以求解下料問題。有約束排樣算法用于確定毛坯在單張板材上的排樣方式，使得在滿足毛坯數(shù)量上限約束的條件下，單張板材上排入毛坯的總價值最大；它通常與順序法結(jié)合，以求解下料問題。本文研究有約束排樣算法及基于順序法的排樣方案生成算法，以求解圓形件剪沖下料排樣問題，即以剪沖下料方式為工藝基礎(chǔ)，確定一個排樣方案，該排樣方案滿足如下條件：(1)排樣方案由一個或多個排樣方式組成；

4、(2)排樣方式必須是可行的；(3)精確滿足各種毛坯的需求量；(4)排樣方案要使所消耗的板材的總面積最小。所謂剪沖下料工藝就是把給定長度和寬度的板材首先用剪床把板材切割成水平或豎直條帶，并且每根條帶中包含的圓片具有相同的直徑，再將每根條帶送至沖床沖出圓片。在對啟發(fā)式算法進行分析和研究的基礎(chǔ)上，使用順序價值修正法對圓形件下料問題進行求解。本文的主要工作如下：第一，針對研究的問題，給出求解圓形件在單張板材上的最優(yōu)排樣方式生成算法，并以此算法為

5、基礎(chǔ)，結(jié)合順序啟發(fā)式策略設(shè)計排樣方案生成算法，使得在精確滿足各圓形件需求量的前提下，最大限度的提高材料利用率。第二，進一步完善和改進本文算法。由于傳統(tǒng)的順序啟發(fā)式策略具有一定的貪婪性質(zhì)，因此使用此方法生成的排樣方案容易造成排樣方案的局部最優(yōu)而不是整體最優(yōu)，所以本文結(jié)合了基于順序價值修正的啟發(fā)式策略和參數(shù)優(yōu)化的方法，提高材料的利用率。順序價值修正是指初始化圓形件毛坯的價值為圓形件的面積，每生成一個新的排樣方式前，都運用價值修正公式以修正前

6、的毛坯價值為基礎(chǔ)加以計算，修正各種毛坯的價值，并多次重復(fù)該過程，最終使其價值系數(shù)達(dá)到較為合理的狀態(tài)。通過適當(dāng)調(diào)整毛坯價值，將他們的相對受歡迎程度體現(xiàn)出來，對不好排的毛坯賦予較高的優(yōu)先權(quán)，使之優(yōu)先被選擇。這樣做有助于生成較好的排樣方式，并利用前面方式的信息，指導(dǎo)后面的排樣過程，從而有效的提高原材料的利用率。第三，規(guī)劃和設(shè)計下料系統(tǒng)的基本功能模塊，設(shè)計開發(fā)了基于順序價值修正法的圓形件下料排樣系統(tǒng)。并用已有的下料系統(tǒng)對本文算法進行有效性檢驗，