An Improved Combinatorial Benders Decomposition Algorithm for the Human-Robot Collaborative Assembly Line Balancing Problem

As an emerging technology, human-robot collaboration (HRC) has been implemented to enhance the performance of assembly lines and improve the safety of human workers. By integrating the advantages of human workers and collaborative robots (cobots), HRC enables production systems to process tasks consecutively, concurrently, or collaboratively. However, the introduction of cobots also makes the corresponding human-robot collaborative assembly line balancing problem more complex and difficult to solve. To solve this problem, we first propose an enhanced mixed integer program (EMIP) with various enhancement techniques and tighter bounds, and then, we develop an improved combinatorial Benders decomposition algorithm (Algorithm ICBD) with new local search strategies, Benders cuts, and acceleration procedures. To verify the effectiveness of our proposed model and algorithms, we conduct extensive computational experiments, and the results show that our proposed EMIP model is significantly better than the existing mixed integer program model; the percentages of instances that can obtain feasible and optimal solutions are increased from 82.42% to 100% and from 29.17% to 43.5%, respectively, whereas the average gap is decreased from 19.81% to 5.64%. In addition, our proposed Algorithm ICBD can get 100% of feasible solutions and 65.92% of optimal solutions for all of the test instances, and the average gap is only 1.49%. Moreover, compared with existing Benders decomposition methods for this problem, our approach yields comparatively better solutions in notably shorter average computational time when run in the same computational environment.