Partitioning-based workflow scheduling in clouds

Khaled Almi'Ani, Young Choon Lee

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

12 Citations (Scopus)


Many applications in science and engineering become increasingly complex and large scale. These applications often consist of a large number of precedence-constrained tasks forming workflows represented by directed acyclic graph (DAG). In recent years, cloud computing has greatly leveraged the elastic and cost-efficient deployment of these applications. However, their effective deployment is largely dependent on the scheduling algorithm adopted. Most existing workflow scheduling algorithms are designed to optimize deadline or budget/cost, i.e., one being the objective and the other being constraint. In this paper, we present the Partitioning-Based Workflow Scheduling (PBWS) algorithm, which liberates the user from explicitly setting the upper bound of deadline and cost. Instead, PBWS adopts a slack parameter that controls the tradeoff point between deadline and cost. In particular, PBWS partitions a workflow into a number of small task graphs (or simply partitions) for which the granularity of such partitions is determined by the slack parameter. Each of these partitions is then matched with the best performing cloud resource in terms of both the overall execution time (makespan) and cost. The size of partitions may change by rearranging tasks between different partitions for the optimization of resource assignment. Our experimental results show that our PBWSalgorithm outperforms two existing algorithms in terms of cost by a large margin with little overhead on makespan.

Original languageEnglish
Title of host publicationProceedings - IEEE 30th International Conference on Advanced Information Networking and Applications, IEEE AINA 2016
EditorsLeonard Barolli, Makoto Takizawa, Tomoya Enokido, Antonio J. Jara, Yann Bocchi
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages8
ISBN (Electronic)9781509018581
ISBN (Print)9781509018574
Publication statusPublished - 19 May 2016
Event30th IEEE International Conference on Advanced Information Networking and Applications, AINA 2016 - Crans-Montana, Switzerland
Duration: 23 Mar 201625 Mar 2016

Publication series

NameInternational Conference on Advanced Information Networking and Applications Proceedings
PublisherIEEE Computer Society
ISSN (Print)1550-445X


Other30th IEEE International Conference on Advanced Information Networking and Applications, AINA 2016


Dive into the research topics of 'Partitioning-based workflow scheduling in clouds'. Together they form a unique fingerprint.

Cite this