The search functionality is under construction.

The search functionality is under construction.

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*(*n*^{2/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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Satoshi FUJITA, "Semi-Dynamic Multiprocessor Scheduling with an Asymptotically Optimal Performance Ratio" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 8, pp. 1764-1770, August 2009, doi: 10.1587/transfun.E92.A.1764.

Abstract: 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*(*n*^{2/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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1764/_p

Copy

@ARTICLE{e92-a_8_1764,

author={Satoshi FUJITA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Semi-Dynamic Multiprocessor Scheduling with an Asymptotically Optimal Performance Ratio},

year={2009},

volume={E92-A},

number={8},

pages={1764-1770},

abstract={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*(*n*^{2/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.},

keywords={},

doi={10.1587/transfun.E92.A.1764},

ISSN={1745-1337},

month={August},}

Copy

TY - JOUR

TI - Semi-Dynamic Multiprocessor Scheduling with an Asymptotically Optimal Performance Ratio

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1764

EP - 1770

AU - Satoshi FUJITA

PY - 2009

DO - 10.1587/transfun.E92.A.1764

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E92-A

IS - 8

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - August 2009

AB - 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*(*n*^{2/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.

ER -