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

带参数的平行机和流水作业排序问题的复杂性及算法研究

作　者: 徐春
导　师: 时凌
学　校: 湖北民族学院
专　业: 基础数学
关键词: 平行机排序问题流水作业排序问题复杂性启发式算法运输时间
分类号: O223
类　型: 硕士论文
年　份: 2010年
下　载: 15次
引　用: 0次
阅　读: 论文下载

内容摘要

平行机及流水作业排序问题是多处理机排序问题的一种情况，其研究在理论和应用上都有重要意义．本文考虑四个排序问题，并且讨论它们的复杂性及启发式算法．第一个问题：研究带单服务器的两台平行机排序问题的复杂性．每个工件在机器加工之前，必须由服务器先进行安装，在同一时刻每一个服务器只能安装一个工件，目标是使最大完工时间达到最小．在工件具有准备时间且所有加工时间等于1的条件下，证明该问题是强NP困难的；第二个问题：研究两台机器情况下的流水作业排序问题的复杂性，目标函数为使最大完工时间达到最小．同一工件在某台机器上完工后和在下一台机器上开始加工这段时间内，存在称为运输时间的时间间隔，所有的运输时间均由自动机完成，自动机在同一时间内最多运输一个工件，证明该特殊情况下的此问题是强ⅣP困难的；第三个问题：研究两台机器情况下的流水作业排序问题的复杂性，目标函数为使加权完工时间总和达到最小．证明该特殊情况下的此问题是强ⅣP困难的，并给出一个启发式算法，证明它的紧界为3/2；第四个问题：研究带准备时间的两台机器情况下的流水作业排序问题的复杂性，目标函数为使加权完工时间总和达到最小．工件有一个准备时间rl，证明该特殊情况下的此问题是强Np难的，并给出一个启发式算法，证明它的紧界为3/2．

全文目录

摘要  3-4
Abstract  4-7
第1章绪论  7-9
第2章带单服务器的平行机排序问题的复杂性  9-12
  2.1 模型描述  9
  2.2 复杂性  9-12
第3章带自动机的流水作业问题的复杂性  12-16
  3.1 模型描述  12-13
  3.2 复杂性  13-16
第4章带运输时间的流水作业问题的复杂性与启发式算法  16-22
  4.1 模型描述  16
  4.2 复杂性  16-20
  4.3 启发式算法  20-22
    4.3.1 算法  20
    4.3.2 紧界  20-22
第5章带准备时间的流水作业问题的复杂性与启发式算法  22-29
  5.1 模型描述  22-23
  5.2 复杂性  23-26
  5.3 启发式算法  26-29
    5.3.1 算法  26
    5.3.2 紧界  26-29
结论  29-30
参考文献  30-33
攻读学位期间发表的学术论文  33-34
致谢  34

带参数的平行机和流水作业排序问题的复杂性及算法研究

内容摘要

全文目录

相似论文