A Lagrangian heuristic for capacitated single item lot sizing problems

This paper presents a new Lagrangian heuristic to solve the general capacitated single item lot sizing problem (CSILSP) where the total costs of production, setup, and inventory are to be minimized. We introduce a pre‐smoothing procedure to transform the problem into a CSILSP with non‐customer specific time windows and relax constraints that are specific to the CSILSP. The resulting uncapacitated single item problems with non‐customer specific production time windows can be solved in polynomial time. We also analyze the performance of the Lagrangian heuristic for solving the CSILSP with non‐customer specific time windows. Finally, the heuristic is adapted to the customer specific case. The introduction of pre‐smoothing and the relaxation of CSILSP‐specific constraints help to decrease the gap between lower bounds and upper bounds from 26.22 to 1.39 %, on average. The heuristic can be used to solve aggregate production planning problems, or can be integrated into a general procedure to solve more complex lot sizing problems.