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. (C) 2022 Elsevier B.V. All rights reserved.

Automated summary

This study analyzes the assembly line balancing problem with stochastic task times. A sampling approach is developed to ensure line reliability. The research proves that lower bounds for the related deterministic problem can be transformed into lower bounds for the sampling formulation. The study exemplifies the use of these bounds in a reliability-based branch-and-bound algorithm and proposes effective fathoming strategies based on the transformed lower bounds or direct consideration of line reliability.