异构分布式系统中计算应用的调度长度最优化问题备受关注。囿于通信网络的带宽及传输速度等限制,通信开销对调度长度的影响不容忽视,通过减少通信开销优化调度长度是研究的焦点之一。为尽量减少通信开销,基于任务复制的各类调度算法应运而生,其可以通过额外的计算开销来减少通信开销,并取得了极好的效果。然而,任务复制的引入会使调度问题更加难以求解,如何在使用任务复制提供高质量调度方案的同时,减少求解时间是当前面临的一大挑战。针对上述挑战,本文将调度问题进行分解,按序求解分配子问题与排序子问题,并分别进行优化以提高求解效率。提出了一种两阶段的高效调度算法,能够给出允许任务复制下调度长度最短的方案。本文的主要贡献如下:1.分析并定义了基于任务复制的异构分布式系统调度长度最优化问题对任务复制所带来的解空间膨胀、链式反应及复制异常现象等调度算法设计难点进行了分析。并根据异构分布式系统及任务复制的特征进行系统及任务建模,形式化定义了基于任务复制的异构分布式系统调度长度最优化问题。2.设计了一种基于分支定界搜索的任务分配算法为避免链式反应,基于分支定界搜索设计了分配阶段算法,以调度长度上界为优化目标搜索任务的最优分配方案。基于拓扑序设计分支操作以避免搜索重复状态,并减少操作计算量,再在过程中根据已有目标值裁剪状态空间,提高算法的求解效率。3.设计了一种基于松弛区间的动态优先级任务排序算法根据任务的优先关系约束及分配方案,设计基于松弛区间的动态优先级对任务进行排序,以得到最终调度方案。为解决复制异常现象,该算法在任务排序过程中使各任务可以从任意处理单元上的前驱获得输入数据,进一步优化调度长度。4.开发了基于任务复制的异构分布式系统调度工具该工具提供友好的人机交互界面,实现了本文所建立模型及本文所提出调度算法。能够针对不同的系统配置及任务配置,给出基于任务复制的调度长度最优化调度方案。本文针对不同的系统配置与任务配置设计了分析实验,验证了本文所提出算法在不同情景下的有效性。并且在特定的系统配置下对比了先进的启发式调度算法与优化搜索调度算法,实验结果表明,本文所提出算法能够给出质量更高的调度方案,且求解时间较单阶段优化搜索调度算法显著减少。