The Multi-Item Capacitated Lot Size Problem: Error Bounds of Manne's Formulations
讨论多物品批量问题的近似方案，基于线性规划最优解构造近似解，给出误差界和不可行性分析，并扩展到可变容量问题。
We discuss an approximation scheme for the multi-item lot size problem. It is based on an optimal basic solution of a linear programming problem derived from the original problem. The approximate solution is obtained by taking a linear convex combination of the optimal solution of the linear programming problem. We express error bounds of the approximation as a function of some parameters that can be easily estimated in practice. When set-up times are positive, the approximation may result in an infeasible solution. We take the same approach to show that the infeasibility of the approximation is small. The analysis is extended to a variable capacity problem with overtime. As an auxiliary result, we provide a bound on the duality gap of the Lagrangian dual problem.