Enhanced beam search heuristic for U-shaped assembly line balancing problems. Issue 4 (3rd April 2021)

• Record Type: Journal Article
• Authors: Li, Zixiang; Janardhanan, Mukund Nilakantan; Rahman, Humyun Fuad
• Is Part Of: Engineering optimization. Volume 53:Issue 4(2021)
• Page Start: 594
• Page End: 608
• Publication Date: 2021-04-03
• Subjects: Combinatorial optimization -- assembly line balancing -- U-shaped assembly line -- heuristics -- beam search; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2020.1741569
• Languages: English
• ISSNs: 0305-215X

Abstract

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.