P2P B&B and GA for the flow-shop scheduling problem

Abstract : Solving exactly Combinatorial Optimization Problems (COPs) using a Branch-and-Bound algorithm (B&B) requires a huge amount of computational resources. The efficiency of such algorithm can be improved by its hybridization with meta-heuristics such as Genetic Algorithms (GA) which proved their effectiveness, since they generate acceptable solutions in a reasonable time. Moreover, distributing at large scale the computation, using for instance Peer-to-Peer (P2P) Computing, provides an efficient way to reach high computing performance. In this chapter, we propose ParallelBB and ParallelGA, which are P2P-based parallelization of the B&B and GA algorithms for the computational Grid. The two algorithms have been implemented using the ProActive distributed object Grid middleware. The algorithms have been applied to a mono-criterion permutation flow-shop scheduling problem and promisingly experimented on the Grid5000 computational Grid.
Type de document :
Chapitre d'ouvrage
Springer. Metaheuristics for Scheduling in Distributed Computing Environments, 146, Springer, pp.301-321, 2008, Studies in Computational Intelligence, 〈10.1007/978-3-540-69277-5_11〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00690360
Contributeur : Ist Rennes <>
Soumis le : lundi 23 avril 2012 - 11:39:26
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Lien texte intégral

Identifiants

Citation

Ahcène Bendjoudi, Samir Guerdah, Madjid Mansoura, Nouredine Melab, El-Ghazali Talbi. P2P B&B and GA for the flow-shop scheduling problem. Springer. Metaheuristics for Scheduling in Distributed Computing Environments, 146, Springer, pp.301-321, 2008, Studies in Computational Intelligence, 〈10.1007/978-3-540-69277-5_11〉. 〈hal-00690360〉

Partager

Métriques

Consultations de la notice

359