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

Simple item page
dc.citation.epage168
dc.citation.issue2
dc.citation.spage159
dc.citation.volume1
dc.contributor.authorBendjoudi, Ahcène
dc.contributor.authorMelab, Nouredine
dc.contributor.authorTalbi, El-Ghazali
dc.date.accessioned2013-06-12T10:14:26Z
dc.date.available2013-06-12T10:14:26Z
dc.date.issued2009
dc.description.abstractSolving 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.fr_FR
dc.identifier.urihttp://dl.cerist.dz/handle/CERIST/192
dc.publisherIndersciencefr_FR
dc.relation.ispartofInternational Journal of Grid and Utility Computing
dc.relation.ispartofseriesInternational Journal of Grid and Utility Computing;01(02)
dc.relation.pages159-168fr_FR
dc.rights.holderInderscience Enterprises Ltdfr_FR
dc.structureCalcul Pervasif et Mobilefr_FR
dc.subjectcombinatorial optimisation; permutation flow-shop problem; parallel branch and bound; peer-to-peer computing; ProActive.fr_FR
dc.titleP2P design and implementation of a parallel branch and bound algorithm for gridsfr_FR
dc.typeArticle
Files
Collections
International Journal Papers