The use of cloud computing, particularly of Infrastructure as a Service clouds, for the execution of largescale scientific workflows has been a topic of interest in recent years. These environments offer on-demand access to all of the infrastructure required for the deployment of workflows, allowing users to pay only for what they use. This leads to schedulers having to find a trade-off between two conflicting quality of service requirements: Time and cost. The majority of research in this area has focused on developing scheduling algorithms that have as objective minimizing the infrastructure cost while meeting a deadline constraint. Few algorithms, however, have addressed the problem of minimizing the execution time of the workflow while meeting a budget constraint. This paper focuses on the latter case. We propose a budget-distribution algorithm that assigns a portion of the overall workflow budget to the individual tasks. This task-level budget then guides the dynamic scheduling process and is continuously refined to reflect any unexpected costs. When compared to the state-of-the-art algorithm, the performance evaluation results demonstrate that in 88% of the cases, our proposal achieves equal or better performance in terms of meeting the budget constraint and achieves lower execution times in 84% of the cases.