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

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 addre...

Full description

Saved in:
Bibliographic Details
Published in:International journal of parallel, emergent and distributed systems emergent and distributed systems, 2011-12, Vol.26 (6), p.493-517
Main Authors: Garg, Saurabh Kumar, Konugurthi, Pramod, Buyya, Rajkumar
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
commodity market
Cost engineering
Genetic algorithms
Integer programming
meta-scheduling
parallel application
resource allocation
Schedules
Scheduling
Studies
Utilities
utility grids
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1744-5760
1744-5779
DOI:10.1080/17445760.2010.530002