An Efficient Computational Method for Non-Stationary (R,S) Inventory Policy with Service Level Constraints

This paper provides an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman (2004) for calculating the parameters of an (R,S) policy in a finite horizon with non-stationary stochastic demand and service level constraints. Given the replenish-ment periods, we characterize the optimal order-up-to levels for the MIP model and use it to guide the development of a relaxed MIP model, which can be solved in polynomial time. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and yields an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, this solution can be used as a tight lower bound, and also (iii) this infeasible solution can be modified easily to obtain a feasible solution, which is an upper bound for the optimal solution. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a sim-ple branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time. Key words: relaxation, lot sizing, stochastic non-stationary demand, mixed integer programming, service level, replenishment cycle polic