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

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

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

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