Distributed workflow scheduling under throughput and budget constraints in grid environments

Fei Cao, Michelle M. Zhu, Dabin Ding

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

7 Scopus citations


Grids enable sharing, selection and aggregation of geographically distributed resources among various organizations. They are emerging as promising computing paradigms for resource and compute-intensive scientific workflow applications modeled as Directed Acyclic Graph (DAG) with intricate inter-task dependencies. With the growing popularity of real-time applications, streaming workflows continuously produce large quantity of experimental or simulation datasets, which need to be processed in a timely manner subject to certain performance and resource constraints. However, the heterogeneity and dynamics of Grid resources complicate the scheduling of streaming applications. In addition, the commercialization of Grids as a future trend is calling for policies to take resource cost into account while striving to satisfy the users' Quality of Service (QoS) requirements. In this paper, streaming workflow applications are modeled as DAGs. We formulate scheduling problems with two different objectives in mind, namely either maximize the throughput under a budget/cost constraint or minimize the execution cost under a minimum throughput constraint. Two different algorithms named as Budget constrained RATE ( -RATE) and Budget constrained SWAP ( -SWAP) are developed and evaluated under the first objective; Another two algorithms named as Throughput constrained RATE ( -RATE) and Throughput constrained SWAP ( -SWAP) are evaluated under the second objective. Experimental results based on GridSim showed that our algorithms either achieved much lower cost with similar throughput, or higher throughput with similar cost compared with other comparable existing algorithms.

Original languageEnglish
Title of host publicationJob Scheduling Strategies for Parallel Processing - 17th International Workshop, JSSPP 2013, Revised Selected Papers
PublisherSpringer Verlag
Number of pages19
ISBN (Print)9783662437780
StatePublished - 2014
Event17th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2013 - Boston, MA, United States
Duration: 24 May 201424 May 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8429 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other17th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2013
Country/TerritoryUnited States
CityBoston, MA


  • Grid computing
  • Streaming workflow
  • Task scheduling
  • Throughput and budget


Dive into the research topics of 'Distributed workflow scheduling under throughput and budget constraints in grid environments'. Together they form a unique fingerprint.

Cite this