Font Size:  Small  Medium  Large

A Tabu Search Algorithm for Scheduling Independent Jobs in Computational Grids

Fatos Xhafa, Javier Carretero, Bernabé Dorronsoro, Enrique Alba


The efficient allocation of jobs to grid resources is indispensable for high performance grid-based applications, and it is a computationally hard problem even when there are no dependencies among jobs.

We present in this paper a new tabu search (TS) algorithm for the problem of batch job scheduling on computational grids. We define it as a bi-objective optimization problem, consisting of the minimization of the makespan and flowtime. Our TS is validated versus three other algorithms in the literature for a classical benchmark. We additionally consider some more realistic benchmarks with larger size instances in static and dynamic environments. We show that our TS clearly outperforms the compared algorithms.

Full Text: PDF