Title: Multiobjective grid scheduling using a domain decomposition based parallel micro evolutionary algorithm

Authors: Sergio Nesmachnow; Santiago Iturriaga

Addresses: Centro de Calculo, Facultad de Ingenieria, Universidad de la Republica, Herrera y Reissig 565, Montevideo, Uruguay ' Centro de Calculo, Facultad de Ingenieria, Universidad de la Republica, Herrera y Reissig 565, Montevideo, Uruguay

Abstract: This work studies the problem of scheduling independent tasks in heterogeneous computing grid systems. A new bi-objective formulation of the scheduling problem is introduced, which aims at minimising the makespan and weighted response ratio objectives. A novel parallel micro evolutionary algorithm is developed in order to efficiently solve the problem. By using a domain decomposition approach, the proposed method allows to efficiently deal with the multiobjective optimisation version of the scheduling problem. The new decomposition-based parallel micro evolutionary algorithm is implemented over MALLBA, a general-purpose library for combinatorial optimisation. The experimental analysis performed on both well-known and new large problem instances that model medium-sized grid environments demonstrate that the new parallel micro evolutionary algorithm achieves a high problem-solving efficacy and shows very good scalability behaviour when facing high-dimensional instances.

Keywords: parallel evolutionary algorithms; grid scheduling; heterogeneous computing; grid computing; multiobjective optimisation.

DOI: 10.1504/IJGUC.2013.054487

International Journal of Grid and Utility Computing, 2013 Vol.4 No.1, pp.70 - 84

Received: 05 Jan 2012
Accepted: 05 Jan 2012

Published online: 18 Sep 2014 *

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