In Infrastructure as a Service (IaaS) Clouds, minimizing the application scheduling length (makespan) while satisfying a given budget constraint is one of the most critical Quality of Service (QoS) requirements since time and cost are the primary concerns for end users. Although various budget-aware scheduling algorithms have been proposed, many either yield a higher makespan or fail to satisfy the budget constraint due to their task prioritization and budget distribution approaches. This paper presents Budget-Constrained Application Scheduling (BUCAS), a novel heuristic algorithm that addresses application scheduling under budget constraints in IaaS clouds. The key innovation of BUCAS is its Minimum Budget Cost Level (MBCL) mechanism, which fairly distributes the overall budget among unassigned tasks. MBCL converts the application’s overall budget constraint into task-level constraints by weighting each task’s minimum execution cost with the ratio of the given budget to the application’s lowest total cost. By pre-assigning budget costs at the task level, the BUCAS algorithm achieves a quadratic-time scheduling that minimizes makespan without repeatedly recalculating the global budget at each step. Experimental results on both randomly generated task graphs and real-world workflows show that BUCAS achieves shorter makespan while satisfying budget constraints compared to state-of-the-art algorithms. For example, on CyberShake workflows with 1,000 tasks, BUCAS reduces the makespan standard deviation by 90.4%, 42.1%, and 66.9% relative to the MSLBL, FBCWS, and NRBWS algorithms, respectively.