二維矩形件和直線塊排樣問題的算法研究.pdf

1、二維矩形件排樣問題和直線塊排樣問題廣泛應(yīng)用于機(jī)械加工、印刷排版、布匹裁剪、VLSI設(shè)計(jì)等領(lǐng)域。由于排樣問題的復(fù)雜性為NP完全，以及工業(yè)生產(chǎn)中即使很小的材料利用率的提高也能帶來顯著的經(jīng)濟(jì)效益，因此這類問題的近似求解方案非常重要。
　　 目前針對矩形件排樣問題提出的一些有效的啟發(fā)式算法，如Best-fit(BF)算法、Fastlayer-based(FH)算法，都是在布局圖上的最低水平線上選取合適的矩形進(jìn)行排放。為了充分利用一些較好

2、的填充策略，本文設(shè)計(jì)的多水平線(Multi-layerHorizon，MLH)算法不僅在最低水平空間中進(jìn)行矩形排放，還將其左右相鄰的合適位置作為排放區(qū)域;另外，在最佳高度線下方的左右兩個(gè)位置處也進(jìn)行矩形填充，以增大獲取到最優(yōu)解的可能。同等測試條件下的實(shí)驗(yàn)結(jié)果表明，對于21組Hopper&Turton問題，MLH算法獲得的解的質(zhì)量略差于BF算法;而13組Burke問題，MLH算法卻明顯好于BF算法。
　　 在研究直線塊排樣問題時(shí)，

3、本文選取最基本的L/T形塊作為研究對象，提出了對零件直接排放的頂點(diǎn)最少(VerticesLeast，VL)算法。VL算法將所有待排零件在最低水平空間上嘗試排放后，選取與當(dāng)前布局圖重合點(diǎn)最多的那個(gè)零件正式排放。如果最低水平空間上不能容納的下任何零件，則提升其高度至左右相鄰空間高度的較小值。由于VL算法同樣適用于矩形件排樣問題，將其與BF算法以及MLH算法進(jìn)行了對比。對于Hopper&Turton問題的測試結(jié)果表明，VL算法的平均排樣高度略

4、好于MLH算法，差于BF算法;而對于Burke問題，VL算法的結(jié)果比BF和MLH算法都差。另外，對于3組L/T形塊排樣問題，VL算法的求解結(jié)果差于結(jié)合了模擬退火算法的B*-trees算法，而與應(yīng)用了回溯技術(shù)的Corner-occupyingaction(COA)算法的結(jié)果相同。
　　 由于啟發(fā)式算法在求解排樣問題時(shí)的解并不理想，為了提高算法的求解精度，本文引入粒子群算法來優(yōu)化求解空間，設(shè)計(jì)出了混合算法MLH+PSO和VL+PSO

5、，并討論了學(xué)習(xí)因子和最大速度對混合算法收斂的影響。分析得到，隨著學(xué)習(xí)因子的增大和最大速度的減小，算法的收斂速度呈現(xiàn)先增快后減慢的趨勢。在對Hoppezr&Turton和Burke問題進(jìn)行實(shí)驗(yàn)測試后，MLH+PSO和VL+PSO算法無論是獲取到最優(yōu)解的實(shí)例數(shù)目還是平均排樣高度，都明顯好于目前比較著名的BF+SA、BF+SW和LH算法;而對于26組不可旋轉(zhuǎn)的non-zero-waste問題，MLH+PSO算法的解也明顯好于Leastwast