Abstract: 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.

Key words: Grid, DAG scheduling, Ant colony optimization