矩形裝箱問題的啟發(fā)式算法研究.pdf

1、裝箱問題簡單地說就是按一定規(guī)則將若干物體互不重疊地放入有一定容量的容器中,并達到某種最佳目標(biāo)的問題。裝箱問題無處不在,被廣泛地應(yīng)用于計算機科學(xué)、工業(yè)領(lǐng)域和管理科學(xué),如多處理器任務(wù)調(diào)度、內(nèi)存管理、集成電路設(shè)計、貨物裝載、材料切割、新聞排版等都可以形式化為一個裝箱問題。由于裝箱問題的廣泛應(yīng)用,早在二十世紀(jì)七十年代它就得到了學(xué)術(shù)界的廣泛而深入的研究。裝箱問題已經(jīng)成為計算機科學(xué)和組合優(yōu)化領(lǐng)域的一個重要問題。由于裝箱問題是一個NP完全問題,具有高

2、度復(fù)雜性,對于規(guī)模較大的裝箱問題,精確算法無法在合理的時間內(nèi)求得滿意的解,因此,目前研究得最多的是該問題的啟發(fā)式算法。
　　 本文首先對裝箱問題的研究現(xiàn)狀及已有算法進行了闡述和分析,重點研究了二維矩形裝箱問題；在BF算法和PH算法的基礎(chǔ)上設(shè)計了一個新的啟發(fā)式算法一砌墻式BF(BBF)算法。BBF算法與BF算法類似,在裝箱前對待裝矩形進行了旋轉(zhuǎn)和排序,在裝箱過程中每次選擇最低的可行位置、選擇“最合適”的矩形進行填充；不同的是,BB

3、F算法引入了PH算法中設(shè)置“基準(zhǔn)磚”、空間動態(tài)分層的策略。應(yīng)當(dāng)指出,這里“基準(zhǔn)磚”的設(shè)置與PH算法不同。在BBF算法的基礎(chǔ)上我們提出了基于SWO(“Squeaky Wheel”O(jiān)ptimization)方法的啟發(fā)式算法-SBBF算法。SBBF算法按BBF的矩形放置策略放置矩形；根據(jù)每一次裝箱的結(jié)果,對影響裝箱效果的矩形設(shè)置懲罰度,懲罰度高的矩形在下一次裝箱時優(yōu)先裝入。借助于SWO方法的全局優(yōu)化能力,SBBF算法能夠改進BBF算法的裝箱效