ONLINE MAINTENANCE OF OPTIMAL MACHINE SCHEDULES

Citation
A. Aman et al., ONLINE MAINTENANCE OF OPTIMAL MACHINE SCHEDULES, Sadhana, 22, 1997, pp. 257-279
Citations number
23
Categorie Soggetti
Engineering
Journal title
ISSN journal
02562499
Volume
22
Year of publication
1997
Part
2
Pages
257 - 279
Database
ISI
SICI code
0256-2499(1997)22:<257:OMOOMS>2.0.ZU;2-T
Abstract
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.