An Asynchronous Distributed Branch and Bound for Load Balancing

摘要

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 A-opt neighborhood in local search. This algorithm has a possibility to be useful in an actual huge dynamic distributed system.