一维装箱问题启发式算法的设计与分析

摘要

装箱问题是经典的组合优化问题之一，它作为一种最早研究的NP-难解问题和复杂性理论的研究平台，为其它NP-难解问题的研究提供了诸多借鉴。装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等各领域有着广泛的应用背景。装箱问题已经有五十多年的研究历史，在此期间，许多著名的组合优化领域的学者，如:E.G.Coffman，D.S.Johnson以及图灵奖获得者A.C.Yao等为装箱问题创建了比较完善的理论和丰富的算法。目前，对于装箱问题及其算法的研究仍然是组合最优化领域的重要问题之一，具有广阔的研究空间。
　　按照Coffman等人的总结，装箱问题的启发式算法研究可以分成三个方面:提出有效的近似算法并分析算法的性能;确定算法的性能界限;考虑与实际应用关系更紧密的、带各类约束的装箱问题。本文遵循该思路进行了研究，其主要内容如下:
　　对于一维装箱问题提出一种带缓冲箱的启发式算法，通过对Benchmark问题的求解，对所提算法与其他经典算法的性能进行了对比分析;对所提算法进行了时间及空间复杂性分析和最坏性能比分析。分析该算法自身参数对性能的影响。
　　关于带约束装箱问题的研究:本文根据实际应用需要，提出了一种工件分批到达的装箱问题，同时给出了该问题一个基于动态规划的近似算法，分析该算法的时间及空间复杂度，最坏性能比。
　　最后，总结了本文的工作并展望了迸一步的研究方向。

目录

声明

摘要

第1章 绪论

1．1 研究背景与发展现状

1．1．1 研究背景

1．1．2 发展现状

1．2 装箱问题分类

1．2．1 按照装箱物体所属装箱空间对装箱问题的分类

1．2．2 按照装箱物体的形状对装箱问题的分类

1．2．3 按照装箱物体达到情况对装箱问题的分类

1．3 经典装箱算法

1．3．1 在线算法

1．3．2 离线算法

1．3．3 半在线算法

1．3．4 并行算法

1．4 本文研究工作和结构

1．4．1 本文的主要工作

1．4．2 论文的结构

1．5 本章小结

第2章 装箱问题基本概念、算法和结论

2．1 基本概念

2．1．1 装箱问题概念

2．1．2 最坏情况性能比概念

2．1．3 平均情况性能概念

2．1．4 算法概念

2．2 基本结论

2．2．1 下次适应算法

2．2．2 首次适应算法

2．2．3 空间受限的在线算法

2．2．4 降序首次|最佳适应算法

2．3 本章小结

第3章 求解一维装箱问题的带缓冲箱的启发式算法

3．1 带缓冲箱的启发式算法的提出

3．1．1 问题分析

3．2 带缓冲箱的启发式算法

3．2．1 带缓冲箱的启发式算法的算法设计

3．2．2 带缓冲箱的启发式算法的算法复杂性分析

3．3 带缓冲箱的启发式算法性能的实验分析

3．3．1 平均性能比的分析

3．3．2 最坏性能比的分析

3．4 实验计算

3．5 本章小结

第4章 成批到达约束的装箱问题

4．1 问题的提出

4．2 动态规划技术

4．3 成批到达约束的装箱问题的启发式算法

4．3．1 批次停留为零的批次到达的装箱问题

4．3．2 批次停留非零的批次到达的装箱问题

4．4 实验计算

4．4．1 批次到达的装箱问题的实验分析

4．4．2 带停留次数约束的批次到达装箱问题的实验分析

4．5 本章小结

第5章 总结与展望

5．1 本文工作

5．2 进一步工作

参考文献

致谢

参加项目