A Branch-Bound-and-Remember Search Framework for U-Shaped Disassembly Line Balancing Problems

The U-shaped Disassembly Line Balancing Problem (UDLBP) is a challenging combinatorial optimization problem for which efficient solution approaches remain limited. This study proposes an efficient branch-bound-and-remember (BBR) algorithm that integrates a memory-based mechanism and U-shaped dominance rules to effectively reduce the search space. Specifically, a new branching method, an additional lower bounding method, and new dominance rules are developed to suit the UDLBP, and different search strategies are developed and explored. Extensive computational experiments are conducted on a comprehensive set of benchmark instances to evaluate the performance of the proposed approach. The results demonstrate that the proposed BBR algorithm can consistently identify the best-known solutions for the evaluated benchmark instances. Compared with constraint programming, mixed-integer linear programming, and several state-of-the-art metaheuristic algorithms, the proposed approach achieves competitive solution quality and computational efficiency, consistently matching the best-known solutions with an average recorded CPU time of 0.0199 s under the 500 s computational setting. These findings indicate that the proposed algorithm provides an efficient optimization framework for solving UDLBP, achieving high-quality solutions with substantially low computational cost.