Print

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

论文摘要

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

论文目录

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

    • 相关论文文献

    本文来源: https://www.lw50.cn/article/6d51fe6712a198a201919da0.html