Accelerated Benders decomposition algorithm for the sequence-dependent cost-oriented assembly line balancing problem

Beykent A., Elmi A., Feizollahi M. J., Hamzadayı A.

Engineering Optimization, 2026 (SCI-Expanded, Scopus) identifier

  • Yayın Türü: Makale / Tam Makale
  • Basım Tarihi: 2026
  • Doi Numarası: 10.1080/0305215x.2026.2647968
  • Dergi Adı: Engineering Optimization
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Compendex, zbMATH
  • Anahtar Kelimeler: assembly line balancing problem, Benders decomposition algorithm, Combinatorial optimization, sequence-dependent set-up time
  • Van Yüzüncü Yıl Üniversitesi Adresli: Evet

Özet

The sequence-dependent cost-oriented assembly line balancing (SDCALB) problem is an NP-hard optimization problem. To solve this problem, a position-based mathematical model is formulated, and then the pure Benders decomposition (PBD) algorithm is proposed. Two acceleration methods are also suggested to improve the convergence rate and reduce solution time for the PBD algorithm: combinatorial Benders cuts (CBCs) and a heuristic algorithm that generates feasible solutions and optimality cuts when the subproblem is infeasible. The efficacy of these methods is evaluated by incorporating them separately and collectively with the PBD algorithm and analysing their performance. The results show that both CBCs and the heuristic algorithm methods improve the convergence rate and solution time. Moreover, the accelerated Benders algorithm demonstrates superior performance to commercial solvers and existing decomposition methods.