一种求解异构DAG调度问题的置换蚁群

减少分布式程序的执行时间，是网格调度系统需要解决的重要问题。因分布式程序常建模为DAG图，故该问题又称异构DAG调度问题。提出的置换调度蚁群PSACS(Permutation Scheduling Ant Colony System)将DAG调度方案表示为任务置换列表，使用标准蚁群搜索技术探索解空间。实验表明，该算法明显优于遗传算法和粒子群算法，能够一次求出大部分(65%)同构DAG调度问题的最优解并获得非常好的异构DAG调度方案。

Permutation Ant Colony System for Heterogeneous DAG Scheduling Problem

Reducing execution time of distributed program is a major issue of Grid Scheduling System Because scheduled programs are modeled by DAG, this problem is also called Heterogeneous DAG scheduling problem. Permutation Schedining Ant Colony System(PSACS) proposed by this paper presents solution of this problem as task permutation list and utilizes standard ACO searching technique to explore solution space. Experimental result indicates that PSACS outperforms GA and PSO substantially. It can get global optima for the majority(65%)of homogeneous DAG scheduling problems and pretty good solutions for heterogeneous DAG scheduling problems.