Multiobjective grid scheduling using a domain decomposition based parallel micro evolutionary algorithm. (1st January 2013)

• Record Type: Journal Article
• Authors: Nesmachnow, Sergio; Iturriaga, Santiago
• Is Part Of: International journal of grid and utility computing. Volume 4:Number 1(2013)
• Page Start: 70
• Page End: 84
• Publication Date: 2013-01-01
• Subjects: parallel evolutionary algorithms -- scheduling -- heterogeneous computing -- grid; Electronic data processing -- Distributed processing -- Periodicals; Electronic commerce -- Management -- Computer programs -- Periodicals; 004.605
• Languages: English
• ISSNs: 1741-847X

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.