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

This study aimed to develop an effective heuristic for solving multi-item uncapacitated lot-sizing problems with near-minimal storage capacities. For the initial replenished plan, applying network flow based on a dynamic programming approach was used to solve the single-item lot-sizing problem, while the push operation was used to move the replenished quantities of some items from the existing period to consecutive periods under storage capacity constraints for meeting all demands. To improve the replenished plan, the pull operation was used to return some replenished quantities from the existing period to the previous one and meet all demands together. The results of the random experiment example showed that the proposed heuristic generated differences of 1.20%, 0.63%, and 0.54% between its solutions and the optimal solution with additional storage capacity parameters of 5%, 10% and 20%, respectively. This heuristic effectively solves all random instances of the worst-case conditions for robust operation with the near-minimal storage capacities. For large-scale problems, the proposed heuristic performed well on small gaps between the approximate and optimal solution using less running time with near-minimal storage capacity. Meanwhile, the MIP solver still enhances the running of small and medium-scale problems with near-minimal storage capacity in the shortest run time.