Enhanced beam search heuristic for U-shaped assembly line balancing problems

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.

KEYWORDS:

• Combinatorial optimization
• assembly line balancing
• U-shaped assembly line
• heuristics
• beam search

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This project is partially supported by National Natural Science Foundation of China [grant number 61803287] and China Postdoctoral Science Foundation [grant number 2018M642928].