Dynamic multi-workflow scheduling: A deadline and cost-aware approach for commercial clouds

Cloud computing, specifically its elastic, on demand, and pay per use instances, provide an ideal model for resourcing large scale state-of-the-art scientific analyses. Such scientific work is typically represented as workflows — the most common model for characterizing e-Science experiments and data analysis. Hosting and managing scientific applications on the cloud poses new challenges in terms of workflow scheduling which is key in leveraging its inherent cost and performance benefits. Prior research has studied static scheduling when the number of workflows is known in advance and all are submitted at the same time. However, in practice, a scheduler may have to schedule an unpredictable stream of workflows, for example, recent workflow management systems — such as Parsl, do not construct complete workflows at any stage during their execution, rather they generate partial workflows dynamically during execution — somewhat akin to lazy evaluation. This change in the way in which scientific data and workflows are created and processed represents a disruptive change to the way in which scheduling needs to occur. This paper represents a first and necessary step towards addressing scheduling problems of this nature, in which we present a new algorithm, Dynamic Workload Scheduler (DWS) that handles the dynamics of multiple deadline constrained workflows arriving randomly and scheduling these workflows with reducing cost in mind. Our results show that the DWS algorithm achieves an average 10% higher success rate in terms of fulfilling deadlines for different workloads and reduces the overall cost by an average 23% when compared to the most recent comparable algorithm.