Effective Heuristics for Solving the Multi-Item Uncapacitated Lot-Sizing Problem Under Near-Minimal Storage Capacities

In inventory management, storage capacity constraints complicate multi-item lot-sizing decisions. As the number of items increases, deciding how much of each item to order without exceeding capacity becomes more difficult. Dynamic programming works efficiently for a single item, but when capacity constraints are nearly minimal across multiple items, novel heuristics are required. However, previous heuristics have mainly focused on inventory bound constraints. Therefore, this paper introduces push and pull heuristics to solve the multi-item uncapacitated lot-sizing problem under near-minimal capacities. First, a dynamic programming approach based on a network flow model was used to generate the initial replenishment plan for the single-item lot-sizing problem. Next, under storage capacity constraints, the push operation moved the selected replenishment quantities from the current period to subsequent periods to meet all demand requirements. Finally, the pull operation shifted the selected replenishment quantities from the current period into earlier periods, ensuring that all demand requirements were satisfied. The results of the random experiment showed that the proposed heuristic generated solutions whose performance compared well with the optimal solution. This heuristic effectively solves all randomly generated instances representing worst-case conditions, ensuring robust operation under near-minimal storage. For large-scale problems under near-minimal storage capacity constraints, the proposed heuristic achieved only small optimality gaps while requiring less running time. However, small- and medium-scale problems can be solved optimally by a Mixed-Integer Programming (MIP) solver with minimal running time.