An Improved Ant Colony Algorithm For Task Scheduling In Grid

Grid computing environment has increasingly grown a very cheapsupercomputing environment beyond area limit.It gathers computation resources,storage resource, knowledge resource, communication resource, and informationresource etc．together from all over the world,aims at serving pubfie and realizingresources sharing and cooperative working. However, due to the heterogeneousdynamic, autonomous, and distribution and other characteristics in grid resources,task scheduling in grid environment is a challenging problem. Task schedulingalgorithm for Grid scheduling is directly related to the speed, quality and etc. It playsan important role in the grid study.Since bionics was created in middle period of1950’s, people have being inspiredfrom the mechanism of the biological evolution constantly. Many new methods hadbeen applied to solve the complicated optimization problems are proposed. Such asneural network, genetic algorithm, simulated annealing, and evolution computation.These new methods had been successfully applied to solve the practice problems.Many scholars research the task scheduling algorithm for the grid technology, and hasachieves good results in recent years. But they don’t take parameter optimization intoaccount and value inspiring information parameter α,the expectations factor β, thepheromone strength Q and the information volatile factor ρ according to the previousexperiment. In fact, the convergence performance and computational efficiency of antcolony are sensitive to it. An ant system based exploration-exploitation forreinforcement learning. During the four parameters, α reflects the impact of thepheromone by the other ants left behind after a grid resource nodes to the ants. Thegreater the value, it is more possible for the ant to choose the same resources of theother ants. The parameter β reflects the inherent properties of ants by the impact ofresource level. The greater the two parameters, it is more easy for ant colonyalgorithm to fall into local optimum. The parameter Q can enhance the positivefeedback, so that the search direction that is conducive to the direction of finding theoptimal solution. The parameter ρ to avoid unlimited accumulation of pheromone,thereby expanding the search scope to improve the solution efficiency. This paperpresents an improved ant colony algorithm NACA (new ant colony algorithm). Firstly,we make the four parameters of the ant colony algorithm coding randomly and get the chromosomes, a set of optimum solutions could be gained by using the Ant ColonyAlgorithm. Then they crossover、mutate and select by using the advantages of geneticalgorithms. Finally, take the value of this group to explore the next round as the antcolony’s original value, runs the maximum number of loop iterations until it stops.NACA make full use of fast global search randomly of genetic algorithm and exploresoptimization of four parameters α、β、ρ、Q, The performance of the system has beensignificantly improved whne it was applied to the grid task scheduling systems.An extensive simulation study in GridSim simulation platform was conducted toevaluate and compare the performance of the algorithms in the later chapters of thispaper. The obtained results show that the algorithm has optimal performance andadapte widely. GridSim using grid simulator of the proposed algorithm simulationresults show that the proposed scheduling algorithm has a shorter length and wideradaptability.when the task is known, execution time could be reduced about21.7%.The execution time of the task is shorten greatly. It impact less to the processorresources when the load on the grid changes. However, when the task is unknown andthe system is large, the algorithm need further improved.