Enhanced branch-bound-remember and iterative beam search algorithms for type II assembly line balancing problem

Abstract

This study presents an enhanced iterative branch, bound and remember (IBBRe) algorithm as an exact method and an enhanced iterative beam search (IBSe) approach as a heuristic method to tackle the type II assembly line balancing problem. The proposed IBBRe is enhanced by utilizing additional lower bounds, a new search strategy and a new sequence of applying the lower bounds and dominance rules. The pro- posed IBSe is also enhanced by utilizing additional lower bounds, more dominance rules and a new sta- tion load selection criterion. The computational study demonstrates that both the proposed methods, namely IBBRe and IBSe, outperform the current state-of-the-art method (iterative beam search), and they update the upper bounds for seven cases which have been open for over two decades. Furthermore, IBBRe outperforms IBSe by achieving the best-known solutions in 301 out of the 302 test cases and might be regarded as the new state-of-the-art methodology.