Branch and bound algorithm with new lower bounding methods for U-shaped assembly line balancing problem

U-shaped assembly lines draw increasing attentions from researchers and engineers due to higher flexibility and efficiency. This research employs several new lower bounding methods to enhance the performance of the branch, bound and remember algorithm (BBR) in solving U-shaped assembly line balancing problem (UALBP), which is the current state-of-the-art methodology. These newly applied lower bounding methods include the well-known LB6, LB7 and a set of bounds derived from the dual feasible function. The sequence of utilizing these lower bounding methods and dominance rules is also investigated to achieve the proper balance between speed and solution quality. Computational results show that these new lower bounding methods achieve tighter lower bounds with the cost of increased computation time. Comparative study demonstrates the superiority of the new BBR method with these new lower bounding methods, and this new BBR method is also capable of achieving 14 new optimal solutions and some new upper bounds

کلیدواژه ها:

Assembly line balancing ، U-shaped assembly line ، branch and bound ، Lower bounds