Enhanced beam search heuristic for U-shaped assembly line balancing problems
Zixiang Li, Mukund Nilakantan Janardhanan, Humyun Fuad Rahman
Abstract
U-shaped assembly lines have drawn increasing attention from the modern assembly line industry owing to their high flexibility. This work develops an enhanced beam search heuristic algorithm to solve types 1 and 2 U-shaped assembly line balancing problems (UALBP-1 and UALBP-2). The proposed beam search heuristic is enhanced by utilizing: (1) five lower bounds and four dominance rules to prune the dominated partial solutions; (2) a new station load selection criterion to select station load with a smaller lower bound, less idle time and fewer ‘easy’ tasks; and (3) a new method to extend partial solutions based on heuristic information to encourage full station load. Extensive numerical study is carried out to test and evaluate the performance of the proposed algorithm. Computational results demonstrate that the proposed method outperforms the state-of-the-art methods for both UALBP-1 and UALBP-2 by achieving 33 and 31 new optimal solutions for UALBP-1 and UALBP-2, respectively.