矩形件優(yōu)化排樣算法的研究與實現(xiàn).pdf

1、矩形件優(yōu)化排樣問題是指在矩形的板材上，要排放多種不同尺寸的矩形件，如何使這些矩形件既不互相重疊，又不超出板材邊界的條件下，使得材料的利用率達(dá)到最高。它廣泛應(yīng)用于玻璃、鋼板、木材和皮革等。從數(shù)學(xué)計算復(fù)雜性理論看，優(yōu)化排樣問題屬于具有較高計算復(fù)雜性的NP完全問題，至今還無法找到解決該問題的有效多項式時間算法[1]。好的排樣結(jié)果可以提高生產(chǎn)效率，提高材料的利用率，降低生產(chǎn)成本，提高企業(yè)的競爭力。對矩形件優(yōu)化排樣問題的研究具有深遠(yuǎn)的理論意義和實

2、際意義。 本文在分析矩形件優(yōu)化排樣問題特點的基礎(chǔ)上，建立了該問題的數(shù)學(xué)模型，描述了一些常見的優(yōu)化算法和排樣算法。在一定的約束條件下，應(yīng)用遺傳算法方法對矩形件排樣問題進(jìn)行優(yōu)化求解，對算例的求解結(jié)果進(jìn)行比較與分析。 首先介紹了矩形件優(yōu)化排樣問題的數(shù)學(xué)模型和矩形件排樣問題的排樣算法，如剩余矩形匹配法、BL算法、下臺階算法、基于最低水平線的搜索算法。比較了這些算法的優(yōu)缺點。 其次介紹了在大規(guī)模生產(chǎn)中矩形件的下料工藝，如“

3、一刀切”；為了提高生產(chǎn)效率，相同的零件盡可能排放在一起；在加工時，要有安全距離的保障等。 再次介紹了遺傳算法的基本原理，采用遺傳算法對矩形件排樣問題進(jìn)行求解。在求解過程中，給出了遺傳算法的編碼與解碼方法、適應(yīng)度函數(shù)的定義方法、遺傳算子的設(shè)計方法以及關(guān)鍵參數(shù)。通過對具體的算例進(jìn)行求解，對求解的結(jié)果進(jìn)行分析比較。 最后，基于以上理論，用VB.NET開發(fā)了矩形件優(yōu)化排樣系統(tǒng)。其中包括用戶登錄模塊，零件與板材管理模塊，利用優(yōu)化算