發(fā)布時(shí)間：2018-11-25 12:08

【摘要】：作為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域最基礎(chǔ)、最原始的問(wèn)題之一,裝箱問(wèn)題的研究已延續(xù)四十年之久,許多關(guān)鍵結(jié)果相繼涌現(xiàn),一些隸屬于計(jì)算機(jī)科學(xué)以及組合優(yōu)化學(xué)科內(nèi)的重大理論均起源于對(duì)裝箱問(wèn)題的研究,由此可見(jiàn)對(duì)裝箱問(wèn)題的研究意義深遠(yuǎn)。此外,裝箱問(wèn)題在實(shí)際生活中應(yīng)用極其廣泛,不論是計(jì)算機(jī)科學(xué)領(lǐng)域中的多處理器任務(wù)調(diào)度、負(fù)載均衡,還是工業(yè)制造領(lǐng)域中的切割存儲(chǔ)和卡車(chē)裝載都是裝箱問(wèn)題的具體例子。近年來(lái),基于受限空間的在線裝箱問(wèn)題以及帶建議的在線裝箱問(wèn)題成為在線裝箱問(wèn)題的兩個(gè)研究熱點(diǎn),其中只打開(kāi)兩個(gè)箱子的二維在線裝箱問(wèn)題的最好的結(jié)果是Januszewski提出的近似度為3.8的算法,而帶建議的一維在線裝箱問(wèn)題,到目前為止結(jié)果最好的是由Boyar等人提出的算法,其近似度達(dá)到了4/3。本論文主要針對(duì)這兩個(gè)結(jié)果分別進(jìn)行了改進(jìn)和相應(yīng)的擴(kuò)展研究,具體工作如下：1.對(duì)于只開(kāi)兩個(gè)箱子的正方形在線裝箱問(wèn)題,基于Januszewski提出的在箱子劃分塊的思想,通過(guò)繼續(xù)劃分放大物體的混合箱子,使之包括一種新類(lèi)型的塊,從而達(dá)到只放小物體的簡(jiǎn)單箱子中劃分出的塊占用率提高的目的,另外采用將一部分小物體與大物體混合裝入復(fù)雜箱子的方法,彌補(bǔ)混合箱子的空閑空間。最終使得打開(kāi)的兩種類(lèi)型的箱子的占用率都得到提高。通過(guò)分析得出,本文提出的只開(kāi)兩個(gè)箱子的正方形在線裝箱算法的近似度為3.63556。2.將正方形塊劃分的思想擴(kuò)展到只開(kāi)兩個(gè)箱子的立方體在線裝箱和超級(jí)立方體在線裝箱問(wèn)題上,通過(guò)不同維度的塊劃分技巧,分別提出一個(gè)近似度為5.43的立方體在線裝箱算法和一個(gè)近似度為32/21·2d的超級(jí)立方體在線裝箱算法,在只開(kāi)兩個(gè)箱子的在線多維立方體裝箱問(wèn)題上,這兩個(gè)結(jié)果均為這類(lèi)問(wèn)題的首次的研究結(jié)果。3.對(duì)于帶建議的在線裝箱問(wèn)題,本文通過(guò)細(xì)化物體分類(lèi),增加物體組合拼裝的種類(lèi),以及設(shè)定最少數(shù)目的建議位來(lái)表示對(duì)應(yīng)的組合物體類(lèi)型,最終將一維帶建議的在線裝箱問(wèn)題的近似算法的結(jié)果改進(jìn)為5/4。對(duì)于最少要用到的建議位數(shù)目問(wèn)題,通過(guò)構(gòu)建一類(lèi)特定形式的到來(lái)物體序列,本文分析出最少需要的建議位數(shù)為(n-3OPT) log OPT來(lái)達(dá)到最優(yōu)裝箱效果。4.將相應(yīng)的思想擴(kuò)展到二維的帶建議的在線裝箱問(wèn)題上,分別提出了近似度為2的正方形在線裝箱算法和近似度為2.25的可旋轉(zhuǎn)長(zhǎng)方形在線裝箱算法,這兩個(gè)結(jié)果不僅是這類(lèi)問(wèn)題的首次研究,而且均比目前最好的不帶建議位的同類(lèi)問(wèn)題的結(jié)果要好。5.本論文研究了二維正方形在線裝箱的并行化問(wèn)題,提出了一個(gè)SIMD模型,并分析出基于此模型的并行裝箱算法的近似度為9/4,時(shí)間復(fù)雜度為θ(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).
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

2 杜少波;張國(guó)基;劉清;;一種新的多約束尺寸可變的裝箱問(wèn)題[J];計(jì)算機(jī)工程與應(yīng)用;2011年19期

3 顧曉東 ,許胤龍 ,陳國(guó)良 ,黃劉生;受啟動(dòng)空間約束的裝箱問(wèn)題[J];軟件學(xué)報(bào);2002年03期

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

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

6 楊鼎強(qiáng);王晨;;受位置約束的有色裝箱問(wèn)題[J];計(jì)算機(jī)工程與設(shè)計(jì);2006年20期

7 楊鼎強(qiáng);蔣加伏;;帶核元的帶拒絕裝箱問(wèn)題[J];長(zhǎng)沙理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年02期

8 張清富;陳珍娜;;淺議裝箱問(wèn)題的若干求解策略[J];廈門(mén)廣播電視大學(xué)學(xué)報(bào);2007年01期

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

10 王晨;楊曙;;A型變尺寸裝箱問(wèn)題之模型及算法研究[J];計(jì)算技術(shù)與自動(dòng)化;2010年03期

相關(guān)會(huì)議論文 前4條

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

2 陳鋒;邢文訓(xùn);;在線塔狀裝箱問(wèn)題(英文)[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2000年

3 ;Voronoi Diagram Approximate the Extreme Packing and Its Applications[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2000年

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

相關(guān)博士學(xué)位論文 前5條

1 趙曉凡;在線裝箱問(wèn)題相關(guān)近似算法研究[D];北京交通大學(xué);2016年

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

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

4 余國(guó)松;與裝箱相關(guān)的幾類(lèi)問(wèn)題[D];浙江大學(xué);2009年

5 石永強(qiáng);若干批處理機(jī)排序與裝箱問(wèn)題的算法研究[D];浙江大學(xué);2005年

相關(guān)碩士學(xué)位論文 前10條

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

2 王驍;汽車(chē)零部件物流中心三維裝箱問(wèn)題研究[D];大連理工大學(xué);2015年

3 高偉;多約束有色三維裝箱問(wèn)題的混合遺傳算法研究[D];長(zhǎng)沙理工大學(xué);2014年

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

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

6 邱朝陽(yáng);考慮重量約束的集裝箱裝箱問(wèn)題[D];華南理工大學(xué);2010年

7 王鐘;染色裝箱問(wèn)題的相關(guān)研究[D];浙江大學(xué);2007年

8 劉林浩;關(guān)于脆度裝箱問(wèn)題的若干研究[D];長(zhǎng)沙理工大學(xué);2013年

9 徐妮;具有不同價(jià)格的裝箱問(wèn)題[D];云南大學(xué);2015年

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

，

本文編號(hào)：2356052