Abstract

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.

Keywords

MSC

68T20

Cite this article

@article{cai-18174,
  author  = {Fatos Xhafa and Javier Carretero and Bernabé Dorronsoro and Enrique Alba},
  title   = {A Tabu Search Algorithm for Scheduling Independent Jobs in Computational Grids},
  journal = {Computing and Informatics},
  volume  = {28},
  number  = {2},
  pages   = {237--250},
  year    = {2009},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2009/2/a-tabu-search-algorithm-for-scheduling-independent-jobs-in-computational-grids/}
}
Download .bib