An efficient branch and bound algorithm for smoothing the workloads on simple assembly lines

Abstract : In this study, we develop a branch and bound solution algorithm to solve the workload smoothing problem. Our algorithm incorporates new formulas for dynamically computing a lower bound on the optimal value of the objective function and for determining the earliest workstations for tasks. It also uses a fast heuristic for computing a good initial upper bound. A comprehensive experimental analysis is conducted in this study. The analysis demonstrates the outstanding performance of the algorithm and its efficiency in solving medium-sized workload smoothing problems.