本文關(guān)鍵詞：一維捆綁式裝箱問題

  更多相關(guān)文章： 一維捆綁式裝箱問題 K-組裝箱 漸進(jìn)(近似)算法

【摘要】：本文對(duì)一維裝箱問題進(jìn)行了推廣,提出了一個(gè)新的問題,稱為一維捆綁式裝箱問題。一維捆綁式裝箱問題的具體描述如下：給定n個(gè)物品的序列I=(a1,a2,...,an),每個(gè)物品尺寸為s(ai)∈(0,l],這里i=1,2,...,n,提供若干個(gè)K-組裝箱,把I中的物品裝入若干個(gè)K-組裝箱中,要求每個(gè)小箱子所裝物品的尺寸之和不超過l,目標(biāo)是使得所使用的K-組裝箱的數(shù)目達(dá)到最小,其中一個(gè)K-組裝箱由K個(gè)尺寸為l的箱子捆綁組成,K-組裝箱的尺寸為l。為了解決一維捆綁式裝箱問題,本文設(shè)計(jì)了K-NF算法、]K-FFD算法和K-SFOF算法三個(gè)離線算法,其中K-NF算法的近似值為2,復(fù)雜性為O(n)；K-FFD算法和K-SFOF算法的漸進(jìn)近似值都為3/2,時(shí)間復(fù)雜性分別為O(n2)和O(n)。同時(shí)本文設(shè)計(jì)一個(gè)在線漸進(jìn)近似算法-K-SFON算法,該算法的漸進(jìn)近似值為7/4,時(shí)間復(fù)雜性為O(n)。
【關(guān)鍵詞】：一維捆綁式裝箱問題 K-組裝箱 漸進(jìn)(近似)算法
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O224
【目錄】：

• 摘要3-4
• Abstract4-6
• 第一章 引言6-9
• 1.1 理論背景6-7
• 1.2 主要結(jié)果7-8
• 1.3 論文結(jié)構(gòu)8-9
• 第二章 預(yù)備知識(shí)9-16
• 2.1 組合最優(yōu)化9-11
• 2.2 近似算法11-13
• 2.3 一維裝箱問題及算法13-16
• 第三章 一維捆綁式裝箱問題及其算法設(shè)計(jì)16-40
• 3.1 K-NF算法及其分析16-19
• 3.2 K-FFD算法及其分析19-24
• 3.3 K-SFOF算法及其分析24-29
• 3.4 K-SFON算法及其分析29-36
• 3.5 算例36-40
• 結(jié)論40-41
• 附錄41-59
• 參考文獻(xiàn)59-61
• 致謝61

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫 前10條

1 楊殿生;求解裝箱問題的一種變長(zhǎng)度染色體遺傳算法[J];長(zhǎng)春工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2004年02期

2 劉林浩;楊鼎強(qiáng);王晨;;一種帶脆度的尺寸可變裝箱問題[J];計(jì)算機(jī)工程與應(yīng)用;2013年12期

3 杜林古,孫孝瑞;風(fēng)向圖上兩問題的復(fù)雜性[J];青島大學(xué)學(xué)報(bào)(自然科學(xué)版);1997年01期

4 閔孟斌;鎖具裝箱問題的最大不互開鎖數(shù)的理論證明[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2000年04期

5 孫春玲,陳智斌,李建平;裝箱問題的一種新的近似算法[J];云南大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年05期

6 解其生,李維仙,吳欣明;用綜合試探法提高一維裝箱問題的性能[J];廊坊師范學(xué)院學(xué)報(bào);2004年04期

7 孫春玲;染色的裝箱問題及其近似算法[J];云南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年03期

8 孫春玲;染色裝箱問題及其啟發(fā)式算法[J];云南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年04期

9 湯巖;胡俊敏;武立豐;;一種改進(jìn)的二維裝箱問題的混合遺傳算法[J];集美大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期

10 陳德良;陳治亞;;三維裝箱問題的模型與改進(jìn)遺傳算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2010年02期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫 前4條

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

2 陳鋒;邢文訓(xù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 董杰方;張漢欣;李安平;;冷卷入庫的數(shù)學(xué)模型及算法[A];2001中國(guó)鋼鐵年會(huì)論文集（下卷）[C];2001年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫 前5條

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

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

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

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

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

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

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

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

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

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

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

6 梁佳雯;汽車下一代車載網(wǎng)絡(luò)調(diào)度算法的研究[D];貴州師范大學(xué);2016年

7 王明明;一維捆綁式裝箱問題[D];云南大學(xué);2016年

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

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

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

，

本文編號(hào)：563776