一维捆绑式装箱问题

发布时间：2017-07-19 16:22

  本文关键词：一维捆绑式装箱问题

  更多相关文章： 一维捆绑式装箱问题 K-组装箱 渐进(近似)算法

【摘要】：本文对一维装箱问题进行了推广,提出了一个新的问题,称为一维捆绑式装箱问题。一维捆绑式装箱问题的具体描述如下：给定n个物品的序列I=(a1,a2,...,an),每个物品尺寸为s(ai)∈(0,l],这里i=1,2,...,n,提供若干个K-组装箱,把I中的物品装入若干个K-组装箱中,要求每个小箱子所装物品的尺寸之和不超过l,目标是使得所使用的K-组装箱的数目达到最小,其中一个K-组装箱由K个尺寸为l的箱子捆绑组成,K-组装箱的尺寸为l。为了解决一维捆绑式装箱问题,本文设计了K-NF算法、]K-FFD算法和K-SFOF算法三个离线算法,其中K-NF算法的近似值为2,复杂性为O(n)；K-FFD算法和K-SFOF算法的渐进近似值都为3/2,时间复杂性分别为O(n2)和O(n)。同时本文设计一个在线渐进近似算法-K-SFON算法,该算法的渐进近似值为7/4,时间复杂性为O(n)。
【关键词】：一维捆绑式装箱问题 K-组装箱 渐进(近似)算法
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O224
【目录】：

• 摘要3-4
• Abstract4-6
• 第一章 引言6-9
• 1.1 理论背景6-7
• 1.2 主要结果7-8
• 1.3 论文结构8-9
• 第二章 预备知识9-16
• 2.1 组合最优化9-11
• 2.2 近似算法11-13
• 2.3 一维装箱问题及算法13-16
• 第三章 一维捆绑式装箱问题及其算法设计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
• 结论40-41
• 附录41-59
• 参考文献59-61
• 致谢61

【相似文献】

中国期刊全文数据库 前10条

1 杨殿生;求解装箱问题的一种变长度染色体遗传算法[J];长春工程学院学报(自然科学版);2004年02期

2 刘林浩;杨鼎强;王晨;;一种带脆度的尺寸可变装箱问题[J];计算机工程与应用;2013年12期

3 杜林古,孙孝瑞;风向图上两问题的复杂性[J];青岛大学学报(自然科学版);1997年01期

4 闵孟斌;锁具装箱问题的最大不互开锁数的理论证明[J];数学的实践与认识;2000年04期

5 孙春玲,陈智斌,李建平;装箱问题的一种新的近似算法[J];云南大学学报(自然科学版);2004年05期

6 解其生,李维仙,吴欣明;用综合试探法提高一维装箱问题的性能[J];廊坊师范学院学报;2004年04期

7 孙春玲;染色的装箱问题及其近似算法[J];云南民族大学学报(自然科学版);2005年03期

8 孙春玲;染色装箱问题及其启发式算法[J];云南民族大学学报(自然科学版);2005年04期

9 汤岩;胡俊敏;武立丰;;一种改进的二维装箱问题的混合遗传算法[J];集美大学学报(自然科学版);2006年03期

10 陈德良;陈治亚;;三维装箱问题的模型与改进遗传算法[J];数学的实践与认识;2010年02期

中国重要会议论文全文数据库 前4条

1 张国川;;组合优化算法研究-从装箱问题说起[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

2 陈锋;邢文训;;在线塔状装箱问题(英文)[A];中国运筹学会第六届学术交流会论文集（上卷）[C];2000年

3 ;Voronoi Diagram Approximate the Extreme Packing and Its Applications[A];中国运筹学会第六届学术交流会论文集（上卷）[C];2000年

4 董杰方;张汉欣;李安平;;冷卷入库的数学模型及算法[A];2001中国钢铁年会论文集（下卷）[C];2001年

中国博士学位论文全文数据库 前5条

1 赵晓凡;在线装箱问题相关近似算法研究[D];北京交通大学;2016年

2 王俊岭;矩形装箱问题的协同决策模型[D];兰州大学;2013年

3 于洪霞;二维装箱问题的非线性优化方法[D];大连理工大学;2006年

4 余国松;与装箱相关的几类问题[D];浙江大学;2009年

5 石永强;若干批处理机排序与装箱问题的算法研究[D];浙江大学;2005年

中国硕士学位论文全文数据库 前10条

1 江瀑;组合装箱问题模型与算法研究[D];上海交通大学;2015年

2 王骁;汽车零部件物流中心三维装箱问题研究[D];大连理工大学;2015年

3 高伟;多约束有色三维装箱问题的混合遗传算法研究[D];长沙理工大学;2014年

4 朱园;基于多智能体进化算法的布图方法及三维装箱方法[D];西安电子科技大学;2014年

5 宋园春;关于带冲突装箱问题的若干优化算法研究[D];天津大学;2014年

6 梁佳雯;汽车下一代车载网络调度算法的研究[D];贵州师范大学;2016年

7 王明明;一维捆绑式装箱问题[D];云南大学;2016年

8 邱朝阳;考虑重量约束的集装箱装箱问题[D];华南理工大学;2010年

9 王钟;染色装箱问题的相关研究[D];浙江大学;2007年

10 刘林浩;关于脆度装箱问题的若干研究[D];长沙理工大学;2013年

，

本文编号：563776