在線裝箱問題相關(guān)近似算法研究.pdf

1、作為計算機科學(xué)與技術(shù)領(lǐng)域最基礎(chǔ)、最原始的問題之一，裝箱問題的研究已延續(xù)四十年之久，許多關(guān)鍵結(jié)果相繼涌現(xiàn)，一些隸屬于計算機科學(xué)以及組合優(yōu)化學(xué)科內(nèi)的重大理論均起源于對裝箱問題的研究，由此可見對裝箱問題的研究意義深遠(yuǎn)。此外，裝箱問題在實際生活中應(yīng)用極其廣泛，不論是計算機科學(xué)領(lǐng)域中的多處理器任務(wù)調(diào)度、負(fù)載均衡，還是工業(yè)制造領(lǐng)域中的切割存儲和卡車裝載都是裝箱問題的具體例子。
　　近年來，基于受限空間的在線裝箱問題以及帶建議的在線裝箱問題成為

2、在線裝箱問題的兩個研究熱點，其中只打開兩個箱子的二維在線裝箱問題的最好的結(jié)果是Januszewski提出的近似度為3.8的算法，而帶建議的一維在線裝箱問題，到目前為止結(jié)果最好的是由Boyar等人提出的算法，其近似度達到了4/3。本論文主要針對這兩個結(jié)果分別進行了改進和相應(yīng)的擴展研究，具體工作如下:
　　1.對于只開兩個箱子的正方形在線裝箱問題，基于Januszewski提出的在箱子劃分塊的思想，通過繼續(xù)劃分放大物體的混合箱子，使之

3、包括一種新類型的塊，從而達到只放小物體的簡單箱子中劃分出的塊占用率提高的目的，另外采用將一部分小物體與大物體混合裝入復(fù)雜箱子的方法，彌補混合箱子的空閑空間，最終使得打開的兩種類型的箱子的占用率都得到提高，通過分析得出，本文提出的只開兩個箱子的正方形在線裝箱算法的近似度為3.63556。
　　2.將正方形塊劃分的思想擴展到只開兩個箱子的立方體在線裝箱和超級立方體在線裝箱問題上，通過不同維度的塊劃分技巧，分別提出一個近似度為5.43的

4、立方體在線裝箱算法和一個近似度為32/21·2d的超級立方體在線裝箱算法，在只開兩個箱子的在線多維立方體裝箱問題上，這兩個結(jié)果均為這類問題的首次的研究結(jié)果。
　　3.對于帶建議的在線裝箱問題，本文通過細(xì)化物體分類，增加物體組合拼裝的種類，以及設(shè)定最少數(shù)目的建議位來表示對應(yīng)的組合物體類型，最終將一維帶建議的在線裝箱問題的近似算法的結(jié)果改進為5/4。對于最少要用到的建議位數(shù)目問題，通過構(gòu)建一類特定形式的到來物體序列，本文分析出最少需要

5、的建議位數(shù)為(n-3OPT) log OPT來達到最優(yōu)裝箱效果。
　　4.將相應(yīng)的思想擴展到二維的帶建議的在線裝箱問題上，分別提出了近似度為2的正方形在線裝箱算法和近似度為2.25的可旋轉(zhuǎn)長方形在線裝箱算法，這兩個結(jié)果不僅是這類問題的首次研究，而且均比目前最好的不帶建議位的同類問題的結(jié)果要好。
　　5.本論文研究了二維正方形在線裝箱的并行化問題，提出了一個SIMD模型，并分析出基于此模型的并行裝箱算法的近似度為9/4，時間復(fù)