Search this article in Google Scholar


分類 国際会議
著者名 (author) Satoshi Fujita
英文著者名 (author)
編者名 (editor)
編者名 (英文)
キー (key)
表題 (title) A Semi-Dynamic Multiprocessor Scheduling Algorithm with an Asymptotically Optimal Performance Ratio
表題 (英文)
書籍・会議録表題 (booktitle) Euro-Par 2002, Parallel Processing, 8th International Euro-Par Conference, LNCS
書籍・会議録表題(英文)
巻数 (volume) 2400
号数 (number)
ページ範囲 (pages) 240-247
組織名 (organization)
出版元 (publisher)
出版元 (英文)
出版社住所 (address)
刊行月 (month) August
出版年 (year) 2002
付加情報 (note) Paderborn, Germany
注釈 (annote) Acceptance rate: 67/265 = 25%, http://www.springerlink.com/content/hk5ae60we3aq1vaf/
内容梗概 (abstract) In this paper, we consider the problem of assigning a set of n independent tasks onto a set of m identical processors in such a way that the overall execution time is minimized provided that the precise task execution times are not known a priori. 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 scheduling policy. It is shown that the best known algorithm in the literature achieves a worst case competitive ratio of 1 + 1/f(n) where f(n) = O(n 2/3) for any fixed m, that approaches to one by increasing n to the infinity. We then propose a new scheme that achieves a better worst case ratio of 1 + 1/g(n) where g(n) = ⊝ (n/ log n) for any fixed m, that approaches to one more quickly than the other schemes.
論文電子ファイル Not available.


[1-34]  Satoshi Fujita, ``A Semi-Dynamic Multiprocessor Scheduling Algorithm with an Asymptotically Optimal Performance Ratio,'' In Euro-Par 2002, Parallel Processing, 8th International Euro-Par Conference, LNCS, vol. 2400, pp. 240-247, August 2002. (Paderborn, Germany)

@inproceedings{1_34,
    author = {Satoshi Fujita},
    author_e = {},
    editor = {},
    editor_e = {},
    title = {A Semi-Dynamic Multiprocessor Scheduling Algorithm with an
    Asymptotically Optimal Performance Ratio      },
    title_e = {},
    booktitle = {Euro-Par 2002, Parallel Processing, 8th International Euro-Par
    Conference, LNCS},
    booktitle_e = {},
    volume = {2400},
    number = {},
    pages = {240-247},
    organization = {},
    publisher = {},
    publisher_e = {},
    address = {},
    month = {August},
    year = {2002},
    note = {Paderborn, Germany},
    annote = {Acceptance rate: 67/265 = 25%, http://www.springerlink.com/content
    /hk5ae60we3aq1vaf/}
}

This site is maintained by Distributed System Laboratory.

PMAN 2.5.5 - Paper MANagement system / (C) 2002-2008, Osamu Mizuno / All rights reserved.