This paper addresses the problem of task scheduling and resource provisioning for workloads submitted on IaaS clouds. It presents a novel algorithm capable of executing workloads with deadline constraints, while efficiently utilizing given budgets. Our simulation study demonstrates a substantial performance gain by the proposal. © 2014 IEEE.