P2P design and implementation of a parallel branch and bound algorithm for grids. (18th December 2008)

• Record Type: Journal Article
• Authors: Bendjoudi, Ahcene; Melab, Nouredine; Talbi, El-Ghazali
• Is Part Of: International journal of grid and utility computing. Volume 1:Number 2(2009)
• Page Start: 159
• Page End: 168
• Publication Date: 2008-12-18
• Subjects: combinatorial optimisation -- permutation flow shop problem -- parallel branch and bound -- peer-to-peer computing -- P2P computing -- ProActive -- grid computing -- flow shop scheduling; Electronic data processing -- Distributed processing -- Periodicals; Electronic commerce -- Management -- Computer programs -- Periodicals; 004.605
• Languages: English
• ISSNs: 1741-847X

Abstract

Solving optimally large instances of combinatorial optimisation problems using Branch and Bound (B&B) algorithms is CPU-time intensive and requires a large number of computational resources. To harness such huge amount of resources Peer-to-Peer (P2P) communications must be allowed between resources, and adaptive load balancing and fault-tolerance have to be dealt with when designing and implementing a B&B algorithm. In this paper, we propose a P2P design and implementation of a parallel B&B algorithm on top of the ProActive grid middleware. Load distribution and fault-tolerance strategies are proposed to deal with the dynamic and heterogeneous characteristics of the computational grid. The approach has been promisingly applied to the Flow-Shop scheduling problem and experimented on a computational pool of 1500 CPUs from the GRID'5000 Nation-wide experimental Grid.