A New Scheduling Algorithm in Grid Based on Dynamic Decisive Path

Grid environment is an open, dynamic and changeful application environment, in which task scheduling is a hot topic of grid environment research in recent years. Task scheduling in grid environment is a NP problem. How to choose effective resource to run the tasks is an important problem. Although some iterative methods, such as GA, can solve it effectively. However it will spend too much time scheduling too many tasks. And some custom heuristic algorithms often cause the spare time slots in the resource. So in this paper a new heuristic algorithm is addressed based on the idea which is scheduling the tasks first, and then optimizing them. First it uses the common heuristic algorithm to schedule the tasks, and then a new DAG can be rebuilt and the decisive tasks and decisive path can be constructed. After that the decisive tasks will be rescheduled to the new resource which includes the fit spare time slots in order to advance the decisive task and its child tasks. Also adopted in this paper is a new method to judge the deadlock between tasks in the DAG so that the tasks could be completed normally. Simulation tests prove that the heuristic algorithm can tackle the NP problem in a simple and efficient way.