R-SALSA: A branch, bound, and remember algorithm for the workload smoothing problem on simple assembly lines
针对给定节拍和工位数的简单装配线平衡问题，提出一种改进的分支定界与记忆算法R-SALSA，通过支持者与阻止者等新概念增强分支定界效率，在多达1000个任务的基准数据集上优于现有精确算法。
We consider a simple assembly line balancing problem with given cycle time and number of stations. A quadratic objective function based on a so-called smoothness index SX levels the workloads of the stations. For this problem, called SALBP-SX, only a few solution procedures have been proposed in literature so far. In this paper, we extend and improve the branch-and-bound procedure SALSA ( S imple A ssembly L ine S moothing A lgorithm) of Walter et al. (2021) to a bidirectional branch, bound, and remember algorithm called R-SALSA ( R for remember). Like SALSA, it is based on a dynamic programming scheme which pre-determines potential workloads of the stations and provides a construction plan for possible station loads. This scheme is extended by the new concept of supporters and preventers which significantly enhances branching, bounding, and logical tests. Furthermore, a tailored heuristic that searches for improved initial solutions, a bidirectional branching scheme and additional dominance rules are integrated. In extensive computational experiments, we find out that our new procedure clearly outperforms all former exact solution procedures on benchmark data sets with up to 1000 tasks.