Balanceamento de Carga em um algoritmo Branch-and-Bound para execução em Grades computacionais

This work introduces new techniques of load balance for a distributed branch-and-bound algorithm, applied to the Steiner Problem in Graphs (SPG), to be executed on computational Grids. Many Grids are composed of cluster of processors connected via highspeed links and the clusters, geographically distant, are connected through low-speed links, in a hierarchical fashion. In Grids, the processor performance may vary a lot during a certain period of time due to the fact that they are usually shared with several other applications. The proposed load balance algorithms have the following features: i) they do not employ the usual master-worker paradigm; ii) they consider the hierarchical structure of such Grids and the processors performance iii) they estimate the future load of processes. Several experiments were executed showing the efficiency of the proposed algorithms.