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

论文摘要

本文主要讨论一类平行机带传递时间，且任务的先后加工顺序约束于一棵出树，目标函数为极小化时间表长的排序问题。即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|C_max'>§3.2 排序问题P_m|delivery-times,outtree|C_max
• 第四节 算法及其性能分析
• §4.1 一般出树约束下的算法
• §4.2 处理机数大于任务数时的算法
• §4.3 下一步的工作
• 参考文献
• 致谢