Accelerated Benders Decomposition Algorithm for Sequence-Dependent Cost-Oriented Assembly Line Balancing Problem

The Sequence-dependent Cost-oriented Assembly Line Balancing (SDCALB) problem is a challenging optimization problem that belongs to the NP-hard class. To solve this problem, a position based mathematical model is formulated and then the Pure Bender's Decomposition (PBD) algorithm is proposed. Two acceleration methods are also suggested to improve the convergence rate and reduce the solution time of the PBD algorithm: combinatorial Bender's cuts (CBC), and a heuristic algorithm that generates feasible solutions and optimality cuts if the subproblem is infeasible. The efficacy of these methods is evaluated by incorporating them separately and collectively with the PBD algorithm and analyzing their performance. The results show that both CBC and the heuristic algorithm methods improve the convergence rate and solution time. Moreover, the accelerated Bender's algorithm, outperforms both PBD and optimization solvers such as CPLEX and GUROBI