%0 Journal Article %J Concurrency and Computation: Practice and Experience %D 2021 %T Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on IaaS Cloud platforms %A Eddy Caron %A Yves Caniou %A Aurélie Kong Win Chang %A Yves Robert %B Concurrency and Computation: Practice and Experience %V 33 %P e6065 %G eng %R https://doi.org/10.1002/cpe.6065 %0 Journal Article %J International Journal of High Performance Computing Applications %D 2019 %T Scheduling Independent Stochastic Tasks under Deadline and Budget Constraints %A Louis-Claude Canon %A Aurélie Kong Win Chang %A Yves Robert %A Frederic Vivien %X This article discusses scheduling strategies for the problem of maximizing the expected number of tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The execution times of tasks follow independent and identically distributed probability laws. The main questions are how many processors to enroll and whether and when to interrupt tasks that have been executing for some time. We provide complexity results and an asymptotically optimal strategy for the problem instance with discrete probability distributions and without deadline. We extend the latter strategy for the general case with continuous distributions and a deadline and we design an efficient heuristic which is shown to outperform standard approaches when running simulations for a variety of useful distribution laws. %B International Journal of High Performance Computing Applications %V 34 %P 246-264 %8 2019-06 %G eng %N 2 %R https://doi.org/10.1177/1094342019852135 %0 Conference Paper %B 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) %D 2018 %T Budget-Aware Scheduling Algorithms for Scientific Workflows with Stochastic Task Weights on Heterogeneous IaaS Cloud Platforms %A Yves Caniou %A Eddy Caron %A Aurélie Kong Win Chang %A Yves Robert %K budget aware algorithm %K multi criteria scheduling %K workflow %X This paper introduces several budget-aware algorithms to deploy scientific workflows on IaaS cloud platforms, where users can request Virtual Machines (VMs) of different types, each with specific cost and speed parameters. We use a realistic application/platform model with stochastic task weights, and VMs communicating through a datacenter. We extend two well-known algorithms, MinMin and HEFT, and make scheduling decisions based upon machine availability and available budget. During the mapping process, the budget-aware algorithms make conservative assumptions to avoid exceeding the initial budget; we further improve our results with refined versions that aim at re-scheduling some tasks onto faster VMs, thereby spending any budget fraction leftover by the first allocation. These refined variants are much more time-consuming than the former algorithms, so there is a trade-off to find in terms of scalability. We report an extensive set of simulations with workflows from the Pegasus benchmark suite. Most of the time our budget-aware algorithms succeed in achieving efficient makespans while enforcing the given budget, despite (i) the uncertainty in task weights and (ii) the heterogeneity of VMs in both cost and speed values. %B 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) %I IEEE %C Vancouver, BC, Canada %8 2018-05 %G eng %R 10.1109/IPDPSW.2018.00014