.png){kind=icon}
返回
A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2020.01.039.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this work we propose an efficient branch-and-bound (B&B) algorithm for the permutation flow-shop problem (PFSP) with makespan objective. We present a new node decomposition scheme that combines dynamic branching and lower bound refinement strategies in a computationally efficient way. To alleviate the computational burden of the two-machine bound used in the refinement stage, we propose an online learning-inspired mechanism to predict promising couples of bottleneck machines. The algorithm offers multiple choices for branching and bounding operators and can explore the search tree either sequentially or in parallel on multi-core CPUs. In order to empirically determine the most efficient combination of these components, a series of computational experiments with 600 benchmark instances is performed. A main insight is that the problem size, as well as interactions between branching and bounding operators substantially modify the trade-off between the computational requirements of a lower bound and the achieved tree size reduction. Moreover, we demonstrate that parallel tree search is a key ingredient for the resolution of large problem instances, as strong super-linear speedups can be observed. An overall evaluation using two well-known benchmarks indicates that the proposed approach is superior to previously published B&B algorithms. For the first benchmark we report the exact resolution - within less than 20 minutes - of two instances defined by 500 jobs and 20 machines that remained open for more than 25 years, and for the second a total of 89 improved best-known upper bounds, including proofs of optimality for 74 of them. (C) 2020 Elsevier B.V. All rights reserved.
Keyword:
Branch-and-Bound
Flowshop
Makespan
Parallel computing
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
Parallel Branch-and-Bound in multi-core multi-CPU multi-GPU heterogeneous environments多核多CPU多GPU异构环境中的并行分支定界OAAI
OAAI分享收藏A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem置换流水车间调度问题的模糊推理分支定界算法
PREAI
分享收藏Ancient DNA reveals traces of Iberian Neolithic and Bronze Age lineages in modern Iberian horsesOAAI
OAAI分享收藏
查看更多内容