树型网格下独立任务的实用调度算法

摘要

讨论了节点计算能力和网络通信速度异构的树型网格下独立任务的调度问题.与最小化任务总执行时间不同,文中提出了树型网格平台任务调度问题的一种修正的整数线性规划模型,为解决多层树通过线性规划模型求解最优任务分配数时时间复杂性大的问题,引入推拉方法,将多层树线性规划求解归结为单层树求解,使得求解过程的复杂性大大降低.基于求出的近似最优任务分配数,提出一个静态分布式的启发式任务调度算法.分析和实验表明,在异构的树型网格下进行大量的独立任务调度时,算法性能优于同类算法.