分批排序、可拒绝排序及离散可控排序中的若干问题

摘要

排序理论一直是组合优化领域的一个热门方向，有坚实的应用背景和深刻的理论意义.分批排序、可拒绝排序及离散可控排序都是比较新的排序模型，本文就这三个模型做了以下一些工作： 1.本文指明了单台机器上工件有不同到达时间极小化总完工时间的无穷批量问题在一种新的编码下是NP-难的；就有任意多个到达时间极小化最大完工时间的分批排序问题，本文给出了一致不相关机上的PTAS算法；对于工件有尺寸极小化最大完工时间的分批排序问题，在工时与工件尺寸成比例且比例系数为常数时，我们给出了问题的一个下界3/2，设计出了渐进PTAS算法. 2.本文首次研究了可拒绝排序的约束模型以及工件不同时到达的可拒绝排序.对于在总惩罚费用的约束下极小化加权总完工时间的问题，证明了其NP-难性，设计出了FPTAS算法；对于极小化总惩罚费用与最大完工时间之和的问题，证明了其NP-难性，设计出了PTAS算法，并对只有两个到达时间的情形设计出了竞争比为(√5+1)/2的最有竞争性的在线算法. 3.本文证明了在总压缩费用的约束下极小化最大完工时间的离散可控排序问题是NP-难的，设计出了FPTAS算法；我们指明了极小化总压缩费用与加权总完工时间之和的离散可控排序问题是NP-难的，给出了一个在一定条件下具有有限近似比的启发式算法.大量的数值试验表明，此算法的平均性能是很好的.

目录

文摘

英文文摘

第一章绪论

第二章分批排序中的若干问题

第三章可拒绝排序和离散可控排序中的若干问题

参考文献

附录一附表

附录二硕士生期间发表或完成的论文

附录三致谢