Article ID: | iaor1999115 |
Country: | United States |
Volume: | 9 |
Issue: | 4 |
Start Page Number: | 319 |
End Page Number: | 334 |
Publication Date: | Sep 1997 |
Journal: | INFORMS Journal On Computing |
Authors: | Scholl Armin, Klein Robert |
Keywords: | optimization |
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 (SALOME) 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 SALOME outperforms the most effective existing procedures for solving this problem.