ONLINE MAINTENANCE OF OPTIMAL MACHINE SCHEDULES

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.