| 【论文摘要】 |
将异构任务调度到异构资源上的问题,即任务分配问题,一般是NP问题。存在许多任务调度问题的具体实例的启发式算法,但多数情况下效率都不高。Holland提出的遗传算法应用进化策略实现了对调度空间的更快搜索,能够更快更好的找到优质的解。该算法在许多领域都得到了应用。许多研究者探索了遗传算法在同构和异构多处理机上对任务调度的应用,并取得了许多成绩。
但是,他们都多情况作了各种假设,降低了解决方案的通用性,如调度必须事先离线做出并且不能改变,所有的通信时间事先知道,所有的处理机具有相同的处理能力,处理机专门用来处理来自调度器分配来的任务等。这些假设限制了这些调度策略在分布式系统中的通用性。网格具有动态性和异构性,所以这些策略不适合网格中的应用。
本文提出了一种遗传算法的改进算法—动态遗传算法DGA(Dynamic Genetic Algorithm),根据网格系统各服务节点的计算能力、负载及网络状态进行动态调度,从而向用户提供最优性能,不仅使总的完成时间最短,还尽量考虑到使主机的空闲时间最短,同时要满足每个任务的deadline的要求。动态遗传算法主要是在基本遗传算法的基础上,针对网格任务调度... |
