The Impact of Task Runtime Estimate Accuracy on Scheduling Workloads of Workflows

Alexey Ilyushkin, Dick Epema

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

9 Citations (Scopus)
139 Downloads (Pure)


Workflow schedulers often rely on task runtime estimates when making scheduling decisions, and they usually target the scheduling of a single workflow or batches of workflows. In contrast, in this paper, we evaluate the impact of the absence or limited accuracy of task runtime estimates on slowdown when scheduling complete workloads of workflows that arrive over time. We study a total of seven scheduling policies: four of these are popular existing policies for (batches of) workloads from the literature, including a simple backfilling policy which is not aware of task runtime estimates, two are novel workloadoriented policies, including one which targets fairness, and one is the well-known HEFT policy for a single workflow adapted to the online workload scenario. We simulate homogeneous and heterogeneous distributed systems to evaluate the performance of these policies under varying accuracy of task runtime estimates. Our results show that for high utilizations, the order in which workflows are processed is more important than the knowledge of correct task runtime estimates. Under low utilizations, all policies considered show good results, even a policy which does not use task runtime estimates. We also show that our Fair Workflow Prioritization (FWP) policy effectively decreases the variance of workflow slowdown and thus achieves fairness, and that the plan-based scheduling policy derived from HEFT does not show much performance improvement while bringing extra complexity to the scheduling process.
Original languageEnglish
Title of host publication18th IEEE/ACM Int'l Symp. on Cluster, Cloud and Grid Computing
Number of pages11
ISBN (Electronic)978-1-5386-5815-4
Publication statusPublished - 2018


  • workflow
  • workload
  • scheduling
  • fairness
  • plan
  • dynamic
  • runtime estimates
  • DAG
  • dynamic scheduling


Dive into the research topics of 'The Impact of Task Runtime Estimate Accuracy on Scheduling Workloads of Workflows'. Together they form a unique fingerprint.

Cite this