多任务调度问题的研究与实现

发布时间：2021-06-18 11:39

　　本课题的研究对象是分布式环境下的多任务静态调度问题。研究求解该问题的高效近似算法具有极高的理论价值和实践价值。这个问题是强NP完全的,是最难的组合优化问题之一。各国学者已对它做了十多年的深入研究,并提出了多种调度模型和算法。一般用有向无回路图（Directed Acyclic Graph, DAG）来描述有优先关系的任务集,目前文献中只给出了有向无回路图的存在性定义。本文提出了有向无回路图的两种构造性定义,使DAG直观化、可操作化。然后将问题的约束归纳为任务约束、链路约束和资源约束,给出了分布式环境下多任务静态调度问题的统一的、完整的描述和形式化的定义,证明了这个问题是可计算的但也是强NP完全的,不存在任何常数近似比的多项式时间近似算法。遵循从简单到复杂、循序渐进的研究方法,深入地研究了同构环境下的多任务静态调度问题。前人在这个问题的描述上,虽然采用加权的DAG描述问题,但没有建立问题的约束和目标的完整数学模型,尤其是允许任务复制的情况;另外对资源的数目,或者假设有无穷多,或者作为一个参数传入。本文将约束条件归纳为任务约束、链路约束和资源约束,并将资源数限定为与任务数一样多,给出了允许... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：143 页

【学位级别】：博士

【部分图文】：

多级的资源调度结构

以上分析可得出，对于树型和规则对称的 DAG 图，IREA 的求解优度中有 6 个算例得到了比上述 5 个算法更优的解。对不规则不对称的 D情况不是太好，但不是最差的，进一步分析对 NEQ 和 IRR 的求解过程务间的互连边较多，动态分团对其几乎不起作用，下一步将考虑如何改进对任务间互连边较多的 DAG 的求解。

中有 6 个算例得到了比上述 5 个算法更优的解。对不规则不对称的 D情况不是太好，但不是最差的，进一步分析对 NEQ 和 IRR 的求解过程务间的互连边较多，动态分团对其几乎不起作用，下一步将考虑如何改进对任务间互连边较多的 DAG 的求解。图 4.7 加速比比较

【参考文献】：
期刊论文
[1]网格环境下资源调度问题的统一建模与分析[J]. 何琨,赵勇.  华中科技大学学报(自然科学版). 2006(03)
[2]一个调度Fork-Join任务图的最优算法（英文）[J]. 李庆华,阮幼林,刘干,蒋盛益,杨世达.  软件学报. 2005(05)
[3]网络集群计算系统中的并行任务调度[J]. 黄金贵,陈建二,陈松乔.  计算机学报. 2004(06)
[4]一个调度Fork-Join任务图的新算法[J]. 刘振英,方滨兴,姜 誉,张 毅,赵 宏,张 毅.  软件学报. 2002(04)
[5]任务分配与调度的共同进化方法[J]. 钟求喜,谢涛,陈火旺.  计算机学报. 2001(03)

博士论文
[1]网格工作流关键技术研究[D]. 张绍华.复旦大学 2004



本文编号：3236595