Title: Hybrid algorithms for independent batch scheduling in grids

Authors: Fatos Xhafa; Joanna Kolodziej; Leonard Barolli; Vladi Kolici; Rozeta Miho; Makoto Takizawa

Addresses: Technical University of Catalonia, C/Jordi Girona, 1-3, 08034 Barcelona, Spain ' Institute of Computer Science, Cracow University of Technology, ul. Warszawska 24, PL-31-155 Cracow, Poland ' Faculty of Information Engineering, Fukuoka Institute of Technology (FIT), 3-30-1 Wajiro-higashi, Higashi-ku, Fukuoka 811-0295, Japan ' Polytechnic University of Tirana, Mother Teresa Sq., 4, Tirana, Albania ' Polytechnic University of Tirana, Mother Teresa Sq., 4, Tirana, Albania ' Seikei University, 3-3-1 Kichijoji-kitamachi, Musashino-shi, Tokyo 180-8633, Japan

Abstract: Grid computing has emerged as a wide area distributed paradigm for solving large-scale problems in science, engineering, etc. and is known as the family of eScience grid-enabled applications. Computing planning of incoming jobs efficiently with available machines in the grid system is the main requirement for optimised system performance. One version of the problem is that of independent batch scheduling, in which jobs are assumed to be independent and are scheduled in batches aimed at minimising the makespan and flowtime. Given the hardness of the problem, heuristics are used to find high quality solutions for practical purposes of designing efficient grid schedulers. Recently, considerable efforts were spent in implementing and evaluating not only stand-alone heuristics and meta-heuristics, but also their hybridisation into even higher level algorithms. In this paper, we present a study on the performance of two popular algorithms for the problem, namely Genetic Algorithms (GAs) and Tabu Search (TS) and two hybridisations involving them, namely, the GA (TS) and GA-TS, which differ in the way the main control and cooperation among GA and TS are implemented. The hierarchic and simultaneous optimisation modes are considered for the bi-objective scheduling problem. Evaluation is done using different grid scenarios generated by a grid simulator. The computational results showed that the hybrid algorithm outperforms both the GA and TS for the makespan parameter, but not for the flowtime parameter.

Keywords: computational grids; metaheuristics; GAs; genetic algorithms; tabu search; hybridisation; makespan; flow time; hierarchic optimisation; simultaneous optimisation; grid computing; independent batch scheduling.

DOI: 10.1504/IJWGS.2012.048402

International Journal of Web and Grid Services, 2012 Vol.8 No.2, pp.134 - 152

Published online: 31 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article