Hierarchical Branch and Bound Algorithm for Computational Grids
| dc.citation.epage | 1176 | |
| dc.citation.issue | 8 | |
| dc.citation.spage | 1168 | |
| dc.citation.volume | 28 | |
| dc.contributor.author | Bendjoudi, Ahcène | |
| dc.contributor.author | Melab, Nouredine | |
| dc.contributor.author | Talbi, El-Ghazali | |
| dc.date.accessioned | 2013-06-12T10:13:59Z | |
| dc.date.available | 2013-06-12T10:13:59Z | |
| dc.date.issued | 2012 | |
| dc.description.abstract | Branch and Bound (B&B) algorithms are efficiently used for exact resolution of combinatorial optimization problems (COPs). They are easy to parallelize using the Master/Worker paradigm (MW) but limited in scalability when solving large instances of COPs on large scale environments such as Grids. Indeed, the master process rapidly becomes a bottleneck. In this paper, we propose a new approach H-B&B for parallel B&B based on a hierarchical MW paradigm in order to deal with the scalability issue of the traditional MW-based B&B. The hierarchy is built dynamically and evolves over time according to the dynamic acquisition of computing nodes. The inner nodes of the hierarchy (masters) perform branching operations to generate sub-trees and the leaves (workers) perform a complete exploration of these sub-trees. Therefore, in addition to the parallel exploration of sub-trees, a parallel branching is adopted. H-B&B is applied to the Flow-Shop scheduling problem.Unlike most existing grid-based B&B algorithms, H-B&B has been experimented on a real computational grid i.e. Grid’5000. The results demonstrate the scalability and efficiency of H-B&B. | fr_FR |
| dc.identifier.uri | http://dl.cerist.dz/handle/CERIST/189 | |
| dc.publisher | Elsevier | fr_FR |
| dc.relation.ispartof | Future Generation Computer System (FGCS) | |
| dc.relation.ispartofseries | Future Generation Computer System (FGCS);28(8) | |
| dc.relation.pages | 1168-1176 | fr_FR |
| dc.structure | Calcul Pervasif et Mobile | fr_FR |
| dc.subject | Parallel Branch and Bound; Master/Worker; Hierarchical Master/Worker; Grid Computing; Large scale Ex- periments; | fr_FR |
| dc.title | Hierarchical Branch and Bound Algorithm for Computational Grids | fr_FR |
| dc.type | Article |