SALOME: A Bidirectional Branch-and-Bound Procedure for Assembly Line Balancing
SALOME: A Bidirectional Branch-and-Bound Procedure for Assembly Line Balancing
复制标题
DOI：
10.1287/ijoc.9.4.319
复制
发表时间：
1997-11
期刊：
影响因子：
--
通讯作者：
A. Scholl;Robert Klein
中科院分区：
文献类型：
--
作者：
A. Scholl;Robert Klein
在这篇文章中，我们报告了著名的简单装配线平衡问题类型1的新结果。对于这个NP难问题，在过去的四十年里，已经提出了大量的精确算法和启发式算法。最近的研究导致了有效的分支定界过程。在分析它们各自优势的基础上，提出了一种新的算法（S alome）。它的主要特点是一种新的分支策略（局部下界方法）和一种双向分支规则。此外，新的边界和优势规则。计算实验的基础上，以前的数据集，以及一个新的，更具挑战性的，表明S alome优于最有效的现有程序来解决这个问题。
In this article, we report on new results for the well-known Simple Assembly Line Balancing Problem Type 1. For this NP-hard problem, a large number of exact and heuristic algorithms have been proposed in the last four decades. Recent research has led to efficient branch-and-bound procedures. Based on an analysis of their specific strengths, a new algorithm (S alome ) is developed. Its main characteristic is a new branching strategy (local lower-bound method) and a bidirectional branching rule. Furthermore, new bounding and dominance rules are included. Computational experiments on the basis of former data sets, as well as a new, more challenging one, show that S alome outperforms the most effective existing procedures for solving this problem.