eCite Digital Repository

A linear programming-driven genetic algorithm for meta-scheduling on utility grids


Garg, SK and Konugurthi, P and Buyya, R, A linear programming-driven genetic algorithm for meta-scheduling on utility grids, International Journal of Parallel, Emergent and Distributed Systems, 26, (6) pp. 493-517. ISSN 1744-5760 (2011) [Refereed Article]

Copyright Statement

Copyright 2011 Taylor & Francis

DOI: doi:10.1080/17445760.2010.530002


In Grids, single user-based brokers focus on meeting individual user job's quality of service requirements such as minimising the cost and time without considering demands from other users. This results in contention for resources and suboptimal schedules. Meta-scheduling in Grids aims to address this scheduling problem, which is NP-hard due to its combinatorial nature. Thus, many heuristic-based solutions using genetic algorithm (GA) have been proposed, apart from traditional algorithms such as greedy and first come first serve. In this paper, we propose the need for a ‘meta-brokering system’ and present a Meta-Broker which schedules multiple jobs on utility Grids. First, we present the architecture of our Meta-Broker and discuss the requirements and functionalities of the Meta-Broker. We, then, propose a linear programming (LP)/integer programming model for scheduling user jobs to multiple resources. We also propose a novel algorithm LP-driven GA which combines the capabilities of LP and GA. The aim of this algorithm is to obtain the best meta-schedule that minimises the combined cost of all users in a coordinated manner. Simulation results show that in comparison to single user-based brokers such as Gridbus and GRUBER, our proposed integrated algorithm offers the best schedule having the minimum processing cost with negligible time overhead.

Item Details

Item Type:Refereed Article
Keywords:utility grids, scheduling, resource allocation, parallel application, commodity market, meta-scheduling
Research Division:Information and Computing Sciences
Research Group:Distributed computing and systems software
Research Field:Distributed systems and algorithms
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Garg, SK (Dr Saurabh Garg)
ID Code:93857
Year Published:2011
Deposited By:Information and Communication Technology
Deposited On:2014-08-19
Last Modified:2014-08-21

Repository Staff Only: item control page