A comparative study of exact methods for the simple assembly line balancing problem

Abstract

Exact methods have shown advanced and promising performance in solving the simple assembly line balancing problem, known as NP-hard. This research investigates the impact of various structural parameters on the performance of exact methods, includingbranching methods,search direction,method to achieve upper bounds,utilized lower bounds,utilized dominance rulesandsearch strategy. In accordance with the structural parameter evaluation,utilized dominance rulesandsearch strategyhave shown the most important effect on the exact methods' performance. This research also improves and re-implements three well-known exact methods [i.e., SALOME, bounded dynamic programming (BDP) heuristic and branch, bound and remember (BBR) algorithm] using effective parameters. Computational study demonstrates that the utilization of high-performance structural parameters enhances the performance of exact methods by a significant margin. The re-implemented BBR method with proper parameters shows clear superiority over all the published exact methods and might be regarded as the state-of-the-art exact methodology.