A new heuristic method for capacitated multi-level lot sizing problem with backlogging

In this paper we consider the capacitated multilevel lot sizing problem with the consideration of backlogging. Demand for each item is deterministic in each level and in each period with a given horizon of T periods. The objective is to minimize the total cost that includes setup cost, inventory holding cost, and backlogging cost. For each period, the demand must be satisfied without exceeding capacities or else expensive backlogging will be required. In order to generate feasible high quality solutions quickly, we propose a new heuristic algorithm. The proposed approach can combine the domain knowledge from the different strategies of a relax-and-fix method effectively. Extensive computational tests show that our proposed heuristic approach provides good solution results based on benchmark problems.