Email RIS file
Bookmark
Report an Issue

Optimal time-critical scheduling via resource augmentation [electronic resource].

Published
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, and United States. Department of Energy. Office of Scientific and Technical Information
Access Online

Availability

I Want It
I Want It

Finding items...

Restrictions on Access
Free-to-read Unrestricted online access
Summary
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.
Report Numbers
E 1.99:sand--97-0809c
E 1.99: conf-970599--1-exc.abst.
conf-970599--1-exc.abst.
sand--97-0809c
Subject(s)
Other Subject(s)
Note
Published through SciTech Connect.
04/01/1997.
"sand--97-0809c"
" conf-970599--1-exc.abst."
"DE97004634"
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
AC04-94AL85000
View MARC record | catkey: 14349152