A new algorithm for computing optimal (s, S) policies in a stochastic single item/location inventory system

It has been shown that a class of (s, S) policies is optimal to the single item/location inventory system. However, the computational complexity of finding the optimal (s, S) policy has restricted applications of this inventory system. This paper proposes a new algorithm to search for the optimal pair of s and S. We introduce a dummy cost factor and an auxiliary function into our algorithm. The algorithm searches for the optimal dummy cost through continuously evaluating the auxiliary function. It differs from the approach of Zheng and Federgruen in several aspects and has certain advantages. First, as it revises the dummy cost based on the sign of the auxiliary function, the primary goal of the search is not to compute the optimal s and S during each iteration. Second, by identifying the non-prospective sets of S, the algorithm further reduces the search effort. Numerical tests show that on the average, the proposed algorithm saves more than 30% of evaluation effort compared with Zheng and Federgruen's method.