An Efficient Algorithm for Computing Optimal (<i>s</i>, <i>S</i>) Policies
Operations ResearchPublished 1 December 1984
Awi Federgruen, Paul Zipkin
Citations114
SJR quartileQ1
SJR score2.56
SNIP1.83
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents an algorithm to compute an optimal s, S policy under standard assumptions stationary data, well-behaved one-period costs, discrete demand, full backlogging, and the average-cost criterion.
Abstract
This paper presents an algorithm to compute an optimal (s, S) policy under standard assumptions (stationary data, well-behaved one-period costs, discrete demand, full backlogging, and the average-cost criterion). The method is iterative, starting with an arbitrary, given (s, S) policy and converging to an optimal policy in a finite number of iterations. Any of the available approximations can thus be used as an initial solution. Each iteration requires only modest computations. Also, a lower bound on the true optimal cost can be computed and used in a termination test. Empirical testing suggests very fast convergence.
Keywords
Computer ScienceDecision Sciences
Management ScienceComputing Optimal (<i>s, S</i>) Inventory Policies
306 Citations1965Arthur F. Veinott, Harvey M. Wagner
A complete computational approach for finding optimal (s, S) inventory policies is developed, derived from renewal theory and stationary analysis, generalized to permit the unit interval range of values for \alpha.
SIAM Journal on Applied MathematicsOn the Opimality of $( {s,S} )$ Inventory Policies: New Conditions and a New Proof
277 Citations1966Arthur F. Veinott
Management ScienceThe Power Approximation for Computing (<i>s</i>, <i>S</i>) Inventory Policies
165 Citations1979Richard Ehrhardt
A new analytic approximation for computing (s, S) policies for single items under periodic review with a set-up cost, linear holding and shortage costs, fixed replenishment lead time, and backlogging of unfilled demand is presented.
Management ScienceCoordinated Replenishments in a Multi-Item Inventory System with Compound Poisson Demands
164 Citations1984Awi Federgruen, H. Groenevelt +1 more
Operations Research(<i>s</i>, <i>S</i>) Policies for a Dynamic Inventory Model with Stochastic Lead Times
140 Citations1984Richard Ehrhardt
This study analyzes a stochastic lead time inventory model under the assumptions that a replenishment orders do not cross in time and the lead time distribution for a given order is independent of the number and sizes of outstanding orders to yield an intuitively appealing dynamic program.
The Annals of Mathematical StatisticsDenumerable State Markovian Decision Processes-Average Cost Criterion
117 Citations1966Cyrus Derman
Management Science(<i>s</i>, <i>S</i>) Policies Under Continuous Review and Discrete Compound Poisson Demand
115 Citations1978Blyth C. Archibald, Edward A. Silver
Operations ResearchOn Finding the Maximal Gain for Markov Decision Processes
115 Citations1969Amedeo R. Odoni
This paper shows that White's scheme not only converges, but also can be modified so that monotonic upper and lower bounds on the maximal gain can be obtained.
Management ScienceAn Empirical Study of Exactly and Approximately Optimal Inventory Policies
84 Citations1965Harvey M. Wagner, Michael O’Hagan +1 more
Management ScienceOptimal and Heuristic Decisions in Single-and Multi-Item Inventory Systems
77 Citations1975Eliezer Naddor
Journal of the Operational Research SocietyMethods for Determining the Re-order Point of an (<i>s</i>, <i>S</i>) Ordering Policy when a Service Level is Specified
70 Citations1978Helmut Schneider
Operations ResearchOn the Objective Function Behavior in (<i>s</i>, <i>S</i>) Inventory Models
70 Citations1982İzzet Şahin
It is proved in this paper that E's1Δ, Δ = 0, Δ â¥ 0, is both necessary and sufficient for a global minimum if the underlying renewal function is concave, and the optimal stationary policy can be computed efficiently by a one-dimensional search routine.
Journal of Applied ProbabilityThe optimality equation in average cost denumerable state semi-Markov decision problems, recurrency conditions and algorithms
61 Citations1978Awi Federgruen, Henk Tijms
It will be shown that under each of a number of recurrency conditions on the transition probability matrices associated with the stationary policies, the optimality equation has a bounded solution and yields a stationary policy which is optimal for a strong version of the average cost optimality criterion.
Operations ResearchEvaluating the Effectiveness of a New Method for Computing Approximately Optimal (<i>s</i>, <i>S</i>) Inventory Policies
49 Citations1980James R. Freeland, Evan L. Porteus
A new method for obtaining approximately optimal (s, S) inventory policies was presented recently as an illustration of a general approximation methodology proposed by Porteus and numerical work showed that when demand was normally distributed the method performed very well.
Mathematische Operationsforschung StatistikOn a Switch-Over Policy for Controlling the Workload in a Queueing System with Two Constant Service Rates and Fixed Switch-Over Costs
34 Citations1976Henk Tijms
Management ScienceComputing Optimal Control Limits for <i>GI</i>/<i>M</i>/<i>S</i> Queuing Systems with Controlled Arrivals
26 Citations1983J.A.E.E. van Nunen, Martin L. Puterman
This paper shows how the special structure of this queuing system can be exploited to develop efficient procedures to determine an optimal control limit and presents an explicit algorithm for computing the optimal control.
Operations ResearchA Method for Approximate Solutions to Stochastic Dynamic Programming Problems Using Expectations
26 Citations1968John M. Norman, D. J. White
The technique is to replace probability distributions by their corresponding expectations, and to use the values of the states in the corresponding deterministic system under its optimal policy to determine an approximate policy in the stochastic system through a single application of Howard's policy improvement operation.
Stochastic Processes and their ApplicationsInventory control with two switch-over levels for a class of M/G/1 queueing systems with variable arrival and service rate
26 Citations1978Henk Tijms, F.A. van der Duyn Schouten
International Journal of Production ResearchA comparison and evaluation of approximate continuous review inventory model
25 Citations1975Donald Gross, John F. Ince
Advances in Applied ProbabilityA general markov decision method I: Model and techniques
23 Citations1977G. de Leve, Awi Federgruen +1 more
Management ScienceDimensional and Computational Analysis in Stationary (<i>s</i>, <i>S</i>) Inventory Problems with Gamma Distributed Demand
22 Citations1971B. D. Sivazlian
SIAM Journal on Applied MathematicsImproved Algorithms for Inventory and Replacement-Stocking Problems
21 Citations1970Colin E. Bell
Improved procedures are developed for computing optimal policies in the convex inventory problem with set-up cost and a more efficient algorithm is also developed for a joint replacement and stocking problem.
Operations ResearchTechnical Note—An Adjustment to the Norman-White Approach to Approximating Dynamic Programs
19 Citations1979Evan L. Porteus
An adjustment to the Norman-White approach of approximating stochastic dynamic problems by using expectations is considered, which appears to work surprising well and may turn out to be a competitive practical approach to approximating solutions to the (s, S) inventory model.
Management ScienceConvergence Results and Approximations for Optimal (<i>s</i>, <i>S</i>) Policies
15 Citations1974Arie Hordijk, Henk Tijms
Mathematische Operationsforschung und Statistik Series OptimizationDurchschnittsoptimale Strategien in MARKOVschen Entscheidungsmodellen bei unbeschränkten Kosten
11 Citations1977Christine Küenle, Heinz Uwe Küenle
Markovian decision processes with unbounded one-period costs and average cost criterion are treated and the optimality of (s, S)-policies is shown and a computational method is given.