Cost-Driven Scheduling of Grid Workflows Using Partial Critical Paths

Recently, utility Grids have emerged as a new model of service provisioning in heterogeneous distributed systems. In this model, users negotiate with service providers on their required Quality of Service and on the corresponding price to reach a Service Level Agreement. One of the most challenging...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2012-08, Vol.23 (8), p.1400-1414
Main Authors: Abrishami, S., Naghibzadeh, M., Epema, D. H. J.
Format: Article
Language:English
Subjects:
Communities
Complexity theory
economic Grids
Grid computing
QoS-based scheduling
Quality of service
Schedules
Scheduling
Scheduling algorithm
utility Grids
workflow scheduling
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:Recently, utility Grids have emerged as a new model of service provisioning in heterogeneous distributed systems. In this model, users negotiate with service providers on their required Quality of Service and on the corresponding price to reach a Service Level Agreement. One of the most challenging problems in utility Grids is workflow scheduling, i.e., the problem of satisfying the QoS of the users as well as minimizing the cost of workflow execution. In this paper, we propose a new QoS-based workflow scheduling algorithm based on a novel concept called Partial Critical Paths (PCP), that tries to minimize the cost of workflow execution while meeting a user-defined deadline. The PCP algorithm has two phases: in the deadline distribution phase it recursively assigns subdeadlines to the tasks on the partial critical paths ending at previously assigned tasks, and in the planning phase it assigns the cheapest service to each task while meeting its subdeadline. The simulation results show that the performance of the PCP algorithm is very promising.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2011.303