基于混合粒子群算法的网格任务调度

Task Scheduling in Grid Environment Based on Hybrid PSO Algorithm

减少分布式程序的执行时间是网格调度系统需要解决的重要问题。因分布式程序常建模为DAG图,故该问题又称异构DAG调度问题。在研究网格环境下的任务调度的基础上,提出了一种用于解决DAG任务调度问题的通用混合粒子群优化算法(Common Hybrid Particle Swarm Optimization),简称为CHPSO。该算法将问题的解(粒子)表示为任务的调度优先权向量,采用混合粒子群优化算法探索解空间。实验结果表明,在求解不含孤立点的单个DAG调度问题时,该算法所得解的调度长度仅为HEFT的90%～92%,求解质量与PSGA相当;在多张DAG图(含孤立节点)并发执行的网格环境中,该算法的调度性能明显优于PSGA及文中列出的其它演化计算方法。

Reducing execution time of distributed program is a major issue of grid scheduling system.Because scheduled programs are modeled by DAG,this problem is called Heterogeneous DAG scheduling problem also.Based on the research of task scheduling in grid environment,an algorithm named common hybrid particle swarm optimization（CHPSO） was proposed to solve the DAG scheduling problem.The algorithm presents the solution of the problem（particles） as a priority vector of the scheduling task and utilizes the hybrid PSO algorithm to explore solution space.Experimental result indicates that,in pure DAG scheduling which has no isolate task node,the CHPSO can get a scheduling length only 90%~92% of HEFT algorithm and as good as PSGA,but in grid environment where multi DAG graphs are concurrently executed,this algorithm performs obviously better than PSGA and other evolutionary computation listed in this paper.