【摘要】：作為計算機科學與技術領域最基礎、最原始的問題之一,裝箱問題的研究已延續(xù)四十年之久,許多關鍵結果相繼涌現(xiàn),一些隸屬于計算機科學以及組合優(yōu)化學科內的重大理論均起源于對裝箱問題的研究,由此可見對裝箱問題的研究意義深遠。此外,裝箱問題在實際生活中應用極其廣泛,不論是計算機科學領域中的多處理器任務調度、負載均衡,還是工業(yè)制造領域中的切割存儲和卡車裝載都是裝箱問題的具體例子。近年來,基于受限空間的在線裝箱問題以及帶建議的在線裝箱問題成為在線裝箱問題的兩個研究熱點,其中只打開兩個箱子的二維在線裝箱問題的最好的結果是Januszewski提出的近似度為3.8的算法,而帶建議的一維在線裝箱問題,到目前為止結果最好的是由Boyar等人提出的算法,其近似度達到了4/3。本論文主要針對這兩個結果分別進行了改進和相應的擴展研究,具體工作如下：1.對于只開兩個箱子的正方形在線裝箱問題,基于Januszewski提出的在箱子劃分塊的思想,通過繼續(xù)劃分放大物體的混合箱子,使之包括一種新類型的塊,從而達到只放小物體的簡單箱子中劃分出的塊占用率提高的目的,另外采用將一部分小物體與大物體混合裝入復雜箱子的方法,彌補混合箱子的空閑空間。最終使得打開的兩種類型的箱子的占用率都得到提高。通過分析得出,本文提出的只開兩個箱子的正方形在線裝箱算法的近似度為3.63556。2.將正方形塊劃分的思想擴展到只開兩個箱子的立方體在線裝箱和超級立方體在線裝箱問題上,通過不同維度的塊劃分技巧,分別提出一個近似度為5.43的立方體在線裝箱算法和一個近似度為32/21·2d的超級立方體在線裝箱算法,在只開兩個箱子的在線多維立方體裝箱問題上,這兩個結果均為這類問題的首次的研究結果。3.對于帶建議的在線裝箱問題,本文通過細化物體分類,增加物體組合拼裝的種類,以及設定最少數(shù)目的建議位來表示對應的組合物體類型,最終將一維帶建議的在線裝箱問題的近似算法的結果改進為5/4。對于最少要用到的建議位數(shù)目問題,通過構建一類特定形式的到來物體序列,本文分析出最少需要的建議位數(shù)為(n-3OPT) log OPT來達到最優(yōu)裝箱效果。4.將相應的思想擴展到二維的帶建議的在線裝箱問題上,分別提出了近似度為2的正方形在線裝箱算法和近似度為2.25的可旋轉長方形在線裝箱算法,這兩個結果不僅是這類問題的首次研究,而且均比目前最好的不帶建議位的同類問題的結果要好。5.本論文研究了二維正方形在線裝箱的并行化問題,提出了一個SIMD模型,并分析出基于此模型的并行裝箱算法的近似度為9/4,時間復雜度為θ(n)。
[Abstract]:As one of the most basic and primitive problems in the field of computer science and technology, the study of the packing problem has been going on for more than 40 years, and many key results have emerged one after another. Some important theories belonging to computer science and combinatorial optimization all originate from the study of packing problem, so the research on packing problem is of great significance. In addition, the packing problem is widely used in real life. Whether it is multiprocessor task scheduling, load balancing, cutting storage and truck loading in the field of industrial manufacturing, it is a concrete example of packing problem. In recent years, the online packing problem based on restricted space and the online packing problem with suggestions have become two research hotspots in online packing problem. The best result of the two-dimensional online packing problem with only two open boxes is that the approximation is 3.8 proposed by Januszewski, while the best result of the proposed one-dimensional online packing problem is by far the algorithm proposed by Boyar et al. The approximation is 4 / 3. This paper mainly aims at these two results to carry on the improvement and the corresponding expansion research separately, the concrete work is as follows: 1. For the problem of square online packing with only two boxes open, based on the idea of dividing blocks in boxes proposed by Januszewski, a new type of block is included by continuing to divide mixed boxes with enlarged objects. In order to achieve the purpose of increasing the occupancy rate of blocks divided in simple boxes with only small objects, the method of mixing some small objects with large objects into complex boxes is adopted to make up for the free space of the mixed boxes. As a result, the occupancy rate of both types of open boxes is increased. Through analysis, the approximate degree of the square online packing algorithm with only two boxes is 3.63556.2. The idea of square block partition is extended to the problem of cubes online packing and super cube online packing with only two boxes, and the techniques of block partitioning in different dimensions are used. A cube online packing algorithm with an approximate degree of 5.43 and a super cube online packing algorithm with an approximate degree of 32 / 21.2 d are proposed, respectively. These two results are the first results of this kind of problem. 3. 3. For the online packing problem with suggestions, this paper presents the corresponding combination object types by refining the classification of objects, increasing the types of assembly of objects, and setting the minimum number of suggested bits. Finally, the approximate algorithm for one dimensional online packing problem with suggestions is improved to 5 / 4. For the problem of the least number of bits to be used, by constructing a class of special coming object sequences, this paper analyzes that the least required number of suggested bits is (n-3OPT) log OPT) to achieve the optimal packing effect. 4. In this paper, the corresponding idea is extended to the two dimensional online packing problem with suggestions, and a square online packing algorithm with approximate degree 2 and a rotating rectangle online packing algorithm with an approximate degree of 2.25 are proposed, respectively. These two results are not only the first study of this kind of problem, but also better than that of the best one without suggestion. In this paper, we study the parallelization of two-dimensional square online packing, propose a SIMD model, and analyze that the parallel packing algorithm based on this model has an approximate degree of 9 / 4 and a time complexity of 胃 (n).
【學位授予單位】：北京交通大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP301.6

