具有不同容量的装箱问题.pdf

《具有不同容量的装箱问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级好编号碎士蚵究嗲像洽夂题目具有不同容量的装箱问鼸学院（所、中心）数学与统计学院专业名称计算数学研究生姓名徐霞学号导师姓名李建平职称教授年月论文独创性声明及使用授权本论文是作者在导师指导下取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人己经发表或撰写过的研究成果，不存在剽窃或抄袭行为。与作者一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。现就论文的使用对云南大学授权如下：学校有权保留本论文（含电子版），也可以釆用影印、缩印或其他复制手段保存论文；学校有权公布论文的全部或部分内容，可以将论文用于查阅或借阅服务；学校有权向有关机构送交学

2、位论文用于学术规范审查、社会监督或评奖；学校有权将学位论文的全部或部分内容录入有关数据库用于检索服务。内部或保密的论文在解密后应遵循此规定）摘要一维装箱问题是指把一个物品序列装入单位容量的箱子中，目标是使得所使用的箱子数目达到最少。本论文研究一维装箱问题的一种推广形式，即具有不同容量的装箱问题。其叙述如下：给定？！个物品序列乃一化，勿，⋯，知，每个物品的尺寸这里，，，，给定种不同容量的箱子若干，每种箱子的容量为卿，，这里要求将物品序列仏⑷，叱，⋯，如库入若干个箱子中，且每个箱子中的物品尺寸和不超过箱子的容量，目标是使得所使用箱子的容量之和达到最小。对于具有不同容量的装箱问题，和设计了三个有

3、效的渐近近似算法，即算法，算法和兀算法，它们的渐近近似值分别为，。本论文修正了算法的一些策略，设计出一个渐近近似算法，其复杂性为⋯。关键词：不同容量的装箱；（渐近近似算法；复杂性AbstractTheone-dimensionalbinpackingproblemistopackalistofitemsintobinsofunitcapacity,itsobjectiveistominimizethenumberofthebinsused.Inthisthesis,westudyageneralizationoftheone-dimensionalbinpackingproblem,i.e

4、.thevariable-capacitybinpackingproblem.Itisdefinedasfollows:givenalistL=(ai,a2,...,an)ofnitems,eachitema;withsize5(ai)e(0，，，，，，，，，目录摘要第一章引言理论背景主要结果论文结构第二章预备知识组合优化理论一维装箱问题及典型算法第三章具有不同容量的装箱问题及其算法问题描述算法咒仏紐算法正确性结论参考文献致谢第一章引言§理论背景一维装箱问题是一种经典的组合最优化问题，一维装箱问题具体描述如下：给定个物品序列，每个物品叫的尺寸为这里，要求把所有物品装入若干个单位容量的箱子中

5、，目标是使得所使用的箱子数目达到最少。一维装箱问题来源于人们长期以来的生产实践，具有很高的理论价值和现实意义。一维装箱问题是一个经典的完备问题这意味着如果该问题不存在在多项式时间内求得精确解的算法，所以我们主要研究解决一维装箱问题的近似算法，因此一维装箱问题具有很高的理论价值。一维装箱问题在计算机科学，工程领域及现实生活中都具有广泛的应用，如文件分配、内存管理、多处理器任务调度、资源分配、板材切割以及现实生活中货物包装布局等，因此，一维装箱问题具有很高的实践价值。对于一维装箱问题，目前人们提出了许多求解的近似算法，所谓近似算法是指该算法可以求得与精确解接近的结果，但不一定得到精确解。为了评

6、价一个算法的性能，引入了不同的方法。对于一个近似算法■，对于一维装箱问题的任意实例，用⑷记近似算法把所有物品完全装箱所使用的箱子数目，用戶⑷记最优算法所使用的箱子数目（即最少必须使用的箱子数目），则算法■的近似值定义为。辱）相应的定义算法的渐近近似值为思―盖為’￠目前，一维装箱问题的研究比较成熟，一些近似算法被提出。对于一维装箱问题，等人⑷在年设计了算法力糾认简记为，其渐近近似值为，复杂性为。等人，在年设计了算法如，简记为、算法，简记为它们的渐近近似值都为，复杂性都为。在年设计了算法简记为并且对于一维装箱问题的所有实例，算法产生了一个可行解，满足，不过这个证明很复杂。后来，在年给出了一个稍

7、微简单的证明，且把附加常数从降到了。在年给出了一个比较简单的证明，且把附加常数从降到了。在年给出了一个相对最简单的证明，且把附加常数从降到了。在年证明了算法是解决一维装箱问题的近似算法，且在一般情况下，这是一个比较好的结果。算法复杂性为。本论文主要研究具有不同容量的装箱问题、简记为，注意：有些文章中把该问题称为它是一维装箱问题的一种推广形式，它通过增加一种或几种不同型号的箱子来提高装箱效率。具有不同容量的装箱问题具体描述