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

摘要

在计算机科学和工业领域中，装箱问题有着广泛的应用背景，包括多处理器任务调度、资源分配、剪裁和现实生活中包装、整理物件等。在计算机科学中，文件分配、内存管理等低层操作均是装箱问题的实际应用，而装箱问题的各种算法如首次适应、最佳适应等策略在这些领域已经得到广泛的应用。 在至今的局内装箱问题研究当中，除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算法的最坏情况渐进执行比。

目录

文摘

英文文摘

论文说明：插图索引、附表索引

湖南大学学位论文原创性声明及学位论文版权使用授权书

第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.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.2MAREL算法设计

3.2.1数据项区间划分

3.2.2算法的基本原理

3.2.3算法的装箱策略

3.2.4数据结构

3.3算法的主要过程

3.3.1Insert(b,A)

3.3.2Extract(b,A)

3.3.3Move(b B A)

3.3.4Fill(c)

3.3.5Move The Gap (c)

3.3.6MAREL算法主要内容

3.4小结

第4章允许数据项移动的局内装箱算法MAREL分析

4.1算法的分析

4.1.1数据项的移动分析

4.1.2算法的空间复杂度分析

4.1.3算法的时间复杂度分析

4.1.4算法的性能分析

4.2性能比较

4.3小结

第5章受位置约束的有色装箱问题的局内算法KC-LIBA的设计

5.1有色装箱问题与经典一维装箱问题的关系

5.2受位置约束有色装箱问题

5.3受位置约束的有色装箱问题的KC-LIBA算法

5.3.1算法的特征

5.3.2KC-LIBNF算法

5.3.3KC-LIBFF算法

5.4小结

第6章受位置约束的有色装箱问题的局内算法KC-LIBA分析

6.1平均性能分析

6.2最坏情况渐进性能比分析

6.2.1KC-LIBNF算法最坏情况渐进执行比分析

6.2.2KC-LIBFF算法最坏情况渐进性能比分析

6.3小结

结 论

参考文献

致 谢

附录A攻读学位期间所发表的学术论文目录