并行计算,是提高计算机性能的一种有效途径,已成为一种极具吸引力的计算模式,在工业、商业、科技和军事等领域有着非常广泛的用途,并且已经有了很多实际的应用。任务调度是影响并行计算性能或效率的关键因素之一,任务的不恰当调度不仅会使系统真正的潜在计算能力不能被开发出来,还可能会降低并行系统的效率。因此,调度问题作为并行系统的核心内容之一,一直是人们研究的热点问题。基于Fork-Join任务图的调度问题是并行计算中调度的基础性问题,解决好Fork-Join任务图的调度问题,对于实现并行语言的编译器、提高并行计算的性能具有很重要的作用。基于Fork-Join任务图的调度算法的研究对于并行系统的普及推广将会产生重要的影响。针对已有的Fork-Join任务图的调度算法在使用处理机个数较多的情况下效率较低等问题,提出了基于任务复制和处理机负载平衡的贪心调度算法-TDGS_FJ算法。该算法采用一种处理机选择上的贪心策略,通过分析已用处理机的负载和空闲时间段,在确保最短调度长度的同时,尽量将任务分配至已用的处理机上以平衡负载并试图最小化使用的处理机数目。实验结果表明,该算法在总体效率上优于TDS、TSA_FJ等经典算法。针对Join任务图提出了TDGS_J1算法和TDGS_J2算法,它们均可以应用至Join任务图并产生最短调度长度,实例表明在主要性能指标方面,它们优于相比较的算法。针对已有的Fork-Join任务图的调度算法未考虑通信竞争的问题,提出一个基于通信竞争的调度算法-CCGS_FJ算法,该算法取消所有处理机之间的通信均能同步进行的约束,通过对通信边的串行化集成通信竞争,进而提高调度性能。实验结果表明,CCGS_FJ算法具有较短的调度长度、使用的处理机较少,而且任务图中的结点数越大,该算法的主要性能越显著优于其它算法,该算法可以作为在通信成为性能瓶颈的场合中基于通信竞争的有效调度策略,具有较强的实用性。针对Join任务图分别提出两个基于通信竞争的算法-CCGS_J1算法及CCGS_J2算法,分析表明了它们的有效性。目前已有的Fork-Join任务图的调度算法大多假定处理机为同构的,而没有考虑实际应用中处理机的异构性以及节省处理机的问题,导致算法在具体应用中效率较低。借鉴基于同构环境的调度算法的有效策略,提出一个针对Fork-Join任务图的异构环境的贪心调度算法-HTGS_FJ算法。该算法利用关键任务进行调度并在确保调度长度较短的前提下,尽量将当前任务调度至已使用过的较快的处理机以节省处理机。实验结果表明,该算法具有调度长度较短、使用的处理机数较少的特点,因而调度效率较高,在异构系统中具有较强的实用性。针对Join任务图,提出了两个基于异构系统的算法-HTGS_J1算法和HTGS_J2算法,分析表明了它们的有效性。对于任意结构的任务图,应用集群和任务复制技术,提出两个新的算法-SCTDS₁算法和SCTDS₂算法。SCTDS₁算法采取将各join任务与其贵宾前驱所在的簇合并的策略,使join任务在其最早开始时间开始执行。该聚簇方案使各簇被调度至相应的处理机后,各任务在被调度至的处理机中均能保证在其最早开始时间开始执行,从而确保调度长度最短。SCTDS₂算法采用的聚簇策略,既有选择地合并join任务的贵宾前驱以外的其它父任务,同时又有选择地复制它们所在簇中的祖先任务,尽可能地减少任务之间的通信开销,因而能产生比其它算法更短的调度长度。SCTDS₁算法及SCTDS₂算法的最优条件较TDS和extended TDS等算法简单而易于满足,同时具有较小的时间复杂度。实验结果表明,它们的性能较优于相比较的算法。在简单的条件下,SCTDS₁算法及SCTDS₂算法应用于Fork-Join任务图,得到满意的调度效果。