Effective and efficient scheduling in a dynamically changing environme
nt is important for real-time control of manufacturing, computer, and
telecommunication systems. This paper illustrates the algorithmic and
analytical issues associated with developing efficient and effective m
ethods to update schedules on-line. We consider the problem of dynamic
ally scheduling precedence-constrained jobs on a single processor to m
inimize the maximum completion time penalty. We first develop an effic
ient technique to reoptimize a rolling schedule when new jobs arrive.
The effectiveness of reoptimizing the current schedule as a long-term
on-line strategy is measured by bounding its performance relative to o
racles that have perfect information about future job arrivals.