P2P design and implementation of a parallel ...
Document type :
Compte-rendu et recension critique d'ouvrage
Title :
P2P design and implementation of a parallel branch and bound algorithm for grids
Author(s) :
Bendjoudi, Ahcène [Auteur]
Laboratoire de Méthodes de Conception de Systèmes [LMCS]
Melab, Nouredine [Auteur]
Centre de recherche sur l'Information Scientifique et Technique [CERIST]
Talbi, El-Ghazali [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire de Méthodes de Conception de Systèmes [LMCS]
Melab, Nouredine [Auteur]
Centre de recherche sur l'Information Scientifique et Technique [CERIST]
Talbi, El-Ghazali [Auteur]

Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Journal title :
International Journal of Grid and Utility Computing
Pages :
159-168
Publisher :
Inderscience
Publication date :
2009
ISSN :
1741-847X
HAL domain(s) :
Informatique [cs]/Autre [cs.OH]
English abstract : [en]
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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :