具有不同容量的装箱问题

发布时间：2017-09-29 07:00

  本文关键词：具有不同容量的装箱问题

  更多相关文章： 不同容量的装箱 (渐近)近似算法 复杂性

【摘要】：一维装箱问题是指把一个物品序列装入单位容量的箱子中,目标是使得所使用的箱子数目达到最少。本论文研究一维装箱问题的一种推广形式,即具有不同容量的装箱问题。其叙述如下：给定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 组合优化理论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