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

Johannes Diefenbach and Raik Stolletz

European Journal of Operational Research, 2022, vol. 302, issue 2, 589-605

Abstract: 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.

Keywords: Stochastic programming; Assembly line balancing; Lower bounds; Branch-and-bound algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722000339
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:302:y:2022:i:2:p:589-605

DOI: 10.1016/j.ejor.2022.01.015

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().