On the performance of task-oriented branch-and-bound algorithms for workload smoothing in simple assembly line balancing
系统分析了两种精确的任务导向分支定界算法在简单装配线工作负载平滑问题中的有效性，并与数学规划求解器和组合算法进行了实验比较，同时提出了理论改进。
Smoothing the workloads among the stations of an already installed assembly line is one of the major objectives in assembly line (re-)balancing. In order to find a feasible task-station assignment that distributes the total workload as equal as possible, two exact task-oriented branch-and-bound algorithms have recently been proposed. In this paper, we systematically analyse their effectiveness in solving the workload smoothing problem on simple assembly lines. In our experiments, we also examine the performance of a state-of-the-art mathematical programming solver and a ‘combined’ exact branch-and-bound procedure that integrates components of the two algorithms from the literature. In terms of theory, we show the equivalence of two recently developed local lower bounding arguments and suggest a slight improvement of the bound. We also propose an enhanced feasibility test.