异构系统中基于可用性的粒子群任务调度算法

摘要

Task scheduling techniques, playing an important role to system performance, are one of the key technology in parallel and distributed systems. In general, the task scheduling problem in large-scale systems is a NP problem. The modern heuristic biological evolution algorithm is an effective method to find an approximate solution for NP problems. In this paper, a scheduling algorithm which applys particle swarm algorithms into availability grid dispatch systems is proposed. The performance of the algorithm is analysed in theory. The simulation results show that compared with the SSAC algorithm which is recently proposed, the proposed particle swarm optimization task scheduling algorithm can generate shorter makespan while conserving the same availability level.%任务调度技术是并行分布式系统中的关键技术之一,对系统的性能起着重要作用,但通常情况下大型系统的任务调度问题属于NP问题.而现代启发式生物进化算法是找出很多NP问题近似解的有效方法.本文将粒子群算法应用于基于可用性的网格系统调度中,提出了一种调度算法,对算法的性能进行了理论分析和模拟实验.结果表明:和最近文献中的基于可用性的调度算法SSAC相比,所提出的新算法在保证系统资源具有同样的可用性条件下,能够产生更好的调度长度.