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.

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}{popsize}),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.