不規(guī)則零件的玻璃排樣問題啟發(fā)式算法研究.pdf

1、二維不規(guī)則零件排樣問題在玻璃加工、金屬切割、服裝等行業(yè)都有著廣泛的應(yīng)用，排樣的目的是將一系列形狀各異的零件排放在給定的材料上，找出零件的最優(yōu)布局，讓材料的利用率最大化，達(dá)到節(jié)省原料、提高企業(yè)經(jīng)濟(jì)效益的目的。排樣問題屬于典型的組合優(yōu)化問題，在理論上，它屬于NP完全問題，求解過程非常困難。
　　 本文以建筑設(shè)計(jì)的不斷發(fā)展為背景，以玻璃排樣問題為研究對象，提出了一種啟發(fā)式排樣算法。鑒于玻璃這種物質(zhì)的特殊屬性，在切割過程中必須滿足貫通性

2、約束條件，即guillotine約束，所以相對于布料、皮料等材料的切割，玻璃的切割過程更加的復(fù)雜。本文首次結(jié)合了貫通性約束和不規(guī)則排樣兩個方面的問題，提出了一種貫通性約束下的不規(guī)則零件排樣算法。顯然，這一問題有著廣泛的應(yīng)用背景及理論意義。
　　 本文首先以玻璃排樣問題為研究對象，提出了一種以貼邊度為啟發(fā)式信息的不規(guī)則零件匹配算法，并應(yīng)用該啟發(fā)式匹配方法構(gòu)造了n階匹配矩陣，將劃分問題轉(zhuǎn)換成在可行劃分方案中尋找浪費(fèi)率之和最小的方案，

3、然后通過改進(jìn)的匈牙利方法和KuhnMunkras算法進(jìn)行最優(yōu)劃分。
　　 其次，在排樣零件的填充問題上，通過介紹BL排樣的相關(guān)知識，并對它的優(yōu)缺點(diǎn)進(jìn)行分析，針對其缺點(diǎn)提出了矩形復(fù)合的概念。指出在矩形復(fù)合過程中，需要遞歸地進(jìn)行矩形排樣，并以兩個矩形匹配的利用率為啟發(fā)式信息，分階構(gòu)造森林，只接受那些利用率大于給定閾值的匹配方案。
　　 最后，通過中英兩個玻璃加工企業(yè)的訂單數(shù)據(jù)，進(jìn)行了實(shí)驗(yàn)驗(yàn)證，證明本文提出的算法是有效的，原材