Solving the Dynamic Lot-Sizing Problem with Safety Stocks and Limited Inventories based on New Properties〔含 質疑応答〕 Solving the Dynamic Lot-Sizing Problem with Safety Stocks and Limited Inventories based on New Properties

The dynamic lot-sizing problem with safety stocks and limited inventories is often met in practice. The goal of the problem aims at determining the relative frequency of setups satisfying the demands under restrictions of the safety stock and limited inventory over a planning horizon at minimum cost. In this paper a framework to solve this problem effectively is proposed, which consists of two procedures devised to deal with the safety stock and limited inventory due to new valid inequalities, and new properties to obtain optimal policies. Based on these properties a dynamic programming algorithm is introduced and then a priori is added to the branch-and-bound tree of the reduced shortest-path problem to obtain a tight reformulation. Our computational results suggest that our contributions represent significant progress in solving instances of this problem.