The search functionality is under construction.
The search functionality is under construction.

Semi-Dynamic Multiprocessor Scheduling with an Asymptotically Optimal Performance Ratio

Satoshi FUJITA

  • Full Text Views

    0

  • Cite this

Summary :

In this paper, we consider a problem of assigning n independent tasks onto m identical processors in such a way that the overall execution time of the tasks will be minimized. Unlike conventional task assignment problem, we assume that the execution time of each task is not fixed in advance, and merely upper and lower bounds of the execution time are given at the compile time. In the following, we first provide a theoretical analysis of several conventional scheduling policies in terms of the worst case slowdown compared with the outcome of an optimal off-line scheduling policy. It is shown that the best known algorithm in the literature achieves a worst case performance ratio of 1 + 1/f(n) where f(n) = O(n2/3) for any fixed m, which approaches to one by increasing n to the infinity. We then propose a new scheme that achieves better worst case ratio of 1 + 1/g(n) where g(n) = Θ (n/log n) for any fixed m, which approaches to one more quickly than previous schemes.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.8 pp.1764-1770
Publication Date
2009/08/01
Publicized
Online ISSN
1745-1337
DOI
10.1587/transfun.E92.A.1764
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category
Theory

Authors

Keyword