随着计算机应用范围的日益扩大,分布式异构系统(DHS,Distributed Heterogeneous System)逐渐成为解决复杂应用问题的有效工具。DHS利用一组异构的计算机来协作完成应用任务,以期获得最好的执行效果。DHS中的任务调度问题,对发挥系统的并行性能和保持负载平衡具有非常重要的意义。该问题已被证明是NP完全问题,无法在多项式时间内找到最优解,所以促使人们不懈地研究如何设计调度算法,用有限的代价获得更好的解。目前常用的方法就是启发式算法和随机搜索的近似方法。 在本文中研究了主从式DHS中的调度算法问题,对其进行数学建模,定义并分析了主从式DHS在稳定运行阶段的系统特性。对于树形的主从结构,本文给出了达到稳定运行阶段的集中带宽(bandwidth-centric)调度策略,并证明了稳定运行阶段的最优性。 在本文中我们提出了两种主从式DHS下的任务调度算法。首先给出了启发式算法IMM(Improved min-min),该算法可以解决DHS环境下,独立的、带优先权和时限的任务的调度问题。随后根据主从式DHS稳定运行阶段的特点,提出了一种集中带宽的渐进最优算法,并从理论上证明该算法在评估时间段T趋向于无穷大时,可以取得最优解。 另外,我们还对文中提出的两种算法分别进行了仿真实验,其仿真结果证明了我们算法的优越性。