Optimal time-critical scheduling via resource augmentation [electronic resource].
- Washington, D.C. : United States. Dept. of Energy. Office of Energy Research, 1997.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
- Physical Description:
- 12 pages : digital, PDF file
- Additional Creators:
- Sandia National Laboratories
United States. Department of Energy. Office of Energy Research
United States. Department of Energy. Office of Scientific and Technical Information
- We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless Ρ = ΝΡ. We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For the optimization of average flow time, these are the first results of any sort, for any ΝΡ-hard version of the problem, that indicate that it might be possible to design good approximation algorithms.
- Published through SciTech Connect.
29. annual ACM symposium on the interface: computing science and statistics, El Paso, TX (United States), 4-17 May 1997.
Phillips, C.A.; Stein, C.; Wein, J.; Torng, E.
- Funding Information:
View MARC record | catkey: 14349152