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

若干车间排序问题和最短路问题的组合问题

作　者: 聂嘉明（Nip Kameng）
导　师: 王振波
学　校: 清华大学
专　业: 数学
关键词: 车间排序最短路组合优化的组合问题计算复杂性近似算法
分类号: O223
类　型: 硕士论文
年　份: 2013年
下　载: 26次
引　用: 0次
阅　读: 论文下载

内容摘要

本文研究了一些由三个经典的车间排序问题,和最短路问题各自组合而成的组合问题。问题的目的是在一个工件集中选取一个子集,使其构成一个最短路问题的可行解,然后把工件安排到一个车间进行排序,使所得排序的最大完工时间最小。本文先对这些问题的计算复杂性进行研究。第一个结果是即使在只有两台机器的情况下,这些问题仍是NP难的。第二个结果是当机器数目作为问题的输入时,除非P=NP,这些问题不存在近似比小于2的多项式近似算法。随后根据每一个问题的特点设计相应的近似算法,并对这些算法的时间复杂性和近似比进行分析。最后讨论把问题的结果推广到车间排序和最小支撐树,或和一个更广泛的covering问题的组合问题上。本文表明前面的研究结果基本都可以推广到车间排序和这两个问题各自的组合问题上。本文主要的创新点如下:1.通过结合车间排序问题和最短路(最小支撐树、covering)问题,提出一系列新的组合优化问题,并证明了这些问题的计算复杂性和提出了相应的近似算法。2.针对车间排序问题的特点,提出了一个比covering问题更广泛的问题,把它应用到车间排序问题和它的组合问题的定义上,并得到一个对组合优化问题的组合问题适用性更广泛的定义。3.对于这些组合问题,根据车间排序问题的已有算法返回的解的特点,通过重复迭代算法和修正权重的思想,设计出一系列有效求解的近似算法,同时进一步扩展了这个思想的应用。

全文目录

摘要  3-4
Abstract  4-5
目录  5-9
第1章引言  9-17
  1.1 组合优化问题的组合问题  9-11
  1.2 车间排序问题  11-12
  1.3 最短路及其相关问题  12-13
  1.4 计算复杂性及近似算法  13-15
  1.5 本文主要工作及內容安排  15-17
第2章车间排序问题和最短路问题的组合问题  17-25
  2.1 本文研究问题模型  17-18
  2.2 车间排序问题的复杂性与算法  18-24
    2.2.1 Fm||Cmax的复杂性与算法  18-20
    2.2.2 Om||Cmax的复杂性与算法  20-21
    2.2.3 Jm||Cmax的复杂性与算法  21-24
  2.3 最短路及相关问题的复杂性与算法  24-25
第3章流水车间排序和最短路问题的组合  25-37
  3.1 计算复杂性  25-30
    3.1.1 一般情况下的复杂性  25-26
    3.1.2 F2|shortest path|Cmax的一些特例  26-28
    3.1.3 F|shortest path|Cmax的不可近似性  28-30
  3.2 Fm|shortest path|Cmax的近似算法  30-37
    3.2.1 自然的m-近似HD算法  30-32
    3.2.2 改进的（3m+1）／4 (1 + )-近似GFAR算法  32-37
第4章自由车间排序和最短路问题的组合  37-45
  4.1 计算复杂性  37
  4.2 HD算法和GFAR算法的推广  37-39
  4.3 O2|shortest path|Cmax的GO2AR算法  39-42
  4.4 Om|shortest path|Cmax的ROAR算法  42-45
第5章异序车间排序和最短路问题的组合  45-53
  5.1 计算复杂性  45
  5.2 HD算法的推广  45-46
  5.3 J2|op ≤ 2,shortest path|Cmax的JJAR算法  46-49
  5.4 Jm|shortest path|Cmax的SJAR算法  49-53
第6章扩展问题  53-60
  6.1 与最小支撑树问题的组合  53-56
    6.1.1 计算复杂性  53-54
    6.1.2 近似算法  54-56
  6.2 与covering问题的组合  56-60
第7章总结  60-62
参考文献  62-65
致谢  65-67
个人简历、在学期间发表的学术论文与研究成果  67

若干车间排序问题和最短路问题的组合问题

内容摘要

全文目录

相似论文