DescriptionThe advantages of cloud computing including elastic, on demand, and pay per use instances, provide an ideal model for resourcing large scale state-of-the-art scientific analyses. Large scale scientific experiments are typically represented as workflows and are the common model for characterizing escience experiments and data analytics. Hosting and managing scientific applications on the cloud poses new challenges in terms of workflow scheduling which is key in leveraging cloud 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. In this paper, we present a new algorithm, Dynamic Workload Scheduler (DWS). Our algorithm addresses scheduling of multiple workflows with the aim of satisfying the deadline for each workflow in a typical cloud environment in which workflows can be submitted at any time. 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.