Search this article in Google Scholar


分類 論文誌
著者名 (author) Satoshi Fujita
英文著者名 (author)
キー (key)
表題 (title) A Branch-and-Bound Algorithm for Solving the Multiprocessor Scheduling Problem with Improved Lower Bounding Techniques
表題 (英文)
定期刊行物名 (journal) IEEE Trans. Computers
定期刊行物名 (英文)
巻数 (volume) 60
号数 (number) 7
ページ範囲 (pages) 1006-1016
刊行月 (month) July
出版年 (year) 2011
付加情報 (note)
注釈 (annote) http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5483286
内容梗概 (abstract) In branch-and-bound (B&B) schemes for solving a minimization problem, a better lower bound could prune many meaningless branches which do not lead to an optimum solution. In this paper, we propose several techniques to refine the lower bound on the makespan in the multiprocessor scheduling problem (MSP). The key idea of our proposed method is to combine an efficient quadratic-time algorithm for calculating the Fernández's bound, which is known as the best lower bounding technique proposed in the literature with two improvements based on the notions of binary search and recursion. The proposed method was implemented as a part of a B&B algorithm for solving MSP, and was evaluated experimentally. The result of experiments indicates that the proposed method certainly improves the performance of the underlying B&B scheme. In particular, we found that it improves solutions generated by conventional heuristic schemes for more than 20 percent of randomly generated instances, and for more than 80 percent of instances, it could provide a certification of optimality of the resulting solutions, even when the execution time of the B&B scheme is limited by one minute.
論文電子ファイル Not available.


[0-45]  Satoshi Fujita, ``A Branch-And-Bound Algorithm for Solving the Multiprocessor Scheduling Problem with Improved Lower Bounding Techniques,'' IEEE Trans. Computers, vol. 60, no. 7, pp. 1006-1016, July 2011.

@article{0_45,
    author = {Satoshi Fujita},
    author_e = {},
    title = {A Branch-and-Bound Algorithm for Solving the Multiprocessor
    Scheduling Problem with Improved Lower Bounding Techniques},
    title_e = {},
    journal = {IEEE Trans. Computers},
    journal_e = {},
    volume = {60},
    number = {7},
    pages = {1006-1016},
    month = {July},
    year = {2011},
    note = {},
    annote = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5483286}
}

This site is maintained by Distributed System Laboratory.

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