The Research Of Heuristic Task Scheduling Algorithm For Grid Computing

Grid is the strategic infrastructure of intense computing and informationservices, which has become the key technique of the next generation ofinternet. There are many different kinds of grid; however, the grid schedulingsystem is the core system to make grid a reality. And the task schedulingmodel and its optimization algorithm of the grid scheduling system is thebasic and key problem need to be figure out.Since task scheduling problem is NP-complete, and thus academic put alot attention on heuristic task scheduling algorithm. This paper has thefollowing contribution on heuristic scheduling algorithm of grid:1. The concept, objective, architecture, application and significance ofgrid computing are presented; and then the task scheduling model isintroduced. And on the basis of above, the details of grid scheduling and thecurrent research situation are analyzed.2. An innovative algorithm is put forward which adopts a mode thatdiffers with traditional algorithms model—Tabu_MaxLoad: it is based on principles of the Tabu. To make only one resource available to each task,some task to be dispatched to some computing resource is prohibited. Theexperimental result shows that it gets shorter makespan than traditionalalgorithm such as Min-min, Max-min obviously.3. After analysis of Min-min, to avoid the defect of Min-min, a minimaldeviation based grid scheduling algorithm (Dev Min-min) is put forward. Adeviation matrix is constructed, and then the distribution of task is based onthe matrix. Dev_Min-min can only maintain a smaller span but also maintainan excellent load balance.4. Considering security and reliability of grid scheduling, the currenttrust-based grid scheduling algorithm is improved, results in a betterefficiency and stability.5. Under the basis isomorphism environment DAG task schedulingalgorithm, a task-duplication and time-cost optimization based DAG taskscheduling algorithm is put forward. By this way, the cost of communicationbetween tasks, user defined deadline and cost constraint is considered. Thealgorithm results in a better performance which lower the time span and cost.In the end, the conclusion is made and the problem encountered isanalyzed, and the future research is put forward.