二維不規(guī)則零件排樣及相關(guān)問題研究.pdf

1、二維不規(guī)則零件的排樣問題，在理論上屬于NP完全問題，有著較高的計算復雜度，求解很困難。因為對該問題的研究有其理論意義和廣泛的應(yīng)用背景，所以，該問題成為最優(yōu)化問題中的一個重要的研究分支。研究方法主要基于兩種思路：一種是基于規(guī)則零件排樣處理的矩形化方法，另一種是對不規(guī)則零件的直接排樣處理。本文在原有矩形近似算法和不規(guī)則件直接處理算法的基礎(chǔ)上，探索了一種基于兩種方法相結(jié)合處理不規(guī)則零件排樣的優(yōu)化方法，以提高排樣效率和材料利用率。 在研

2、究國內(nèi)外學者提出的算法的基礎(chǔ)上，本文主要做了如下工作： 首先對排樣問題的復雜性理論進行了分析，指出了有NP難度的二維排樣問題在矩形件上的遺傳算法改進同樣的也適合于不規(guī)則件。其次，對遺傳算法和模擬退火算法分別進行了介紹，指出兩種算法的結(jié)合可以有效的減弱遺傳算法的早熟現(xiàn)象。最后，提出了二維不規(guī)則零件正交排樣的概念和一種新的定位啟發(fā)式方法——占角優(yōu)先算法，該算法與最低水平線算法進行比較，實例驗證表明，新的定位算法在保證排樣效果的前提下