This paper addresses a fundamental trade-off in dynamic scheduling between
the cost of scheduling and the quality of the resulting schedules. The time
allocated to scheduling must be controlled explicitly, in order to obtain
good-quality schedules in reasonable times. As task constraints are relaxed
, the algorithms proposed in this paper increase scheduling complexity to o
ptimize longer and obtain high-quality schedules. When task constraints are
tightened, the algorithms adjust scheduling complexity to reduce the adver
se effect of long scheduling times on the schedule quality. We show that ta
king into account the scheduling time is crucial for honoring the deadlines
of scheduled tasks. We investigate the performance of our algorithms in tw
o scheduling models: one that allows idle-time intervals to exist in the sc
hedule and another that does not. The model with idle-time intervals has im
portant implications for dynamic scheduling which are discussed in the pape
r. Experimental evaluation of the proposed algorithms shows that our algori
thms outperform other candidate algorithms in several parameter configurati
ons.