以工作站机群为代表的并行计算模式无疑是并行分布式计算的重点研究领域,同时,随着网络互联技术的发展,并行计算环境也从局域网范畴向广域网范畴拓展,在机群计算的基础上出现了新的基于因特网的并行分布式计算模式即网格计算。而无论在机群计算还是网格计算的实现中,如何对并行作业的任务进行调度是影响整个系统成败和性能的关键因素,因而研究多处理器或多计算机的任务调度算法对于机群计算和网格计算都具有十分重要的理论和实际意义。随着并行处理和并行计算概念的出现,对并行作业任务调度问题的研究就由来已久。前人的研究已经证明,即使在简化模型的情形下,绝大多数的并行作业任务调度问题也是NP完全问题,所以在计算复杂度可以接受的前提下获取并行作业任务调度问题最优解的努力无疑是不现实的。而启发式算法由于在更接近实际情况下具有算法实现容易、性能较好以及时间复杂度较低的优点被普遍采用,在研究相应的已有任务调度算法的基础上,针对静态编译时调度、动态运行时调度和实时调度的不同要求提出了一系列并行作业任务调度的启发式算法。在涉及到的所有启发式调度算法都采用DAG(Directed Acyclic Graph)模型来描述并行作业的状况,因为DAG模型更能真实地反映并行作业的实际情况。同时所有算法都考虑了处理器异构的因素。在研究和分析两个异构环境下典型的静态调度算法HEFT和CPOP的基础上提出了基于层次和分支优先性的调度算法LBP。目前绝大多数静态启发式调度算法是关键路径的表调度算法,算法HEFT和CPOP亦不例外,但是在异构计算环境下关键路径已失去表达最迫切需要调度任务的意义,算法LBP摒弃了传统的以关键路径作为优先性首要考虑的思想,而以任务的层次性和分支数来考虑任务的优先性,理论证明和试验分析说明,在异构计算环境中算法LBP和算法HEFT、CPOP具有相同的时间复杂度,但算法LBP比上述两算法的调度性能相比较有较大的改进。除此之外,算法LBP本身具有天然较好的并行性。并行作业任务调度算法的并行化研究并不是很多,因为调度算法本身固有的串行性。尽管静态启发式调度算法的时间复杂度较低,但在任务规模过大的情况下算法所花费的时间也可能很可观。根据串行算法LBP各步骤中数据和操作的相关性,提出了算法LBP的并行算法PLBP,理论证明算法PLBP与LBP具有相同的调度性能,与文献中已有的并行化调度算法HPMCP及PBSA相比,算法PLBP的时间复杂度更低。静态调度算法受限于DAG中各参数必须在调度之前完全获取的前提条件,而在实际科学计算中这一前提并不能得到满足,DAG中任务参数一般是在其父任务执行完成时才能实例化,即DAG中各任务是边调度边执行的。在分析已有几种典型的动态调度算法基础上,采用DAG的参数化模型PTG(Parameterized Task Graph),并对建立在PTG模型上的动态调度算法PTGDS进行研究,在任务调度的同步性和调度策略等方面对其进行改善,并把静态调度算法LBP的思想融入其中,提出了改进的并行作业动态调度算法IPTGDS。并在理论上分析算法IPTGDS是可行的,同时试验结果说明算法IPTGDS与PTGDS相比调度性能更优。把研究的基于DAG的静态调度算法和动态调度算法的成果引入到实时系统中,建立了异构环境下的动态实时调度模型,在此模型上提出了动态最早完成优先算法DEFF;同时,对实时环境下的动态调度经典算法――近视算法进行分析,借鉴近视算法中的回溯思想,提出了基于有限回溯的动态调度算法BBDS,算法BBDS与近视算法的不同在于:近视算法针对元任务集而算法BBDS是针对DAG任务集;算法BBDS比近视算法对回溯的控制更严格和精确;算法BBDS采用的评估函数比近视算法有改进。为了适应实时系统单机失效容错的要求,在算法BBDS的基础上设计了容错版本FTBBDS。理论证明算法BBDS和FTBBDS的时间复杂度均较低,即O(nm3);并在仿真试验的条件下,对几种主要参数影响算法DEFF、BBDS和FTBBDS调度成功率的变化情况进行了比较。