Genetic Algorithm for Independent Job Scheduling in Grid Computing

Muhanad Tahrir Younis; Shengxiang Yang

doi:10.13164/mendel.2017.1.065

Muhanad Tahrir Younis
Shengxiang Yang

DOI: https://doi.org/10.13164/mendel.2017.1.065

Keywords: evolutionary algorithms, genetic algorithm, job scheduling, grid computing, makespan

Abstract

Grid computing refers to the infrastructure which connects geographically distributed computers owned
by various organizations allowing their resources, such as computational power and storage capabilities, to be
shared, selected, and aggregated. Job scheduling is the problem of mapping a set of jobs to a set of resources.
It is considered one of the main steps to e ciently utilise the maximum capabilities of grid computing systems.
The problem under question has been highlighted as an NP-complete problem and hence meta-heuristic methods
represent good candidates to address it. In this paper, a genetic algorithm with a new mutation procedure to
solve the problem of independent job scheduling in grid computing is presented. A known static benchmark for
the problem is used to evaluate the proposed method in terms of minimizing the makespan by carrying out a
number of experiments. The obtained results show that the proposed algorithm performs better than some known
algorithms taken from the literature.

References

Abraham, A., Buyya, R., Nath, B.: Natures heuristics for scheduling jobs on computational grids. In: The 8th IEEE international conference on advanced computing and communications (ADCOM 2000), pp. 45–52 (2000)

Braun, T.D., Siegel, H.J., Beck, N., B¨ol¨oni, L.L., Maheswaran, M., Reuther, A.I., Robertson, J.P., Theys, M.D., Yao, B., Hensgen, D., et al.: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed computing 61(6), 810–837 (2001)

Carretero, J., Xhafa, F., Abraham, A.: Genetic algorithm based schedulers for grid computing systems. International Journal of Innovative Computing, Information and Control 3(6), 1–19 (2007)

Foster, I., Kesselman, C.: The Grid 2: Blueprint for a new computing infrastructure. Elsevier (2003)

Foster, I., Kesselman, C.: The history of the grid. computing 20(21), 22 (2010)

Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the grid: Enabling scalable virtual organizations. International journal of high performance computing applications 15(3), 200–222 (2001)

Ibarra, O.H., Kim, C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. Journal of the ACM (JACM) 24(2), 280–289 (1977)

Izakian, H., Abraham, A., Snasel, V.: Performance comparison of six efficient pure heuristics for scheduling meta-tasks on heterogeneous distributed environments. Neural Network World 19(6), 695 (2009)

Kolodziej, J., Xhafa, F.: Enhancing the genetic-based scheduling in computational grids by a structured hierarchical population. Future Generation Computer Systems 27(8), 1035–1046 (2011)

Liu, H., Abraham, A., Hassanien, A.E.: Scheduling jobs on computational grids using a fuzzy particle swarm optimization algorithm. Future Generation Computer Systems 26(8), 1336–1343 (2010)

Maheswaran, M., Ali, S., Siegel, H.J., Hensgen, D., Freund, R.F.: Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. Journal of parallel and distributed computing 59(2), 107–131 (1999)

Nesmachnow, S., Alba, E., Cancela, H.: Scheduling in heterogeneous computing and grid environments using a parallel chc evolutionary algorithm. Computational Intelligence 28(2), 131–155 (2012)

Osaba, E., Carballedo, R., Diaz, F., Onieva, E., de la Iglesia, I., Perallos, A.: Crossover versus mutation: a comparative analysis of the evolutionary strategy of genetic algorithms applied to combinatorial optimization problems. The Scientific World Journal 2014 (2014)

Pacini, E., Mateos, C., Garino, C.G.: Distributed job scheduling based on swarm intelligence: A survey. Computers & Electrical Engineering 40(1), 252–269 (2014)

Selvi, S., Manimegalai, D.: Task scheduling using two-phase variable neighborhood search algorithm on heterogeneous computing and grid environments. Arabian Journal for Science & Engineering (Springer Science & Business Media BV) 40(3) (2015)

Selvi, S., Manimegalai, D., Suruliandi, A.: Efficient job scheduling on computational gridwith differential evolution algorithm. International Journal of Computer Theory and Engineering 3(2), 277 (2011)

Xhafa, F., Abraham, A.: Computational models and heuristic methods for grid scheduling problems. Future generation computer systems 26(4), 608–621 (2010)

Xhafa, F., Kolodziej, J., Barolli, L., Fundo, A.: A ga+ ts hybrid algorithm for independent batch scheduling in computational grids. In: Network-Based Information Systems (NBiS), 2011 14th International Conference on, pp. 229–235. IEEE (2011)

Younis, M.T., Yang, S., Passow, B.: Meta-heuristically seeded genetic algorithm for independent job scheduling in grid computing. In: European Conference on the Applications of Evolutionary Computation, pp. 177–189. Springer (2017)