文档介绍：摘要
本课题的研究对象是分布式环境下的多任务静态调度问题。研究求解该问题的高
效近似算法具有极高的理论价值和实践价值。这个问题是强 NP 完全的,是最难的组
合优化问题之一。各国学者已对它做了十多年的深入研究,并提出了多种调度模型和
算法。
一般用有向无回路图(Directed Acyclic Graph, DAG)来描述有优先关系的任务集,
目前文献中只给出了有向无回路图的存在性定义。本文提出了有向无回路图的两种构
造性定义,使 DAG 直观化、可操作化。然后将问题的约束归纳为任务约束、链路约
束和资源约束,给出了分布式环境下多任务静态调度问题的统一的、完整的描述和形
式化的定义,证明了这个问题是可计算的但也是强 NP 完全的,不存在任何常数近似
比的多项式时间近似算法。
遵循从简单到复杂、循序渐进的研究方法,深入地研究了同构环境下的多任务静
态调度问题。前人在这个问题的描述上,虽然采用加权的 DAG 描述问题,但没有建
立问题的约束和目标的完整数学模型,尤其是允许任务复制的情况;另外对资源的数
目,或者假设有无穷多,或者作为一个参数传入。本文将约束条件归纳为任务约束、
链路约束和资源约束,并将资源数限定为与任务数一样多,给出了允许任务复制情况
下问题的完整描述和两种数学模型。证明了对 n 个任务的问题,给定 n 个资源足够找
到无穷多资源时的最优解,使对问题的认识更深入,并使问题的描述更趋于实际。采
用三种不同的方法证明了问题具有可计算性,从不同的角度帮助加深对问题的理解,
有利于想出好的策略。
调度方法以优先级列表、任务分簇、任务复制最具代表性,其中基于任务复制的
方法(Task Duplication Based, TDB)是效率最好的一种。各种 TDB 算法的理论基础
是采用以空间换时间的策略,通过冗余地分配任务到多个资源以减少通信开销,从而
减少总的调度长度。如何准确地确定应被复制的重要任务是获得较短 makespan 的关
键,TDB 算法之间的主要区别也正在于其选择复制任务的策略不同。本文基于任务复
制与分簇技术,提出了两种求解同构环境下多任务静态调度问题的高效近似算法。
关系演化算法(IREA)模拟人类社会的关系演化过程,是一种基于贪心分簇的启发
式算法,包括前沿调度、动态分团、分离图三个子算法。IREA 采用全新的优先级规
I
则,定义并采用关系数、发展潜力、权和归并度来表示簇的优先级,定义并采用任务
的发展潜力来表示任务的优先级。实验表明求解的结果颇好。
目前的 TDB 算法中,国外学者提出的两种先进算法 PY 和 MJD 算法对任意的 DAG
给出了性能保证,而其它算法仅部分算法对特定的 DAG 给出了性能保证。动态关键
前驱算法(DCP)借鉴理论上最优的 MJD 算法的思想,并针对其不足进行改进,采用新
的选择策略来定义待复制的重要祖先集。改进了粒度的定义,理论分析表明 DCP 算
法的优度好于其他近现代的典型 TDB 算法,对任意 DAG 和特定 DAG 均得到了好的
性能保证;实验求解的质量很高,且有若干算例得到了好于前人的最优解。定义了
DAG 图的补图,讨论了对树型 DAG 在无任务复制情况下的 2-优度的算法。
另外,目前同构环境下的多任务调度问题还没有形成标准的算例集。本文对目前
较为分散的算例进行了整理,并对其中一些算例的最优解进行了分析与证明,便于后
续工作和相关工作的开展和比较。
最后讨论了多任务调度问题的一种应用,即网格环境下的工作流调度问题。
关键词:分布式环境; 调度算法; 有向无回路图; 任务复制; 任务分簇
II
知识水坝为您整理
Abstract
The thesis is for multitasks static scheduling problem in distributed environments.
Efficient algorithms for it will have both highly theoretical and highly practical value. It is
strong plete, which is the hardest among the NP-difficult problems. It has been
deeply studied by worldwide researchers for decades. And many schedule models and
algorithms were proposed for it.
Directed acyclic gr