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

Available online: 16 Jun 2013 *

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