.png){kind=icon}
返回
Hierarchical branch and bound algorithm for computational grids
.png){kind=icon}
PRE
AI
DOI：10.1016/j.future.2012.03.001.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 computational 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 (Grid'5000). The results demonstrate the scalability and efficiency of H-B&B. (C) 2012 Elsevier B.V. All rights reserved.
Keyword:
Parallel branch and bound
Master/worker
Hierarchical master/worker
Grid computing
Large scale experiments
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
F
IF:
6.1
论文数:
6.8K
被引数:
2.3W
机构
引用论文
Are mountains refuges for farmland bird species? A case study in the northern French Alps.png)
Bird Study
Bird StudyIF0
PREAI
分享收藏A new step toward load balancing based on competency rank and transitional phases in Grid networks
PREAI
分享收藏
Easing the Formalization of Clinical Guidelines with a User-tailored, Extensible Agile Model Driven Development (AMDD)通过用户定制、可扩展的敏捷模型驱动开发（AMDD）简化临床指南的规范化
OAAI
OAAI分享收藏
查看更多内容