允许数据项移动和受位置约束的局内装箱算法的研究

论文摘要

在计算机科学和工业领域中,装箱问题有着广泛的应用背景,包括多处理器任务调度、资源分配、剪裁和现实生活中包装、整理物件等。在计算机科学中,文件分配、内存管理等低层操作均是装箱问题的实际应用,而装箱问题的各种算法如首次适应、最佳适应等策略在这些领域已经得到广泛的应用。 在至今的局内装箱问题研究当中,除Giorgio在2000年提出一种数据项可移动的局内装箱算法之外,所有的局内装箱算法中的数据项均是不能移动的,即输入序列中的数据项一旦入箱,就不能再移动,并且在所有数据项处理完后,均不能释放部分曾经被装过数据项的箱子。 论文为了进一步提高局内装箱近似算法的最坏情况渐进性能比,改进Giorgio提出的数据项移动模型,提出MAREL局内算法,算法中数据项所属区间(0,1]划分为8个并不均等且不相交的子区间:I0,I1,I2,I3,I4,I5I6,I7。I7-数据项当作能被聚集的“小”数据项,且能整体（组）移动,插入I1-箱,I2-箱,I3-箱,I4-箱和I5-箱当中。MAREL算法的空间复杂度是O（n）,时间复杂度是O（nlogn）,最坏情况渐近性能比为1.25。该算法的最坏情况渐进性能比低于同类算法的最坏情况渐进性能比,并且低于局内装箱算法渐近性能比理论上的下确界1.536…,同时低于目前所有的局内装箱近似算法的最坏情况渐进性能比。 此外,本文还首先提出受位置约束的有色装箱问题。它在有色装箱问题的基础上加上一个约束:在有色装箱的过程中要满足重（长）的物品置于轻（短）的物品下方的原则,同时使所用的箱子数最少。论文给出了求解受位置约束的有色装箱问题的KC-LIBA算法,它首先对输入物品进行分类预处理,然后在同一类箱子内部使用经典装箱问题的近似策略A,并且重（长）的物品置于轻（短）物品下方的原则。给出了以受位置约束的经典一维装箱问题的近似算法A为基础的K-分类算法的最坏情况渐进性能比的下界。分析了当选用的受位置约束的算法A是著名装箱算法NF和FF时,KC-LIBNF以及KC-LIBFF算法的最坏情况渐进执行比。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 经典一维装箱问题
• 1.2 局内装箱算法的研究现状
• 1.3 本文的主要研究工作
• 1.4 本文组织结构
• 第2章 装箱问题的近似算法及性能分析
• 2.1 近似算法的评价标准
• 2.1.1 算法的局内特性
• 2.1.2 算法的时间复杂度
• 2.1.3 算法的空间复杂度
• 2.1.4 算法的最坏情况渐进性能比
• 2.1.5 算法的平均性能比
• 2.2 装箱问题的近似算法
• 2.2.1 下次适应算法
• 2.2.2 任意适应算法
• 2.2.2.1 首次适应算法
• 2.2.2.2 最佳适应算法
• 2.2.2.3 最坏适应算法
• 2.2.3 降序任意算法
• 2.2.4 RFF算法
• 2.2.5 调和算法
• 2.3 数据项移动算法
• 2.3.1 数据项成组定义
• 2.3.2 数据项移动
• 2.3.3 算法的装箱策略
• 2.4 有色装箱问题的KC-A算法
• 2.4.1 有色装箱问题定义
• 2.4.2 KC-A算法
• 2.5 小结
• 第3章 允许数据项移动的局内装箱算法的设计
• 3.1 设计思想
• 3.2 算法设计
• 3.2.1 数据项区间划分
• 3.2.2 算法的基本原理
• 3.2.3 算法的装箱策略
• 3.2.4 数据结构
• 3.3 算法的主要过程
• 3.3.1 插入过程
• 3.3.2 弹出过程
• 3.3.3 移动过程
• 3.3.4 填充过程
• 3.3.5 回收过程
• 3.3.6 允许数据项移动的局内装箱算法主要内容
• 3.4 小结
• 第4章 允许数据项移动的局内装箱算法分析
• 4.1 算法的分析
• 4.1.1 数据项的移动分析
• 4.1.2 算法的空间复杂度分析
• 4.1.3 算法的时间复杂度分析
• 4.1.4 算法的性能分析
• 4.2 性能比较
• 4.3 小结
• 第5章 受位置约束的有色装箱问题的局内算法的设计
• 5.1 有色装箱问题与经典一维装箱问题的关系
• 5.2 受位置约束有色装箱问题
• 5.3 受位置约束的有色装箱问题的算法
• 5.3.1 算法的特征
• 5.3.2 下次适应算法
• 5.3.3 首次适应算法
• 5.4 小结
• 第6章 受位置约束的有色装箱问题的局内算法分析
• 6.1 平均性能分析
• 6.2 最坏情况渐进性能比分析
• 6.2.1 下次适应算法最坏情况渐进执行比分析
• 6.2.2 首次适应算法最坏情况渐进性能比分析
• 6.2.2.1 数据项的尺寸从小到达排列
• 6.2.2.2 数据项的尺寸从大到小排列
• 6.2.2.3 数据项的尺寸为一般情况
• 6.3 小结
• 结论
• 参考文献
• 致谢
• 附录A 攻读学位期间所发表的学术论文目录