随着网络技术的飞速发展,互联网上充斥着更多可以利用的廉价资源。利用此类资源的网格计算解决规模庞大、复杂问题具有重要的意义。网格资源具有规模庞大、分布异构和动态性等特点。实现高效的网格计算需要解决许多复杂的问题,任务调度问题就是其中的一个关键问题。网格资源动态性主要反应在资源能力衰减、增强以及新资源的加入和旧资源的退出。以往的很多调度算法主要关注调度方案制定,直接将任务加入到资源节点的待执行任务序列,忽略了方案制定时和方案执行时资源能力的变化。若在方案制定时的资源能力在方案执行时衰减(退出),使得高权限任务占有了低性能资源,造成任务执行时间增加,有可能增加整个应用的并行完成时间(Makespan);若在方案制定时的资源能力在方案执行时增强,任务执行时间减小,有可能减小整个应用的Makespan;当新资源加入时,由于已经为任务分配资源,所以不影响任务执行时间和整个应用的Makespan。为了减小资源能力衰减引起应用Makespan增加的程度,以及增加能力出众的新加入资源对作业Makespan的影响,本算法根据调度执行开始时间(BT)将任务调度分为调度方案制定(TSPF)和调度方案执行(TSPE)两个阶段,定义了网格环境下的调度执行最晚开始时间、调度执行开始时间和任务优先图(DAG)中边的权值,分析了任务图冻结消减和执行消减对任务图结构的影响以及方案制定和方案执行时间的资源能力变化对调度准确性的影响。基于关键路径的调度算法(CPA)认为,尽量提前任务优先图关键路径中每个任务的完成时间,就能缩短整个作业的Makespan,即关键路径上的任务具有更高的优先权。但是,与基于最早开始时间的调度算法(ETF)比较发现,最早开始时间同样影响着作业Makespan,且在一定条件下ETF算法优于CPA算法。当前大多数调度算法主要通过预防抢夺解决资源抢夺,即在任何情况下都不允许资源抢夺。本算法在关键路径算法的基础上,根据关键路径长度(CP)定义了任务优先权,并且考虑最早开始时间对作业Makespan的影响,允许未分配资源的任务抢夺已经被任务占有的资源。在此基础上定义了资源抢夺和调度最小图,分析了资源抢夺有可能出现的几种情况,以及对任务图和调度结果的影响,并且针对一种资源抢夺情况,提出了两个启发式原则用以决定是否允许资源抢夺。最后,提出了基于BT的允许资源抢夺的网格依赖任务调度算法(BTTS)。重点分析了网格模拟平台GridSim,并在此平台上实现ETF算法、CPA算法和BTTS算法,试验结果发现BTTS算法优于其它两种算法,且有效地降低了网格动态性对调度结果的影响。