Scalable and Fault Tolerant Hierarchical B&B Algorithm for Computational Grids
Abstract
Solving to optimality large instances of combinatorial optimization problems using Branch and Bound (B&B) algorithms requires a huge amount of computing resources. Nowadays, such power is provided by large scale environments such as computational grids. However, grids induce new challenges: scalability, heterogeneity, and fault tolerance. Most of existing grid-based B&Bs are developed using the Master-Worker paradigm, their scalability is therefore limited. Moreover fault tolerance is rarely addressed in these works. In this thesis, we propose three main contributions to deal with these issues: P2P-B&B, H-B&B, and FTH-B&B. P2P-B&B is a MW-based B&B framework which deals with scalability by reducing the task request frequency and enabling direct communication between workers. H-B&B also deals with scala-
bility. Unlike the state-of-the-art approaches, H-B&B is fully dynamic and adaptive, meaning it takes into account the dynamic acquisition of new computing resources. FTH-B&B is based on new fault tolerant mechanisms enabling efficient building of the hierarchy and maintainingits balancing, and minimizing of work redundancy when storing and recovering tasks. The proposed approaches have been implemented using ProActive grid-middleware and applied to the Flow-Shop scheduling Problem (FSP). The large scale experiments performed on Grid’5000 proved the efficiency of the proposed approaches.
Description
Keywords
Parallel B&B, Master-Worker, Hierarchical Master-Worker, Fault Tolerance, Grid Computing, Large Scale Experiment, FSP, ProActive, Grid’5000