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

带传递时间的通信模型中的树约束排序问题

作　者: 马蕾
导　师: 王海明
学　校: 兰州大学
专　业: 运筹学与控制论
关键词: 排序拟传递时间算法复杂性多项式时间归结出树
分类号: O223
类　型: 硕士论文
年　份: 2007年
下　载: 15次
引　用: 0次
阅　读: 论文下载

内容摘要

本文主要讨论一类平行机带传递时间，且任务的先后加工顺序约束于一棵出树，目标函数为极小化时间表长的排序问题。即P_m|pseudo-delivery times，outtree|C_max。首先给出排序问题P_m|pseudo-delivery times，outtree|C_max的一个实例排序问题（k-OPTS）。通过将背包问题（KNP）归结为限制背包问题（k-KNP），将限制背包问题（k-KNP）归结为排序问题（k-OPTS）来证明排序问题P_m|pseudo-delivery times，outtree|C_max是NP-完全的。然后给出了适合所有情况的启发式算法，并证明了算法的复杂性为O（n）。进而对任务数小于机器数的特殊情况给出了一个启发式算法，并证明了算法的最优性及算法复杂性为O（nβ／log n）。

全文目录

中文摘要  4-5
英文摘要  5-7
第一节引言  7-11
第二节基本概念、符号说明及已知结论  11-16
  §2.1 计算复杂性的一些概念  11-13
  §2.2 符号说明  13-14
  §2.3 一些已知道性质的平行机排序问题  14-16
第三节带传递时间加工任务优先约束为出树的平行机排序问题  16-27
  §3.1 相关概念及一些预备定理  16-18
  §3.2 排序问题P_m|delivery-times,outtree|C_(max)  18-27
第四节算法及其性能分析  27-32
  §4.1 一般出树约束下的算法  27-29
  §4.2 处理机数大于任务数时的算法  29-31
  §4.3 下一步的工作  31-32
参考文献  32-35
致谢  35

带传递时间的通信模型中的树约束排序问题

内容摘要

全文目录

相似论文