Lagrangian heuristics for the capacitated multi-item lot-sizing problem with backordering

This paper presents two algorithms for solving a network-based formulation of the capacitated multi-item lot-sizing problem with backordering. We employ Lagrangian decomposition and Lagrangian relaxation techniques which exploit the underlying network structure of the problem. In both approaches, we exploit a transportation subproblem which guarantees a primal feasible solution at every iteration of the procedure. Further, we use a primal partitioning scheme to produce additional primal feasible solutions. Valid lower bounds are obtained at each iteration of the algorithms, thereby providing a readily available ex post measure of the quality of the primal solutions. Computational analysis shows that both algorithms are quite effective, particularly when item setup and unit backorder costs are high. We also provide a means of evaluating the potential impact of permitting backorders under various problem characteristics.