In this paper, we introduce a new set of dynamic scheduling algorithms for scheduling and guaranteeing the deadline compliance of a set of aperiodic real-time tasks on a uniprocessor architecture. The task model selected is that of non-preemptable tasks with arbitrary start times and deadlines. The proposed algorithms address a fundamental trade-off in dynamic scheduling between the cost of scheduling and the quality of the resulting schedules. The algorithms control the time allocated to scheduling explicitly, in order to obtain good-quality schedules in reasonable times. We show that taking into account the scheduling time is crucial for honoring the deadlines of scheduled real-time tasks. The paper provides experimental evaluation of our algorithms via performance comparisons with existing landmark algorithms that were originally designed to address some similar issues. The results of our experiments show that our algorithms outperform the existing techniques in several parameter configurations.