This Article Full Text (PDF) e-companion References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Baron, O. Search for Related Content

Regulated Random Walks and the LCFS Backlog Probability: Analysis and Application

Rotman School of Management, University of Toronto, Toronto, Ontario, Canada M5S 3E6
opher.baron{at}rotman.utoronto.ca

Random walks have been used extensively within operations research models such as inventory systems and single-server queues to estimate performance measures. In this paper, we use sample-path analysis to express the steady-state probability of a one-sided regulated random walk to increase and be above a threshold, referred to as the last-come-first-serve (LCFS) backlog probability. We approximate the LCFS backlog probability under mild assumptions on the distribution of the random walk's steps and provide its exact expression when the steps are exponentially distributed, and a closed-form approximation when the steps are normally distributed. In our numerical experiments, the average relative gap between the approximated LCFS backlog probabilities and their simulated values is 5.13%. We further show that the LCFS backlog probability is an upper bound on the loss probability—the probability that a two-sided regulated random walk is at a boundary. This bound is tighter than the backlog probability—the probability that a random walk ever crosses a threshold—that also bounds the loss probability. In an inventory application, we demonstrate that using the LCFS backlog probability rather than the backlog probability reduces the inventory level required to satisfy a service-level constraint on the percentage of orders backlogged. In our examples, this reduction leads to cost savings of 31% on average.

Subject classifications: inventory/production; uncertainty; stochastic; base-stock level for a single item; probability; random walk; bounds on threshold-related probabilities.
History: Received January 2006; revision received February 2007; accepted March 2007.