Design And Realization Of Task Scheduling Algorithm In Grid Environment

With the flourishing of grid computing in recent years, people have been trying to integrate the heterogeneous resources distributed around the world into a uniformly computing infrastructure. For a grid to efficiently support a variety of applications, effective scheduling of grid tasks is an important issue, and becomes one of the research focuses. Considering the dynamism, heterogeneity, uncertainty of grid nature as well as QoS demands, task scheduling in grid environment becomes more difficult than traditional parallel task scheduling.In this paper, firstly grid task scheduling based on DAG model is researched. Through emphasize analyzing Gentic Algorithm based scheduling algorithm and Task Duplication based scheduling algorithm, we find that the existent Gentic Algorithm based scheduling Algorithm can not make better use of task duplication to reduce the communication delays. Therefore we present a task duplication based Gentic scheduling algorithm (TDGA) . This algorithm adopts an encoding scheme combining direct encoding with indirect encoding, which can take advantage of task duplication. By use duplicate the tasks on Critical Path to gain an initial population, which can quicken convergent speed. And that, designing three mutation operators to increase the chromosome's variety and reducing the task duplication of no use with optimize process. Finally Through experiment proves the validity of algorithm.Moreover, we deeply study Deadline and Budget Constrained(DBC) Scheduling Policy and its three algorithms-Time Optimization,Cost Optimization and Cost-Time Optimization. Aim to the fact that thethree heuristic algorithms can optimize one target of the two QoS targets(Time and Cost) , we proposed Average Cost based DBC ClassifiedOptimization (AC_DBC) . It considers both the time and cost of taskscheduling. The result of simulation experiment shows the new AC DBCalgorithm has good performance on balance the time and cost of taskscheduling and effective extending former algorithms.