Publication | Closed Access
SALOME: A Bidirectional Branch-and-Bound Procedure for Assembly Line Balancing
199
Citations
0
References
1997
Year
Mathematical ProgrammingLoad Balancing (Computing)Branch-and-bound AlgorithmEngineeringComputer ArchitectureDiscrete OptimizationOperations ResearchSystems EngineeringParallel ComputingCombinatorial OptimizationInstruction-level ParallelismCombinatorial ProblemComputer EngineeringDominance RulesNp-hard ProblemNew AlgorithmAssemblyAssembly LineParallel ProgrammingBranch And BoundAssembly Line Balancing
The Simple Assembly Line Balancing Problem Type 1 is NP‑hard, and over the past four decades many exact and heuristic algorithms have been proposed, with recent work yielding efficient branch‑and‑bound procedures. The article presents new results for the Simple Assembly Line Balancing Problem Type 1. The authors develop Salome, a branch‑and‑bound algorithm featuring a local lower‑bound branching strategy, bidirectional branching, and additional bounding and dominance rules. Experiments on existing and a new challenging dataset demonstrate that Salome outperforms the most effective existing procedures for solving the problem.
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.