Buffer allocation problem in production flow lines: A new Benders-decomposition-based exact solution approach
针对长生产流水线缓冲区分配问题，提出一种混合整数线性规划模型和Benders分解算法，利用可逆性和单调性生成多个Benders割，显著提升计算效率，为实际生产提供精确求解方法。
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.