随着科学技术的不断发展,包含多个具有依赖关系的子任务的复杂应用逐渐增多,这类应用被称为工作流,其执行往往具有大量的计算需求。为了迎合这种需求,异构分布式计算系统的使用变得普遍起来,例如集群,网格、云等。工作流调度的主要过程就是将众多的任务合理地分配到多个计算资源上,这一过程对于提升应用在计算平台上的执行性能至关重要。近年来工作流调度问题的研究,特别是在异构计算环境中的研究,吸引了越来越多的关注。此类调度研究常采用有向无环图(Directed Acyclic Graph,DAG)表示工作流应用本身,因此亦称为DAG调度。现有的大部分的DAG调度算法都假设任务的执行时间和通讯时间是已知的、确定的,然而现实环境中工作流的执行过程非常复杂,不大可能获得对计算时间和通讯时间的精确预测,因此我们考虑将其假设为随机变量,并假定该随机变量的均值和方差是可被预测的。这种以随机方式建模的DAG调度算法被称为随机调度算法。在本文中,我们着重研究当工作流子任务的执行时间和通讯时间满足某种随机分布时,如何调度到多个互联的异构计算资源上来获得较好的总体执行性能。在异构计算平台上将确定性调度算法改为相应的随机调度算法一种很自然的做法就是将随机分布的期望作为权值的估计值,然后按照确定性调度算法生成的方案进行调度。因此,本文首先考虑经典的确定性调度算法HEFT,针对在HEFT中仅使用期望作为估计值是否为一个好的方案这一问题进行了探究,实验证明这种做法还有很大的提升空间。随后,我们尝试对确定的DAG调度算法HEFT进行扩展以获得更好的性能,本文中的随机调度算法RHEFT由此产生。在RHEFT中我们将随机策略引入到HEFT算法的第二个阶段:依次遍历处理器,哪台能使估计最早估计完成时间最小化便将任务分派到上面。这种随机策略充分考虑到了随机模型的不确定性,相比调度时依靠对时间的静态预测方法更贴合实际。我们通过大量的实验来比较RHEFT和HEFT的调度结果。结果显示,RHEFT不仅显著减少了总的调度时间(makespan),而且具有良好的扩展性。此外,我们将RHEFT算法进一步扩展,将随机策略引入到了第一阶段优先级的比较中去,ERHEFT算法由此产生。实验显示,ERHEFT相较于RHEFT在性能上有了进一步的提升。