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.
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: 16 Jun 2013 *