Title: P2P design and implementation of a parallel branch and bound algorithm for grids

Authors: Ahcene Bendjoudi, Nouredine Melab, El-Ghazali Talbi

Addresses: Division Theories et Ingenierie des Systemes Informatiques DTISI, CEntre de Recherche sur l'Information, Scientifique et Technique CERIST, Algiers, Algeria, Universite Abderrahmane Mira, Bejaia, Algeria. ' Universite des Sciences et Technologies de Lille, LIFL/UMR CNRS 8022, INRIA Lille Nord Europe – DOLPHIN, 59655 Villeneuve d'Ascq cedex, France. ' Universite des Sciences et Technologies de Lille, LIFL/UMR CNRS 8022, INRIA Lille Nord Europe – DOLPHIN, 59655 Villeneuve d'Ascq cedex, France

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.

Keywords: combinatorial optimisation; permutation flow shop problem; parallel branch and bound; peer-to-peer computing; P2P computing; ProActive; grid computing; flow shop scheduling.

DOI: 10.1504/IJGUC.2009.022031

International Journal of Grid and Utility Computing, 2009 Vol.1 No.2, pp.159 - 168

Received: 18 Dec 2007
Accepted: 22 Aug 2008
Published online: 16 Dec 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article