๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An efficient load balancing strategy for grid-based branch and bound algorithm

โœ Scribed by M. Mezmaz; N. Melab; E.-G. Talbi

Publisher
Elsevier Science
Year
2007
Tongue
English
Weight
286 KB
Volume
33
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

โœฆ Synopsis

The most popular parallelization approach of the branch and bound algorithm consists in building and exploring in parallel the search tree representing the problem being tackled. The deployment of such parallel model on a grid rises the crucial issue of dynamic load balancing. The major question is how to efficiently distribute the nodes of an irregular search tree among a large set of heterogeneous and volatile processors. In this paper, we propose a new dynamic load balancing approach for the parallel branch and bound algorithm on the computational grid. The approach is based on a particular numbering of the tree nodes allowing a very simple description of the work units distributed during the exploration. Such description optimizes the communications involved by the huge amount of load balancing operations. The approach has been applied to one instance of the bi-objective flow-shop scheduling problem. The application has been experimented on a computational pool of more than 1000 processors belonging to seven Nation-wide clusters. The optimal solution has been generated within almost 6 days with a parallel efficiency of 98%.

๐Ÿ“œ SIMILAR VOLUMES

An efficient branch-and-bound algorithm
An efficient branch-and-bound algorithm for the two-machine bicriteria flowshop scheduling problem
โœ Wei-Chang Yeh ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Society of Manufacturing Engineers ๐ŸŒ English โš– 826 KB

In this study, the two-machine bicriteria flowshop scheduling problem is addressed. The objective is to minimize a weighted sum of total flowtime and makespan. Different branch-and-bound algorithms have already appeared in the literature for this problem. In this study, a more efficient branch-and-b

An efficient branch-and-bound algorithm
An efficient branch-and-bound algorithm for the two-machine bicriteria flowshop scheduling problem : Wei-Chang Yeh, v20, n2, 2001, pp113โ€“123
๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Society of Manufacturing Engineers ๐ŸŒ English โš– 296 KB

and keyword index optimization, the infrastructure is capable of finding robust error recovery algorithms. It is expected that this approach will require less time for the generation of robust error recovery logic.