【相似文獻】

相關期刊論文 前10條

1 于洪霞;張紹武;張立衛(wèi);;二維裝箱問題非線性規(guī)劃模型和算法[J];大連理工大學學報;2008年02期

2 杜少波;張國基;劉清;;一種新的多約束尺寸可變的裝箱問題[J];計算機工程與應用;2011年19期

3 顧曉東 ,許胤龍 ,陳國良 ,黃劉生;受啟動空間約束的裝箱問題[J];軟件學報;2002年03期

4 何勇,談之奕,任峰;互聯(lián)網(wǎng)信息組織和規(guī)劃中的帶拒絕裝箱問題[J];計算機學報;2003年12期

5 武曉今,朱仲英;二維裝箱問題的一種實現(xiàn)方法[J];微型電腦應用;2003年04期

6 楊鼎強;王晨;;受位置約束的有色裝箱問題[J];計算機工程與設計;2006年20期

7 楊鼎強;蔣加伏;;帶核元的帶拒絕裝箱問題[J];長沙理工大學學報(自然科學版);2007年02期

8 張清富;陳珍娜;;淺議裝箱問題的若干求解策略[J];廈門廣播電視大學學報;2007年01期

9 鐘石泉;王雪蓮;;多箱型三維裝箱問題及其優(yōu)化研究[J];計算機工程與應用;2009年22期

10 王晨;楊曙;;A型變尺寸裝箱問題之模型及算法研究[J];計算技術與自動化;2010年03期

相關會議論文 前4條

1 張國川;;組合優(yōu)化算法研究-從裝箱問題說起[A];2006年中國運籌學會數(shù)學規(guī)劃分會代表會議暨第六屆學術會議論文集[C];2006年

2 陳鋒;邢文訓;;在線塔狀裝箱問題(英文)[A];中國運籌學會第六屆學術交流會論文集（上卷）[C];2000年

3 ;Voronoi Diagram Approximate the Extreme Packing and Its Applications[A];中國運籌學會第六屆學術交流會論文集（上卷）[C];2000年

4 董杰方;張漢欣;李安平;;冷卷入庫的數(shù)學模型及算法[A];2001中國鋼鐵年會論文集（下卷）[C];2001年

相關博士學位論文 前5條

1 趙曉凡;在線裝箱問題相關近似算法研究[D];北京交通大學;2016年

2 王俊嶺;矩形裝箱問題的協(xié)同決策模型[D];蘭州大學;2013年

3 于洪霞;二維裝箱問題的非線性優(yōu)化方法[D];大連理工大學;2006年

4 余國松;與裝箱相關的幾類問題[D];浙江大學;2009年

5 石永強;若干批處理機排序與裝箱問題的算法研究[D];浙江大學;2005年

相關碩士學位論文 前10條

1 江瀑;組合裝箱問題模型與算法研究[D];上海交通大學;2015年

2 王驍;汽車零部件物流中心三維裝箱問題研究[D];大連理工大學;2015年

3 高偉;多約束有色三維裝箱問題的混合遺傳算法研究[D];長沙理工大學;2014年

4 朱園;基于多智能體進化算法的布圖方法及三維裝箱方法[D];西安電子科技大學;2014年

5 宋園春;關于帶沖突裝箱問題的若干優(yōu)化算法研究[D];天津大學;2014年

6 邱朝陽;考慮重量約束的集裝箱裝箱問題[D];華南理工大學;2010年

7 王鐘;染色裝箱問題的相關研究[D];浙江大學;2007年

8 劉林浩;關于脆度裝箱問題的若干研究[D];長沙理工大學;2013年

9 徐妮;具有不同價格的裝箱問題[D];云南大學;2015年

10 王秀清;基于混合分組遺傳算法的裝箱問題研究[D];山東大學;2010年

，

本文編號：2356052