动态自由节点滞后的任务调度算法

任务调度是异构计算系统的核心问题之一。调度问题是一个NP完全问题,为获得次优解,出现了很多启发式的算法。分析表调度的典型算法,发现存在一些不足,提出一种新的方法——动态自由节点滞后调度算法,采用动态判断自由节点并对它们滞后调度,让对任务图调度长度影响更大的节点被优先调度,从而缩短调度长度,分析和实验结果表明该算法要优于ETF,MCP和BDCP算法。

Task Scheduling Algorithm of Dynamic Unrestricted Node Lag

Task scheduling is an integral part of parallel and distributed computing and one of the important problems in Heterogeneous Computing System(HCS).The tasks scheduling problem is an NP-hard in general.In order to obtain better solutions,many scheduling heuristics are presented in the literature.This paper analyzes the typical algorithms of list scheduling,and there are some disadvantages of them.It proposes a new algorithm,Dynamic Unrestricted Node Lag(DUNL) that can generate an optimal scheduling.The algor...