eCite Digital Repository
A linear programming-driven genetic algorithm for meta-scheduling on utility grids
Citation
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
Abstract
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 |
Downloads: | 0 |
Repository Staff Only: item control page