有资源限制的分批排序问题的算法研究

论文摘要

排序问题是组合优化领域的一个重要分支，它有着重要的应用背景和深刻的理论意义．而分批排序是继经典排序之后的较新排序模型之一．本文就这一模型的有资源限制的问题做了一些工作．全文共分四章．第一章简单介绍了排序问题的相关定义、记号及相关预备知识．第二章考虑了单机分批排序问题中目标是极小化加权总完工时间的问题．将FBLW算法进行推广，就工件到达时间均为正整数、加工时间恒为1的情形，设计出了一个时间复杂性为O（n2 log n）的最优算法；对工件有常数m个到达时间、加工时间恒等的情形给出一个最优算法，并给出其算法复杂性为O(2m-1n log n)．第三章研究了分批排序中机器有使用限制的两个问题．这是首次将机器有使用限制的条件在分批排序问题中进行考虑．对于目标是极小化最大完工时间、工件不可中断的单机分批排序问题，我们对批容量无限的情形找到了多项式时间的最优算法，对批容量有限的情形提出了一个最差性能比为4／3的近似算法，并且界是紧的．第四章总结了全文并指出了有待研究的排序问题．

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• §1.1 排序的概念及其应用背景
• §1.2 排序问题的表示
• §1.3 计算复杂性
• §1.4 分批排序
• §1.5 本文主要成果及创新
• jC_j的分批排序问题'>第二章 一种极小化∑ω_jC_j的分批排序问题
• §2.1 问题的研究现状
• §2.2 工件有常数个到达时间、加工时间恒等的情形
• §2.3 工件到达时间均为正整数、加工时间恒为1的情形
• §2.4 结束语
• 第三章 机器有使用限制的分批排序问题的算法研究
• §3.1 问题描述及研究现状
• §3.2 一些用到的记号
• max'>§3.3 批容量有限的情形1|nr-α,B|C_max
• max'>§3.4 批容量无限的情形1|nr-α,B=∞|C_max
• §3.5 结论
• 第四章 总结与展望
• 参考文献
• 硕士生期间撰写的论文
• 致谢