Scheduling online mixed-parallel workflows of rigid tasks in heterogeneous multi-cluster environments

Yi Rong Wang, Kuo Chan Huang*, Feng-Jian Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


Workflow scheduling on parallel systems has long been known to be a NP-complete problem. As modern grid and cloud computing platforms emerge, it becomes indispensable to schedule mixed-parallel workflows in an online manner in a speed-heterogeneous multi-cluster environment. However, most existing scheduling algorithms were not developed for online mixed-parallel workflows of rigid data-parallel tasks and multi-cluster environments, therefore they cannot handle the problem efficiently. In this paper, we propose a scheduling framework, named Mixed-Parallel Online Workflow Scheduling (MOWS), which divides the entire scheduling process into four phases: task prioritizing, waiting queue scheduling, task rearrangement, and task allocation. Based on this framework, we developed four new methods: shortest-workflow-first, priority-based backfilling, preemptive task execution and All-EFT task allocation, for scheduling online mixed-parallel workflows of rigid tasks in speed-heterogeneous multi-cluster environments. To evaluate the proposed scheduling methods, we conducted a series of simulation studies and made comparisons with previously proposed approaches in the literature. The experimental results indicate that each of the four proposed methods outperforms existing approaches significantly and all these approaches in MOWS together can achieve more than 20% performance improvement in terms of average turnaround time.

Original languageEnglish
Pages (from-to)35-47
Number of pages13
JournalFuture Generation Computer Systems
StatePublished - 1 Jul 2016


  • Heterogeneous multi-cluster environment
  • Mixed-parallel applications
  • Workflow scheduling


Dive into the research topics of 'Scheduling online mixed-parallel workflows of rigid tasks in heterogeneous multi-cluster environments'. Together they form a unique fingerprint.

Cite this