Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds

S. Abrishami, M. Naghibzadeh, D.H.J. Epema

Research output: Contribution to journalArticleAcademicpeer-review

325 Citations (Scopus)
1 Downloads (Pure)

Abstract

The advent of Cloud computing as a new model of service provisioning in distributed systems encourages researchers to investigate its benefits and drawbacks on executing scientific applications such as workflows. One of the most challenging problems in Clouds is workflow scheduling, i.e., the problem of satisfying the QoS requirements of the user as well as minimizing the cost of workflow execution. We have previously designed and analyzed a two-phase scheduling algorithm for utility Grids, called Partial Critical Paths (PCP), which aims to minimize the cost of workflow execution while meeting a user-defined deadline. However, we believe Clouds are different from utility Grids in three ways: on-demand resource provisioning, homogeneous networks, and the pay-as-you-go pricing model. In this paper, we adapt the PCP algorithm for the Cloud environment and propose two workflow scheduling algorithms: a one-phase algorithm which is called IaaS Cloud Partial Critical Paths (IC-PCP), and a two-phase algorithm which is called IaaS Cloud Partial Critical Paths with Deadline Distribution (IC-PCPD2). Both algorithms have a polynomial time complexity which make them suitable options for scheduling large workflows. The simulation results show that both algorithms have a promising performance, with IC-PCP performing better than IC-PCPD2 in most cases. Keywords: Cloud computing; IaaS Clouds; Grid computing; Workflow scheduling; QoS-based scheduling
Original languageEnglish
Pages (from-to)158-169
JournalFuture Generation Computer Systems
Volume29
Issue number1
DOIs
Publication statusPublished - 2013

Fingerprint

Scheduling algorithms
Scheduling
Cloud computing
Quality of service
Costs
Grid computing
Polynomials

Cite this

Abrishami, S. ; Naghibzadeh, M. ; Epema, D.H.J. / Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds. In: Future Generation Computer Systems. 2013 ; Vol. 29, No. 1. pp. 158-169.
@article{23a428650dc54ce3bcb00207296fe226,
title = "Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds",
abstract = "The advent of Cloud computing as a new model of service provisioning in distributed systems encourages researchers to investigate its benefits and drawbacks on executing scientific applications such as workflows. One of the most challenging problems in Clouds is workflow scheduling, i.e., the problem of satisfying the QoS requirements of the user as well as minimizing the cost of workflow execution. We have previously designed and analyzed a two-phase scheduling algorithm for utility Grids, called Partial Critical Paths (PCP), which aims to minimize the cost of workflow execution while meeting a user-defined deadline. However, we believe Clouds are different from utility Grids in three ways: on-demand resource provisioning, homogeneous networks, and the pay-as-you-go pricing model. In this paper, we adapt the PCP algorithm for the Cloud environment and propose two workflow scheduling algorithms: a one-phase algorithm which is called IaaS Cloud Partial Critical Paths (IC-PCP), and a two-phase algorithm which is called IaaS Cloud Partial Critical Paths with Deadline Distribution (IC-PCPD2). Both algorithms have a polynomial time complexity which make them suitable options for scheduling large workflows. The simulation results show that both algorithms have a promising performance, with IC-PCP performing better than IC-PCPD2 in most cases. Keywords: Cloud computing; IaaS Clouds; Grid computing; Workflow scheduling; QoS-based scheduling",
author = "S. Abrishami and M. Naghibzadeh and D.H.J. Epema",
year = "2013",
doi = "10.1016/j.future.2012.05.004",
language = "English",
volume = "29",
pages = "158--169",
journal = "Future Generation Computer Systems",
issn = "0167-739X",
publisher = "Elsevier",
number = "1",

}

Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds. / Abrishami, S.; Naghibzadeh, M.; Epema, D.H.J.

In: Future Generation Computer Systems, Vol. 29, No. 1, 2013, p. 158-169.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds

AU - Abrishami, S.

AU - Naghibzadeh, M.

AU - Epema, D.H.J.

PY - 2013

Y1 - 2013

N2 - The advent of Cloud computing as a new model of service provisioning in distributed systems encourages researchers to investigate its benefits and drawbacks on executing scientific applications such as workflows. One of the most challenging problems in Clouds is workflow scheduling, i.e., the problem of satisfying the QoS requirements of the user as well as minimizing the cost of workflow execution. We have previously designed and analyzed a two-phase scheduling algorithm for utility Grids, called Partial Critical Paths (PCP), which aims to minimize the cost of workflow execution while meeting a user-defined deadline. However, we believe Clouds are different from utility Grids in three ways: on-demand resource provisioning, homogeneous networks, and the pay-as-you-go pricing model. In this paper, we adapt the PCP algorithm for the Cloud environment and propose two workflow scheduling algorithms: a one-phase algorithm which is called IaaS Cloud Partial Critical Paths (IC-PCP), and a two-phase algorithm which is called IaaS Cloud Partial Critical Paths with Deadline Distribution (IC-PCPD2). Both algorithms have a polynomial time complexity which make them suitable options for scheduling large workflows. The simulation results show that both algorithms have a promising performance, with IC-PCP performing better than IC-PCPD2 in most cases. Keywords: Cloud computing; IaaS Clouds; Grid computing; Workflow scheduling; QoS-based scheduling

AB - The advent of Cloud computing as a new model of service provisioning in distributed systems encourages researchers to investigate its benefits and drawbacks on executing scientific applications such as workflows. One of the most challenging problems in Clouds is workflow scheduling, i.e., the problem of satisfying the QoS requirements of the user as well as minimizing the cost of workflow execution. We have previously designed and analyzed a two-phase scheduling algorithm for utility Grids, called Partial Critical Paths (PCP), which aims to minimize the cost of workflow execution while meeting a user-defined deadline. However, we believe Clouds are different from utility Grids in three ways: on-demand resource provisioning, homogeneous networks, and the pay-as-you-go pricing model. In this paper, we adapt the PCP algorithm for the Cloud environment and propose two workflow scheduling algorithms: a one-phase algorithm which is called IaaS Cloud Partial Critical Paths (IC-PCP), and a two-phase algorithm which is called IaaS Cloud Partial Critical Paths with Deadline Distribution (IC-PCPD2). Both algorithms have a polynomial time complexity which make them suitable options for scheduling large workflows. The simulation results show that both algorithms have a promising performance, with IC-PCP performing better than IC-PCPD2 in most cases. Keywords: Cloud computing; IaaS Clouds; Grid computing; Workflow scheduling; QoS-based scheduling

U2 - 10.1016/j.future.2012.05.004

DO - 10.1016/j.future.2012.05.004

M3 - Article

VL - 29

SP - 158

EP - 169

JO - Future Generation Computer Systems

JF - Future Generation Computer Systems

SN - 0167-739X

IS - 1

ER -