Computational Grid Task Scheduling Algorithms Based On Multiple QoS Constraints

The multiple QoS constraints based task scheduling problem in the computational grid environment is a hot topic in the research field of grid task scheduling algorithm. Problems such as conquering the heterogeneity of the resource, coordinating the distribution of the management policy and effectively cooperating with multiple QoS constraints are still difficult to solve. There is an extensive foreground for the research on it.This paper studies the QoS model in the grid environment. Based on the taxonomy for the QoS specifications, utility functions modeling the QoS specifications have been brought in so as to provide optimizing target to the scheduling algorithm. Based on these work, two heuristic scheduling algorithms, QB-Min-min and QB-Sufferage are proposed through improving on traditional scheduling algorithms in the heterogeneous environment such as Min-min and Sufferage, with the weighted QoS utility sum as the optimizing target. Though these algorithms are simple and efficiency, they have some certain shortage.Since the multiple QoS constraints based grid task scheduling problem is in fact a multiobjective combinational optimization problem, solving this problem with a multiobjective combinational optimization method may achieve good results. With the multiobjective genetic algorithm NSGA-II and the special character of the grid task scheduling problem, the scheduling algorithms based on multiobjective combinational optimization method are realized through designing the coding of the chromosome, the generating method of the initializing population and the genetic operator such as selection, crossover and mutation.The experimental results show that the scheduling algorithm based on multiobjective combinational optimization method is better than those heuristic scheduling algorithms. This indicates that it is feasible and reasonable to apply multiobjective method to the multiple QoS constraints based grid task scheduling problem. Besides, the experimental results also show that the scheduling algorithms taking the QoS specification into account is better than those not do. This indicates that it is essential to take the QoS specification into account and employ a QoS based scheduling problem in the grid environment.