学位论文 > 优秀研究生学位论文题录展示

带尺寸、可拒绝的分批排序

作　者: 张咸昭
导　师: 张玉忠
学　校: 曲阜师范大学
专　业: 应用数学
关键词: 排序分批可拒绝 NP-困难最差性能比伪多项式时间 FPTAS 动态规划
分类号: O226
类　型: 博士论文
年　份: 2007年
下　载: 70次
引　用: 0次
阅　读: 论文下载

内容摘要

排序问题一直是组合优化领域的一个热门方向，有着坚实的应用背景和深刻的理论意义。带尺寸的分批排序、可拒绝排序都是比较新的排序模型，本文就这两个模型做了以下一些工作：1．本文主要对带尺寸的分批排序极小化完工时间和的问题进行了研究。对于问题1|B，s_j，p_j=1|∑C_j，运用拆分的技巧首次给出了近似比是常数的三个近似算法，近似比分别是4，2，和3／2．此外我们还给出例子表明后两个算法所给的界是紧的。接下来针对问题1|B，s_j|∑C_j，对已有的几个算法进行了分析，说明这几个算法的最差性能比是无穷大。2．首次对可拒绝的分批排序问题1|B≥n，rej|∑ω_jT_j+TP和1|B≥n，rej|∑ω_jU_j+TP进行了研究，在已知它们是NP-困难的基础上，我们给出了伪多项式时间精确算法以及FPTAS算法。这是最好的精确算法和近似算法；因为对于NP-困难问题，最好的精确算法就是伪多项式时间算法，而最好的近似算法也只能是FPTAS算法。

全文目录

摘要  3-4
ABSTRACT  4-8
第一章绪论  8-19
  1.1 应用背景及问题描述  8-14
    1.1.1 应用背景  8-9
    1.1.2 历史起源及研究概况  9-10
    1.1.3 经典排序与现代排序  10-11
    1.1.4 排序问题的表示  11-14
  1.2 预备知识  14-18
    1.2.1 排序问题的求解  14-15
    1.2.2 基本方法和技巧  15-16
    1.2.3 离线与在线  16
    1.2.4 几个常见的NP-困难问题  16-17
    1.2.5 几个经典算法  17-18
  1.3 本文主要结果及创新点  18-19
第二章工件带尺寸的分批排序的几个近似算法  19-32
  2.1 引言  19
  2.2 对于问题1|B,s_j,p_j=1|∑C_j的两个近似算法  19-24
  2.3 一个近似比更优的算法  24-31
  2.4 小结  31-32
第三章关于可拒绝无界分批排序问题的几点探讨  32-41
  3.1 引言  32-33
  3.2 对于问题1|B≥n,rej|∑ω_jT_j+TP的伪多项式算法  33-35
  3.3 问题1|B≥n,rej|∑ω_jU_j+TP的精确算法和近似算法  35-40
  3.4 结论  40-41
第四章对已有启发式算法的性能分析  41-47
  4.1 问题背景及描述  41-42
  4.2 研究概况  42-43
  4.3 算法及其分析  43-46
  4.4 结论  46-47
参考文献  47-51
博士生期间撰写的论文  51-52
致谢  52

带尺寸、可拒绝的分批排序

内容摘要

全文目录

相似论文