Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-12-01T02:57:31.609Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing optimal (s, S) policies in inventory models with continuous demands

Published online by Cambridge University Press:  01 July 2016

A. Federgruen  and
P. Zipkin
A. Federgruen
Affiliation:
Columbia University
P. Zipkin*
Affiliation:
Columbia University
*
∗Postal address: Graduate School of Business, Columbia University, Uris Hall, New York, NY 10027, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Special algorithms have been developed to compute an optimal (s, S) policy for an inventory model with discrete demand and under standard assumptions (stationary data, a well-behaved one-period cost function, full backlogging and the average cost criterion). We present here an iterative algorithm for continuous demand distributions which avoids any form of prior discretization. The method can be viewed as a modified form of policy iteration applied to a Markov decision process with continuous state space. For phase-type distributions, the calculations can be done in closed form.

Keywords

POLICY ITERATION
Type
Research Article
Information
Advances in Applied Probability , Volume 17 , Issue 2 , June 1985 , pp. 424 - 442
Copyright
Copyright © Applied Probability Trust 1985 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Archibald, B. (1976) (s, S) Policies under Continuous Review and Discrete Compound Poisson Demand Processes. Ph.D. Thesis, University of Waterloo, Waterloo, Ontario.Google Scholar
Archibald, B. and Silver, E. (1978) (s, S) policies under continuous review and discrete compound Poisson demands. Management Sci. 24, 899–908.CrossRefGoogle Scholar
Deleve, G., Federgruen, A. and Tijms, H. (1977a) A general Markov decision method, I: Model and techniques. Adv. Appl. Prob. 9, 297–315.Google Scholar
Deleve, G., Federgruen, A. and Tijms, H. (1977b) A general Markov decision method, II: Applications. Adv. Appl. Prob. 9, 316–336.CrossRefGoogle Scholar
Denardo, E. (1967) Contraction mappings in the theory underlying dynamic programming. SIAM Rev. 9, 169–177.CrossRefGoogle Scholar
Derman, C. (1966) Denumerable state markovian decision processes–average cost criterion. Ann. Math. Statist. 37, 1545–1553.CrossRefGoogle Scholar
Doshi, B. (1976) Continuous time control of Markov processes of an arbitrary state space, discounted rewards. Ann. Statist. 1, 1219–1235.Google Scholar
Doshi, B. (1981) Optimal switching among a finite number of Markov processes. J. Optimization Theory Appl. 35, 581–611.CrossRefGoogle Scholar
Ehrhardt, R. (1979) The power approximation for computing (s, S) inventory policies. Management Sci. 25, 777–786.CrossRefGoogle Scholar
Eppen, G. and Schrage, L. (1981) Centralised ordering policies in a multiwarehouse system with lead times and random demand. In Multilevel Production/Inventory Control Systems: Theory and Practice , ed. Schwarz, L.. North-Holland, Amsterdam.Google Scholar
Federgruen, A. and Tijms, H. (1978) The optimality equation in average and denumerable state semi-Markov decision problems, recurrency conditions and algorithms. J. Appl. Prob. 15, 356–373.CrossRefGoogle Scholar
Federgruen, A. and Zipkin, P. (1984a) Approximations of dynamic multilocation production and inventory problems. Management Sci. 30, 69–85.CrossRefGoogle Scholar
Federgruen, A. and Zipkin, P. (1984b) Computational issues in an infinite horizon, multiechelon inventory model. Operat. Res. 32, 818–835.CrossRefGoogle Scholar
Federgruen, A. and Zipkin, P. (1984C) An efficient algorithm for computing optimal (s, S) policies. Operat. Res. To appear.CrossRefGoogle Scholar
Federgruen, A. and Zipkin, P. (1984d) Allocation policies and cost approximations for multilocation inventory models. Naval Res. Log Quart. 31, 97–129.CrossRefGoogle Scholar
Fleming, W. (1963) Some Markovian optimisation problems. J. Math. Mech. 12, 131–140.Google Scholar
Freeland, J. and Porteus, E. (1980a) Evaluating the effectiveness of a new method for computing approximately optimal (s, S) inventory policies. Operat. Res. 28, 353–364.CrossRefGoogle Scholar
Freeland, J. and Porteus, E. (1980b) Easily computed inventory policies for periodic review systems: Shortage cost and service level models. Working Paper, Graduate School of Business, Stanford University, Stanford, CA.Google Scholar
Furukawa, N. (1972) Markovian decision processes with compact action spaces. Ann. Math. Statist. 43, 1612–1622.CrossRefGoogle Scholar
Hastings, N. (1971) Bounds on the gain of a Markov decision process. Operat. Res. 19, 240–244.CrossRefGoogle Scholar
Horduk, A. and Tijms, H. (1974) Convergence results and approximations for optimal (s, S) policies. Management Sci. 20, 1432–1438.CrossRefGoogle Scholar
Iglehart, D. (1963) Dynamic programming and stationary analysis in inventory problems. Chapter 1 in Multi-stage Inventory Models and Techniques , ed. Scarf, H., Guilford, D. and Shelly, M.. Stanford University Press, Stanford, CA.Google Scholar
Johnson, E. (1968) On (s, S) policies. Management Sci. 15, 80–101.CrossRefGoogle Scholar
Kakumanu, P. (1971) Continuously discounted Markov decision models with convertable state and action space. Ann. Math. Statist. 42, 916–926.CrossRefGoogle Scholar
Kakumanu, P. (1977) Relation between continuous and discrete time Markovian decision problems. Naval Res. Log. Quart. 24, 431–439.CrossRefGoogle Scholar
Kuenle, C. and Kuenle, H. (1977) Durchschnittsoptimale Strategien in Markovschen Entschiedungsmodellen bei Unbeschraenkten Kosten. Math. Operationsforsch. Statist., Ser. Optimization 8, 549–564.CrossRefGoogle Scholar
Naddor, E. (1975) Optimal and heuristic decisions in single- and multi-item inventory systems. Management Sci. 21, 1234–1249.CrossRefGoogle Scholar
Neuts, M. (1975) Probability distributions of phase type. In Liber Amicorum Prof. Emeritus H. Florin. Dept of Mathematics, University of Louvain, Belgium.Google Scholar
Neuts, M. (1981) Matrix-geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore.Google Scholar
Odoni, A. (1969) On finding the maximal gain for Markov decision processes. Operat. Res. 17, 857–860.CrossRefGoogle Scholar
Porteus, E. (1979) An adjustment to the Norman-White approach to approximating dynamic programs. Operat. Res. 27, 1203–1208.CrossRefGoogle Scholar
Puterman, M. and Bramelle, S. (1979) On the convergence of policy iteration in stationary dynamic programming. Math. Operat. Res. 4, 60–70.CrossRefGoogle Scholar
Roberts, D. (1962) Approximations to optimal policies in a dynamic inventory model. Chapter 13 in Studies in Applied Probability and Management Science , ed. Arrow, K., Karlin, S. and Scarf, H.. Stanford University Press, Stanford, CA.Google Scholar
Ross, S. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco, CA.Google Scholar
Schneider, H. (1978) Methods for determining the re-order point of an (s, S) ordering policy when a service level is specified. J. Operat. Res. Soc. 29, 1181–1194.CrossRefGoogle Scholar
Sahin, I. (1982) On the objective function behavior in (s, S) inventory models. Operat. Res. 30, 709–725.CrossRefGoogle Scholar
Sivazlian, B. (1971) Dimensional and computational analysis in stationary (s, S) inventory problems with gamma distributed demand. Management Sci. 17, B307–B311.CrossRefGoogle Scholar
Tijms, H. and Groenevelt, H. (1984) Simple approximations for the reorder points in periodic and continuous review (s, S) inventory systems with service level constraints. European J. Operat. Res. 17, 175–190.CrossRefGoogle Scholar
Van Hee, K. and Van Der Wal, J. (1977) Strongly convergent dynamic programming: Some results. Bonn. Math. Schr. 98, 165–172.Google Scholar
Veinott, A. (1966) On the optimality of (s, S) inventory policies: new conditions and a new proof. SIAM J. Appl. Math. 14, 1067–1083.CrossRefGoogle Scholar
Veinott, A. and Wagner, H. (1965) Computing optimal (s, S) inventory policies. Management Sci. 11, 525–552.CrossRefGoogle Scholar
Wagner, H. (1975) Principles of Operation Research , 2nd edn. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Wagner, H., O’Hagan, M. and Lundh, B. (1965) An empirical study of exactly and approximately optimal inventory policies. Management Sci. 11, 690–723.CrossRefGoogle Scholar