Budget constrained dataflow scheduling for minimized completion time on the cloud

Dabin Ding, Fei Cao, Dunren Che, Michelle M. Zhu, Wen Chi Hou

Research output: Contribution to journalArticlepeer-review


Cloud computing provides high-end computing capabilities so that users can access data and applications anywhere in the world on demand and pay for what they use. It is emerging as a promising computing paradigm for large-scale data intensive queries, which are usually modeled as complex Directed Acyclic Graph (DAG)-structured data processing dataflows with arbitrary data operators as nodes and producer-consumer interactions as directed edges. The optimization problem of scheduling dataflows on the Cloud is a very complex and challenging task which is similar to query optimization. Optimization must satisfy a variety of objectives and constraints, while taking into account the particular characteristics of the underlying Cloud environment. In addition to achieving minimum query completion time, the commercialization of Clouds requires policies to take users' economic concerns as well. In this paper, we formulate scheduling of dataflows onto Cloud resources toward the objective of minimizing the query completion time under certain budget constraint. A heuristic scheduling algorithm, Layer-oriented Resource Allocation within Budget constraint (LRA-B) is proposed and evaluated. Experiments are conducted on numerous dataflows and Cloud environment configurations, and the overall results are quite promising and indicate the effectiveness of our algorithm.

Original languageEnglish
Pages (from-to)208-220
Number of pages13
JournalInternational Journal of Computers and their Applications
Issue number4
StatePublished - Dec 2013


  • Budget constraint
  • Cloud computing
  • Dataflows
  • Query completion time
  • Scheduling


Dive into the research topics of 'Budget constrained dataflow scheduling for minimized completion time on the cloud'. Together they form a unique fingerprint.

Cite this