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

Panfei Li and Chongxing Ji

PLOS ONE, 2025, vol. 20, issue 10, 1-32

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.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0333263 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 33263&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0333263

DOI: 10.1371/journal.pone.0333263

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().