The Study Of Grid Task Scheduling Algorithm Based On Cost-Time Constraint

Grid is a developing direction of distributed and parallel processing technology. The goal of grid is to realize share of heterogeneous resources that locate all over the world, and resource management is the core technology and soul of Grid. Because the Grid resource is distributed geographically, heterogeneous inherently, autonomous, dynamic and so on, resource management in the Grid environment is a very complex and challenging work whose efficiency is related to the performance of the whole system directly. Moreover, in order to attract resource consumers to attend the Grid, their needs must be met. Therefore many traditional resource management and scheduling strategies are not exactly suit for the Grid.Based on the research of the advantage and disadvantage of the resource management techniques in using now in the Grid, This article import economic principles to Grid Computing, apply price mechanism to Grid Computing and focus on the task scheduling under the limit of job completion time and the cost of the tasks. Aim to independent and parallel tasks, this article present a task scheduling model and transform Grid task scheduling to tree traversal problem. Due to the reason that when the question scale becomes very large, the tree traversal problem becomes NP-Hard, this article propose a model use pruning strategy and transform the user's time and cost constraint to pruning function .By use of pruning technique, this algorithm dispose the scheduling which doesn't suit the user's demand, and reduce the question scale to a great degree, which make the question solvable.This article gives an example to explain the algorithm clearly and optimize the algorithm, a simulative example based on the algorithm is also provided to analyze the characteristics of the algorithm. It turned out that the algorithm implement with pruning strategy is a feasible option which takes deadline and cost constraint and other factors into account. It can allocate application tasks to appropriate CPU resources based on the user's requirement of deadline and cost constraint, and it has the lowest space cost and a tolerable time cost, it also reduces the search path to a great degree. Our algorithm can finish the schedule in a short time when the scale of the question is not very big, even when the scale becomes very big our algorithm has great advantage over traditional algorithm. It is a feasible task scheduling algorithm.