On-line maintenance of optimal machine schedules

Aman, Amril ; Balakrishnan, Anantaram ; Chandru, Vijay (1997) On-line maintenance of optimal machine schedules Sadhana (Academy Proceedings in Engineering Sciences), 22 (2). pp. 257-279. ISSN 0256-2499

PDF - Publisher Version

Official URL: http://www.ias.ac.in/j_archive/sadhana/22/2/257-27...

Related URL: http://dx.doi.org/10.1007/BF02744492


Effective and efficient scheduling in a dynamically changing environment 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 methods to update schedules on-line. We consider the problem of dynamically scheduling precedence-constrained jobs on a single processor to minimize the maximum completion time penalty. We first develop an efficient 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 oracles that have perfect information about future job arrivals.

Item Type:Article
Source:Copyright of this article belongs to Indian Academy of Sciences.
Keywords:Scheduling; Design and Analysis of Algorithms; Heuristics
ID Code:5473
Deposited On:19 Oct 2010 12:11
Last Modified:16 May 2016 15:58

Repository Staff Only: item control page