Mutation based simulated annealing algorithm for minimizing Makespan in Grid Computing Systems

Computational grids have become attractive and promising platforms for solving large-scale high-performance applications of multi-institutional interest. However, the management of resources and computational tasks is a critical and complex undertaking as these resources and tasks are geographically distributed and are heterogeneous in nature. This paper presents a new stochastic approach for scheduling independent tasks in the grid environment by minimizing Makespan. The novel algorithm, Mutation Based Simulated Annealing Algorithm (MSA), speeds up convergence better than the previous algorithms by using the selection of Simulated Annealing, single change Mutation and a new Random Minimum Completion Time (Random-MCT) heuristic. In order to make the algorithm MSA working fast, it maintains two solutions at a time. The experiments on the algorithm MSA provide a reduction in Makespan equals to eighteen (18) when it is compared with algorithm Min-Min, and equals to three (3) when it is compared with previous genetic algorithm. The simulation results display that the assumed algorithm has better performance than previous genetic algorithm and Min-Min algorithm in terms of quality of solution and Load Balancing, as well as Resource Utilization. However, in this work the gain in average time consumed by algorithm is about 93%, which makes MSA algorithm very high QoS and more preferable for realistic scheduling in Grid environment.