| 【中文题名】 | 带传递时间的通信模型中的树约束排序问题 |
| 【英文题名】 | Scheduling Problem_with Delivery Times between Tasks Whose Precedence Constraints Are Formed to an Outtree in a Communication Model |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-8-20 |
| 【中关键词】 | 排序,拟传递时间,算法复杂性,多项式时间归结,出树, |
| 【英关键词】 | scheduling,pseudo-delivery time,Algorithm complexity,Multinomial time conclusion,outtree, |
| 【分类导航】 | 数理科学和化学>数学>运筹学>统筹方法>> |
| 【论文摘要】 |
本文主要讨论一类平行机带传递时间，且任务的先后加工顺序约束于一棵出树，目标函数为极小化时间表长的排序问题。即
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 |
|
| 【DOI】 | LunWen.ID:2.2008.14829 |
