A Novel Algorithm Applied to Task Scheduling in Grid Computing

Abstract

In this paper a novel optimal scheduling model and its algorithm are developed for task scheduling problems. A novel annealing-inspired genetic algorithm is applied to solve the scheduling model. The effectiveness of the algorithm is shown for a number of test problems and performance comparisons with the genetic algorithm, simulated annealing are also discussed.

Keywords

Grid computings Task scheduling

1. Introduction

In this paper, a novel annealing-inspired genetic algorithm (NAGA) is combined with GA and SA to find efficient solution to the grid task scheduling problem [1].

2. The Structure and Description of NAGA

The solution process of NAGA as follows:

Step 1: Generate an initial population P(t), the size of the population popsize, the initial temperature T₀, k = 0;

Step 2: Select P(k) to generate the parent population F(k)

Step 3: Crossover F(k) to generate C(k);

Step 4: Mutate C(k) to generate M(k);

Step 5: Generate the next population P(k + 1) = F(k) ∪ M(k);

Step 6: When the termination condition is coincident, outputs the result; otherwise, $T_{k + 1} = T_{k} \times (1 - \frac{k}{p o p s i z e}), k = k + 1$ , go to step 2.

3. Experiments and Conclusion

The experiment result shows that the algorithm static performance curve, and the time span of the algorithm in a different evolution algorithm, also effectively reveals that the NAGA algorithm has good convergence speed and a reasonable choice mechanism ensures its good performance.

References

Taura

, “A heuristic algorithm for mapping communicating tasks on heterogeneous resources,” 9^th Heterogeneous Computing Workshop, May 2000, Cancun, Mexico, pp. 102–118.