本文關鍵詞：具有不同容量的裝箱問題

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

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

• 摘要3-4
• Abstract4-6
• 第一章 引言6-9
• 1.1 理論背景6-8
• 1.2 主要結果8
• 1.3 論文結構8-9
• 第二章 預備知識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
• 結論36-37
• 參考文獻37-39
• 致謝39

【參考文獻】

中國期刊全文數據庫 前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期

，

本文編號：940582