On scientific workflow scheduling in clouds under budget constraint

Xiangyu Lin, Chase Qishi Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

53 Scopus citations


Next-generation e-Science features large-scale, compute-intensive workflows of many computing modules that are typically executed in a distributed manner. With the recent emergence of cloud computing and the rapid deployment of cloud infrastructures, an increasing number of scientific workflows have been shifted or are in active transition to cloud environments. As cloud computing makes computing a utility, scientists across different application domains are facing the same challenge of reducing financial cost in addition to meeting the traditional goal of performance optimization.We construct analytical models to quantify the network performance of scientific workflows using cloud-based computing resources, and formulate a task scheduling problem to minimize the workflow end-to-end delay under a user-specified financial constraint. We rigorously prove that the proposed problem is not only NP-complete but also non-approximable. We design a heuristic solution to this problem, and illustrate its performance superiority over existing methods through extensive simulations and real-life workflow experiments based on proof-ofconcept implementation and deployment in a local cloud testbed.

Original languageEnglish (US)
Title of host publicationProceedings
Subtitle of host publicationInternational Conference on Parallel Processing - The 42nd Annual Conference, ICPP 2013
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Print)9780769551173
StatePublished - 2013
Externally publishedYes
Event42nd Annual International Conference on Parallel Processing, ICPP 2013 - Lyon, France
Duration: Oct 1 2013Oct 4 2013

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918


Other42nd Annual International Conference on Parallel Processing, ICPP 2013

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics
  • Hardware and Architecture


  • Cloud computing
  • Scientific workflows
  • Workflow scheduling


Dive into the research topics of 'On scientific workflow scheduling in clouds under budget constraint'. Together they form a unique fingerprint.

Cite this