Buffer Allocation Problem in production flow lines: a new Benders-decomposition-based exact solution approach

The Buffer Allocation Problem (BAP) in production flow lines is very relevant from a practical point of view and very challenging from a scientific perspective. For this reason, it has drawn great attention both in industry and in the academic community. However, despite the problem’s relevance, no exact method is available in the literature to solve it when long production lines are being considered, i.e., in practical settings. This work proposes a new Mixed-Integer Linear Programming (MILP) formulation for exact solution of sample-based BAP. Due to the huge number of variables and constraints in the model, an algorithm based on Benders decomposition is proposed to increase the computational efficiency. The algorithm iterates between a simulation module that generates the Benders cuts and an optimization module that involves the solution of an updated MILP model. Multiple Benders cuts after each simulation run are generated by exploiting the structural properties of reversibility and monotonicity of flow line throughput. The new MILP formulation is tighter than the state-of-the-art model from a theoretical point of view, and order of magnitude of computation time saving is also observed in the numerical results.