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