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. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This research was supported by the National Natural Science Foundation Council of China [Grants 72401214, 92167206, 7221101377, 72471169, and 72231005], the Ministry of Education of China [Grant 24YJC630078], and Computation and Analytics of Complex Management Systems (Tianjin University). This research was also supported by the Tianjin Natural Science Foundation Project [Grant 23JCQNJC01900] and the Tianjin Philosophy and Social Science Planning Project [Grant TJGL21-016]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0279 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0279 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .