Cloud computing, a novel and promising model of Service-oriented computing, provides a pay-per-use framework to solve large-scale scientific and business workflow applications. Workflow scheduling in cloud is challenging due to dynamic nature of the cloud, particularly, on demand provisioning, elasticity, heterogeneous resource types, static & dynamic pricing models and virtualization. An example of workflow scheduling is mapping workflow tasks to cloud computing resources. Additionally, these workflow applications have a runtime constraint—the most typical being the cost of the computation and the time that computation requires to complete. Therefore, the focus is on two criteria: makespan and cost. This paper presents an algorithm called NBWS (Normalization based Budget constraint Workflow Scheduling) which generates a workflow schedule which minimizes the schedule length while satisfying the budget constraint. The algorithm undergoes a process of min–max normalization tailed by computing expect reasonable budget(erb) for dispatching the workflow tasks into one of the virtual machines. To minimize the execution time, NBWS algorithm maps the workflow tasks to resources which are having the earliest finish time within the allocated budget. The experimental results demonstrate that NBWS outperforms current state-of-the-art heuristics with respect to budget constraint and minimizing the makespan. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.