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

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.