Search this article in Google Scholar


分類 国際会議
著者名 (author) Satoshi Fujita,Masayuki Masukawa,Shigeaki Tagashira
英文著者名 (author)
編者名 (editor)
編者名 (英文)
キー (key)
表題 (title) A Fast Branch-and-Bound Scheme for the Multiprocessor Scheduling Problem with Communication Time
表題 (英文)
書籍・会議録表題 (booktitle) The 2003 International Conference on Parallel Processing Workshops (ICPP 2003 Workshops)
書籍・会議録表題(英文)
巻数 (volume)
号数 (number)
ページ範囲 (pages) 104-111
組織名 (organization)
出版元 (publisher)
出版元 (英文)
出版社住所 (address)
刊行月 (month) October
出版年 (year) 2003
付加情報 (note) Kaohsiung, Taiwan
注釈 (annote) DOI: 10.1109/ICPPW.2003.1240360
内容梗概 (abstract) In this paper, we propose a fast branch-and-bound (B&B) algorithm for solving the multiprocessor scheduling problem with non-negligible communication time. The basic idea of our proposed method is to focus on an "inevitable" communication delay that could not be avoided in any assignment of tasks onto the processors. The proposed method is implemented as a part of B&B scheme, and the performance of the scheme is evaluated experimentally. The result of experiments implies that for randomly generated instances consisting of at most 300 tasks: 1) we could solve more than 90% of those instances within one minute if any communication takes zero time unit; 2) the percentage of hard instances increases by increasing the number of processors and the time required for each communication; and 3) the proposed method could achieve a significant improvement in increasing the lower bound of partial solutions especially for those hard instances. Those results suggest that the proposed method could output an optimum solution for many instances within a short computing time by combining it with a good heuristic to give a better upper bound.
論文電子ファイル Not available.


[1-42]  Satoshi Fujita, Masayuki Masukawa, and Shigeaki Tagashira, ``A Fast Branch-And-Bound Scheme for the Multiprocessor Scheduling Problem with Communication Time,'' In The 2003 International Conference on Parallel Processing Workshops (ICPP 2003 Workshops) , pp. 104-111, October 2003. (Kaohsiung, Taiwan)

@inproceedings{1_42,
    author = {Satoshi Fujita and Masayuki Masukawa and Shigeaki Tagashira},
    author_e = {},
    editor = {},
    editor_e = {},
    title = {A Fast Branch-and-Bound Scheme for the Multiprocessor Scheduling
    Problem with Communication Time},
    title_e = {},
    booktitle = {The 2003 International Conference on Parallel Processing
    Workshops (ICPP 2003 Workshops) },
    booktitle_e = {},
    volume = {},
    number = {},
    pages = {104-111},
    organization = {},
    publisher = {},
    publisher_e = {},
    address = {},
    month = {October},
    year = {2003},
    note = {Kaohsiung, Taiwan},
    annote = {DOI: 10.1109/ICPPW.2003.1240360 }
}

This site is maintained by Distributed System Laboratory.

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