Lagrangean 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. The authors employ Lagrangean decomposition and Lagrangean relaxation techniques which exploit the underlying network structure of the problem. In both approaches, they exploit a transportation subproblem which guarantees a primal feasible solution at every iteration of the procedure. Further, the authors 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. The authors also provide a means of evaluating the potential impact of permitting backorders under various problem characteristics.