DDBWS: a dynamic deadline and budget-aware workflow scheduling algorithm in workflow-as-a-service environments

Workflow scheduling has been excessively studied in different environments like clusters, grids, and clouds. Cloud is a scalable, cost-effective environment that allows users to access an unlimited amount of resources and offers a pay-as-you-go model. An increase in the users' desire to run their workflow applications on clouds leads to the development of multi-tenant environments like workflow-as-a-service platforms (WaaS). By leveraging cloud features, WaaS offers an environment where users can submit their workflows for execution with different quality of service (QoS) attributes at different. The problem of finding an appropriate scheduling algorithm considering factors like resource heterogeneity and QoS requirements is an NP-complete problem. Most of the existing algorithms in the literature are designed to schedule a single instance of a workflow or have a static behavior. Using static scheduling in dynamic environments like WaaS can lead to a low planning success rate. Besides, while it is possible to share resources between users, for simplicity purposes a majority of proposed algorithms schedule at most one task on a computing resource at any given point in time. They also consider either the time or cost as a hard constraint during scheduling. To cover these limitations in this study, we propose DDBWS, a Dynamic, Deadline and Budget-aware, Workflow Scheduling algorithm that is designed specifically for the WaaS environments. DDBWS schedules workflows by solving a multi-resource packing problem. Unlike several existing algorithms, it considers both CPU and memory demands for tasks simultaneously. Also, it leverages containers to run multiple tasks on a VM concurrently. It uses a bi-factor to control the tradeoff between cost and resource utilization during the mapping of tasks to resources. Based on real-world workflow traces, we have generated 6 different datasets of synthetic workflows. To compare the performance of the proposed scheduling algorithm, we chose two of the state-of-the-art dynamic concurrent workflow scheduling algorithms called EPSM and MW-HBDCS. We have conducted several experiments on these datasets. The results of the performed experiments show that DDBWS achieves at least 96% planning success rate on 6 different workloads which is a comparable PSR. The proposed algorithm decreases the total leased VM numbers considerably. It also outperforms its rivals in terms of the total execution cost and decreases the overall execution cost by at least 8.03% and on average 32.08%. The 95% confidence interval for this decrease is 32.08 +/- 14.1 based on 12 samples.

Automated summary

This study proposes a Dynamic, Deadline and Budget-aware, Workflow Scheduling algorithm called DDBWS specifically designed for WaaS environments. By solving a multi-resource packing problem, DDBWS schedules workflows considering both CPU and memory demands for tasks simultaneously, showing promising performance results in experiments.