Application of enhanced benders decomposition algorithm in circular assembly line balancing problem with task splitting

Abstract

The advent of the assembly line marked a significant technological innovation in the manufacturing industry, substantially enhancing production efficiency. Today, this production system is extensively adopted by numerous manufacturing enterprises. This paper introduces the Circular Assembly Line Balancing Problem with Task-Splitting (CALBP-TS), a novel NP-hard optimization challenge characterized by closed-loop topology, station revisitation, fixed-position machines, and collaborative task execution. To address its high-dimensional complexity, we propose an Enhanced Benders Decomposition (EBD) framework that decomposes CALBP-TS into a workload-balancing master problem (MP) addressing worker-process assignment and task-splitting using a rigorous linearization theorem and a feasibility-checking subproblem (SP) handling spatio-temporal constraints via dummy process encoding. Key algorithmic accelerators comprise a Heuristic Infeasibility Proof (HIP) for rapid solution screening and Enhanced Benders Cuts (EBC) derived from infeasibility analysis, both integrated with integrated with Local Branching. Validated on 60 real-world instances from Huawei, EBD achieves average runtime reductions of 97.8%, 69.2%, and 48.4% compared to MILP, GA + LP, and Greedy+LP baselines, respectively, while improving solution quality by up to 41.3%. Ablation studies confirm that HIP and EBC collectively enhance computational efficiency by 13.7%. Our methodology facilitates optimal resource utilization in space-constrained circular production systems.