Stochastic assembly line balancing: General bounds and reliability-based branch-and-bound algorithm

We analyze the assembly line balancing problem with stochastic task times. Tasks have to be assigned to a minimum number of stations with a constraint on the line reliability, which is the probability of finishing a work piece completely. A sampling approach is developed that ensures the line reliability. We prove that any lower bound on the number of stations for the related deterministic problem can be transformed into a lower bound for this sampling formulation. This general transformation can be applied to any bound that has already been developed or to any potential new bound. Those bounds can be applied to any MIP model, optimization algorithm or heuristic procedure based on a sampling formulation. We exemplify the usefulness of these bounds in a reliability-based branch-and-bound (RB&B) algorithm that explicitly considers the dependence among all stations due to the constrained line reliability. A partial assignment of tasks to stations has to consider already constructed stations and potential further assignments to other stations. Hence, a feasible assignment of tasks to this station may allow for exceeding the cycle time with a certain probability but has to consider the overall line reliability with respect to the remaining stations. Effective fathoming strategies based on the new transformed lower bounds or based on a direct consideration of the line reliability are proposed. A numerical study shows that the transformed lower bounds are tight and that they substantially reduce the required computation times of the RB&B algorithm and of the solver CPLEX.