中文摘要：

在分布式同构系统中调度相关任务以最小化完工时间的问题是并行任务静态调度中的一个重要问题,也是研究并行分布式异构系统中多任务调度问题的基础。本文利用任务复制以尽量减少调度长度为主要目标,提出了一个基于聚簇(clutering-based)的贪心关键前驱复制(Greedy Critical Predecessor Duplication,GCPD)算法。在借鉴基于优先级调度的CPFD算法的基础上,GCPD算法充分考虑了复制每个机器上可能减少开始时间的关键前驱节点,从而优化了任务复制的技术,进一步提高了调度的性能。测试了两组共一千多个算例,GCPD算法在每个算例上的调度长度均短于或等于典型的任务复制算法的调度长度。实验结果表明,GCPD算法在寻找最短调度长度(makespan)方面是一个相当有优势的算法。