| 講演抄録／キーワード |
| 講演名 |
2005-01-28 10:55
An Asynchronous Distributed Branch and Bound for Load Balancing
○Atsushi Sasaki・Tadashi Araragi（NTT）・Shigeru Masuyama（Toyohashi Univ. of Tech.） |
| 抄録 |
（和） |
本稿では，分散システムにおいて，各変数がタスクに対応し，その値がそのタスクの割り当て先ホストを示すような負荷分散問題を解くための新しい非同期分散分枝限定法を提案する．これは，NP困難な離散最適化問題に対して非同期完全分散システムで近似解でない厳密な最適解を求める最初の最適化分散アルゴリズムである．これは従来の分散最適化アルゴリズムに比べて高い柔軟性と頑健性を持つ．そのアイデアには，分枝限定法，分割統治法，および，局所探索法におけるλ-opt近傍の考え方を複合させている．本手法は，今後の拡張により，大規模動的分散システムにおいて有用になり得る． |
| （英） |
We propose a new asynchronous distributed branch and bound algorithm for a load balancing problem in which each variable corresponds to each task and indicates a host, where the corresponding task is assigned, in a geographically distributed system. This is the first algorithm to provide the exact optimum solution, not an approximation, for NP-hard discrete optimization problems in a distributed context without any centralized control. Moreover, this algorithm has more flexibility and greater robustness than the conventional distributed algorithms. The idea behind the algorithm is a complex consisting of branch and bound, divide and conquer, and λ-opt neighborhood in local search. This algorithm has a possibility to be useful in an actual huge dynamic distributed system. |
| キーワード |
（和） |
分散アルゴリズム / 離散最適化 / 分枝限定法 / 負荷分散 / 整数計画 / / / |
| （英） |
Distributed Algorithm / Discrete Optimization / Branch and Bound / Load Balancing / Integer Programming / / / |
| 文献情報 |
信学技報, vol. 104, no. 642, COMP2004-63, pp. 23-32, 2005年1月. |
| 資料番号 |
COMP2004-63 |
| 発行日 |
2005-01-21 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|