Grid Task Scheduling Algorithm With QoS Constraints

Grid is another great technological revolution after the Internet and Web. Task scheduling is one of key factors of system performance and service quality in grid computing environment and it has been proved to be a-NP-complete problem. Therefore, it attracted the attention of many scholars and turned to be a research hotspot.At present, many grid task scheduling algorithms assume the scheduled task is Meta-task, but many grid applications in areas such as bioinformatics and astronomy are required to consider the dependencies among tasks. In the grid computing environment, resources are heterogeneous and interconnected over the world, so the dependencies among tasks presented new challenges to the traditional scheduling algorithms. The main work of scheduling is to determine the execution order for the tasks of an application and assign the tasks to suitable resources. We can use Directed Acyclic Graphs to describe the dependencies among tasks.On the other hand, ant algorithm is a new kind of intelligent heuristic optimization algorithm to solve the NP problem effectively. It has the characteristics of strong positive feedback, stability and parallelism, and is easily combined to other methods. However, the initial pheromone of ant algorithm is lacked, so it solves slowly.In this paper, considering the users'QoS requirements (time and cost), we proposed two grid task scheduling algorithms:GCAA and GTAA. At first, GC (Greedy Cost-Time Distribution) algorithm or GT (Greedy Time-Cost Distribution) algorithm produced a solution which was transformed into the initial pheromone of ant algorithm. Then, ant colony algorithm converged on global-best solution. Simulation results show that:in the grid environment, the proposed scheduling algorithms perform better than other scheduling algorithms obviously in grid environment.