期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 302, 期 2, 页码 589-605出版社
ELSEVIER
DOI: 10.1016/j.ejor.2022.01.015
关键词
Stochastic programming; Assembly line balancing; Lower bounds; Branch-and-bound algorithm
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.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据