本文關(guān)鍵詞：具有不同容量的裝箱問題

  更多相關(guān)文章： 不同容量的裝箱 (漸近)近似算法 復(fù)雜性

【摘要】：一維裝箱問題是指把一個(gè)物品序列裝入單位容量的箱子中,目標(biāo)是使得所使用的箱子數(shù)目達(dá)到最少。本論文研究一維裝箱問題的一種推廣形式,即具有不同容量的裝箱問題。其敘述如下：給定n個(gè)物品序列L=(a1,a2,….,an),每個(gè)物品ai的尺寸為s(ai)∈(0,1],這里i=1,2…,n,給定k種不同容量的箱子若干,每種箱子的容量為s(Bj)∈(0,1],這里j=1,2…,k,要求將物品序列L=(a1,a2…,an)裝入若干個(gè)箱子中,且每個(gè)箱子中的物品尺寸和不超過箱子的容量,目標(biāo)是使得所使用箱子的容量之和達(dá)到最小。 對(duì)于具有不同容量的裝箱問題,Friesen和Langston設(shè)計(jì)了三個(gè)有效的漸近近似算法,即NFL算法,FFDLR算法和FFDLS算法,它們的漸近近似值分別為2,3/2,4/3。本論文修正了FFDLS算法的一些策略,設(shè)計(jì)出一個(gè)5/4-漸近近似算法,其復(fù)雜性為O(nlogn)。
【關(guān)鍵詞】：不同容量的裝箱 (漸近)近似算法 復(fù)雜性
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O224
【目錄】：

• 摘要3-4
• Abstract4-6
• 第一章 引言6-9
• 1.1 理論背景6-8
• 1.2 主要結(jié)果8
• 1.3 論文結(jié)構(gòu)8-9
• 第二章 預(yù)備知識(shí)9-16
• 2.1 組合優(yōu)化理論9-12
• 2.2 一維裝箱問題及典型算法12-16
• 第三章 具有不同容量的裝箱問題及其算法16-36
• 3.1 問題描述16
• 3.2 Friesen-Langston算法16-19
• 3.3 FFDLSR算法19-20
• 3.4 FFDLSR算法正確性20-36
• 結(jié)論36-37
• 參考文獻(xiàn)37-39
• 致謝39

【參考文獻(xiàn)】

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

1 越民義;A SIMPLE PROOF OF THE INEQUALITY FFD (L)≤11/9 OPT(L)+1, ■L FOR THE FFD BIN-PACKING ALGORITHM[J];Acta Mathematicae Applicatae Sinica(English Series);1991年04期

，

本文編號(hào)：940582