A Benders Decomposition Approach for the Optimization of Flow Lines with Stochastic Processing Times

The allocation of buffer space in flow lines with stochastic processing times is an important decision, as buffers influence the performance of these lines. The objective of this problem is to minimize the overall number of buffer spaces achieving at least one given goal production rate. We solve this problem with a mixed-integer programming (MIP) approach by sampling the effective processing times. To obtain robust results, large sample sizes are required. These incur large models and long computation times using standard solvers. One approach to reduce the computation time is Benders Decomposition. Benders Decomposition divides the original MIP into a master problem and a subproblem. These two problems are solved iteratively by exchanging information via cuts. The cuts are derived from the subproblem and are added to the master problem such that optimality is proven at the termination. This paper presents different approaches for initial bounds and the cuts for the Buffer Allocation Problem (BAP). Numerical experiments are carried out to evaluate the performance of the proposed approaches.