Balancing U-shaped assembly lines with collaborative robots: constraint programming approaches and Benders’ decomposition algorithms
针对协作机器人在U型装配线中的平衡问题，提出了基于约束规划和组合Benders分解的两种精确方法，计算实验表明新方法优于现有最优方法，其中约束规划在1500个测试实例中求解出574个最优解。
Collaborative robots are progressively employed to support human workers in assembly tasks or independently assigned to one station to complete assembly tasks in U-shaped assembly lines. This study develops two exact methods, based on constraint programming (CP) model and Combinatorial Benders’ decomposition algorithm (CBDA), to tackle the U-shaped assembly line balancing problem with collaborative robots. The CBDA is based on distinct decomposition strategies that address the master problem and the subproblem, formulated by a mixed integer linear programming (MILP) model and a CP model, which is designed to obtain a real objective value and generate cuts that refine the master problem. Additionally, MILP-based and CP-based local search techniques are proposed to improve the algorithm's performance. The computational study demonstrates that both the proposed methods, namely CP and CBDA, outperform the current state-of-the-art methods (the MILP model and simulated annealing algorithm). Furthermore, the CP outperforms the CBDA in terms of the number of optimal solutions, achieving the optimal solutions for 574 out of 1500 test instances, and might be regarded as the new state-of-the-art methodology.