Online Multi-Workflow Scheduling under Uncertain Task Execution Time in IaaS Clouds

Cloud has become an important platform for executing numerous deadline-constrained scientific applications generally represented by workflow models. It provides scientists a simple and cost-efficient method of running workflows on their rental Virtual Machines (VMs) anytime and anywhere. Since pay-as-you-go is a dominating pricing solution in clouds, extensive research efforts have been devoted to minimizing the monetary cost of executing workflows by designing tailored VM allocation mechanisms. However, most of them assume that the task execution time in clouds is static and can be estimated in advance, which is impractical in real scenarios due to performance fluctuation of VMs. In this paper, we propose an onliNe multi-workflOw Scheduling Framework, named NOSF, to schedule deadline-constrained workflows with random arrivals and uncertain task execution time. In NOSF, workflow scheduling process consists of three phases, including workflow preprocessing, VM allocation and feedback process. Built upon the new framework, a deadline-aware heuristic algorithm is then developed to elastically provision suitable VMs for workflow execution, with the objective of minimizing the rental cost and improving resource utilization. Simulation results demonstrate that the proposed algorithm significantly outperforms two state-of-the-art algorithms in terms of reducing VM rental costs and deadline violation probability, as well as improving the resource utilization efficiency.

Automated summary

Cloud has become an important platform for executing deadline-constrained scientific applications represented by workflow models. This paper proposes an online multi-workflow scheduling framework, NOSF, to schedule workflows with random arrivals and uncertain task execution time. The framework includes a deadline-aware heuristic algorithm to provision suitable VMs for workflow execution, aiming to minimize rental costs and improve resource utilization. Simulation results show that the proposed algorithm outperforms state-of-the-art algorithms in reducing VM rental costs, deadline violation probability, and improving resource utilization efficiency.