Search

Supply contracts are designed to minimize inventory costs or to hedge against undesirable events (e.g., shortages) in the face of demand or supply uncertainty. In particular, replenishment terms stipulated by supply contracts need to be optimized with respect to overall costs, profits, service levels, etc. In this paper, we shall be primarily interested in minimizing an inventory cost function with respect to a constant replenishment rate. Consider a single-product inventory system under continuous review with constant replenishment and compound Poisson demands subject to lost-sales. The system incurs inventory carrying costs and lost-sales penalties, where the carrying cost is a linear function of on-hand inventory and a lost-sales penalty is incurred per lost sale occurrence as a function of lost-sale size. We first derive an integro-differential equation for the expected cumulative cost until and including the first lost-sale occurrence. From this equation, we obtain a closed form expression for the time-average inventory cost, and provide an algorithm for a numerical computation of the optimal replenishment rate that minimizes the aforementioned time-average cost function. In particular, we consider two special cases of lost-sales penalty functions: constant penalty and loss-proportional penalty. We further consider special demand size distributions, such as constant, uniform and Gamma, and take advantage of their functional form to further simplify the optimization algorithm. In particular, for the special case of exponential demand sizes, we exhibit a closed form expression for the optimal replenishment rate and its corresponding cost. Finally, a numerical study is carried out to illustrate the results.

This paper considers a continuous-review, single-product, production-inventory system with a constant replenishment rate, compound Poisson demands, and lost sales. Two objective functions that represent metrics of operational costs are considered: (1) the sum of the expected discounted inventory holding costs and lost-sales penalties, both over an infinite time horizon, given an initial inventory level; and (2) the long-run time average of the same costs. The goal is to minimize these cost metrics with respect to the replenishment rate. It is, however, not possible to obtain closed-form expressions for the aforementioned cost functions directly in terms of positive replenishment rate (PRR). To overcome this difficulty, we construct a bijection from the PRR space to the space of positive roots of Lundberg's fundamental equation, to be referred to as the Lundberg positive root (LPR) space. This transformation allows us to derive closed-form expressions for the aforementioned cost metrics with respect to the LPR variable, in lieu of the PRR variable. We then proceed to solve the optimization problem in the LPR space and, finally, recover the optimal replenishment rate from the optimal LPR variable via the inverse bijection. For the special cases of constant or loss-proportional penalty and exponentially distributed demand sizes, we obtain simpler explicit formulas for the optimal replenishment rate.

This paper addresses the problem of inventory penalty pricing under the risk-neutral valuation principle. The underlying production-inventory system has a constant replenishment rate and a compound renewal demand stream (i.e., iid demand interarrival times are independent of iid demand sizes), and is subject to underage and overage penalties. Our pricing approach treats the penalties as a series of perpetual American options, and constructs auxiliary martingale processes in term of the inventory process. We provide a necessary and sufficient martingale condition for general compound renewal demands. Explicit expressions of penalty functions for underage and overage are obtained for the case where demand arrivals follow a Poisson process.

ARM (Auto-Regressive Modular) processes constitute a broad class of nonlinear autoregressive schemes with modulo-1 reduction and additional transformations. Unlike their TES (Transform-Expand-Sample) precursors, which only admit iid innovation sequences, ARM processes admit dependent innovation sequences as well, so long as they are independent of the initial ARM variate. As such, the class of ARM processes constitutes a considerable generalization of the TES class, endowed with enhanced modeling flexibility. For example, a Markovian innovation sequence can model burstiness in traffic processes far better by making use of the Markovian state to capture the structure of bursts. This paper introduces ARM processes and derives their fundamental properties in terms of marginal distributions and autocorrelation functions. It defines several useful subclasses that illustrate the modeling flexibility of ARM classes. Finally, it outlines a modeling methodology of empirical time series that can simultaneously fit ...

This paper describes a general methodology for constructing accurate source models of long sequences (full-length movies) of full-motion compressed VBR (variable bit rate) video, directly from empirical data sets of observed bit rate (frame size) records. The main idea is to first cluster scenes into classes and use TES (transform-expand-sample) processes to carefully model their duration and bit rate processes, and then modulate these scene class models by a Markov-renewal process that governs scene transitions. The resulting model is a Markov-renewal-modulated TES (MRMT) process. The fidelity criteria imposed are relatively stringent in that they call for the simultaneous capture of empirical histograms and autocorrelation functions, as well as the qualitative appearance of the empirical data, including burstiness. To illustrate the methodology, the paper provides a detailed description of the modeling procedure, using a JPEG-like coding trace of the "Star Wars" movie as a working example. The resulting MRMT model was validated by comparing its simulation-based statistics to their empirical counterparts, and by a performance study of the corresponding loss rates for various buffer sizes. The results support the efficacy of the modeling methodology and suggest that suites of realistic and compact source models can be developed for other types of movies under a variety of coding schemes. These may be used to drive realistic Monte Carlo simulations of broadband telecommunications networks.

Markov processes are an important ingredient in a variety of stochastic applications. Notable instances include queueing systems and traffic processes offered to them. This paper is concerned with Markovian traffic, i.e., traffic processes whose inter-arrival times (separating the time points of discrete arrivals) form a real-valued Markov chain. As such this paper aims to extend the classical results of renewal traffic, where interarrival times are assumed to be independent, identically distributed. Following traditional renewal theory, three functions are addressed: the probability of the number of arrivals in a given interval, the corresponding mean number, and the probability of the times of future arrivals. The paper derives integral equations for these functions in the transform domain. These are then specialized to a subclass, TES+, of a versatile class of random sequences, called TES (Transform-Expand-Sample), consisting of marginally uniform autoregressive schemes with modulo-1 reduction, followed by various transformations. TES models are designed to simultaneously capture both first-order and second-order statistics of empirical records, and consequently can produce high-fidelity models. Two theoretical solutions for TES+ traffic functions are derived: an operator-based solution and a matric solution, both in the transform domain. A special case, permitting the conversion of the integral equations to differential equations, is illustrated and solved. Finally, the results are applied to obtain instructive closed-form representations for two measures of traffic burstiness: peakedness and index of dispersion, elucidating the relationship between them.

In this paper we establish a joint central limit theorem for customer and time averages by applying a martingale central limit theorem in a Markov framework. The limiting values of the two averages appear in the translation terms. This central limit theorem helps to construct confidence intervals for estimators and perform statistical tests. It thus helps determine which finite average is a more asymptotically efficient estimator of its limit. As a basis for testing for PASTA (Poisson arrivals see time averages), we determine the variance constant associated with the central limit theorem for the difference between the two averages when PASTA holds.

TES (Transform-Expand-Sample) is a versatile class of stochastic sequences which can capture arbitrary marginals and a wide variety of sample path behavior and autocorrelation functions. In TES, the initial variate is uniform on [0,1) and the next variate is obtained recursively by taking the fractional part (i.e., modulo-1 reduction) of a linear autoregressive scheme. We show how this class gives rise to uniform Markovian sequences in a general and natural way, by observing that marginal uniformity is closed under modulo-1 addition of an independent variate with arbitrary distribution. We derive the transition function of TES sequences and the autocovariance function of transformed TES sequences using Fourier and Laplace Transform methods. The autocovariance formulas are amenable to fast and accurate calculation and provide the theoretical basis for a computer-based methodology of heuristic TES modeling of empirical data. A companion paper contains various examples which show the efficacy of the TES appr...

We investigate when Arrivals See Time Averages (ASTA) in a stochastic model; i.e., when the stationary distribution of an embedded sequence, obtained by observing a continuous-time stochastic process just prior to the points (arrivals) of an associated point process, coincides with the stationary distribution of the observed process. We also characterize the relation between the two distributions when ASTA does not hold. We introduce a Lack of Bias Assumption (LBA) which stipulates that, at any time, the conditional intensity of the point process, given the present state of the observed process, be independent of the state of the observed process. We show that LBA, without the Poisson assumption, is necessary and sufficient for ASTA in a stationary process framework. Consequently, LBA covers known examples of non-Poisson ASTA, such as certain flows in open Jackson queueing networks, as well as the familiar Poisson case (PASTA). We also establish results to cover the case in which the process is observed just after the points, e.g., when departures see time averages. Finally, we obtain a new proof of the Arrival Theorem for product-form queueing networks.

A cluster-based server consists of a front-end dispatcher and several back-end servers. The dispatcher receives incoming requests, and then assigns them to back-end servers for processing. Our goal is to devise an assignment policy that has good response time performance, and is practical to implement in that the amount of information used by the dispatcher is relatively small, so that the attendant computation and communication overheads are low. In contrast to extant assignment policies that apply the same assignment policy to all incoming jobs, our approach calls for the dispatcher to classify incoming jobs as long or short, and then use class-dependent assignment policies. Specifically, we propose a policy, called CDA (Class Dependent Assignment), where short jobs are assigned in Round-Robin manner as soon as they arrive, while long jobs are deferred and assigned only when a back-end server becomes idle. Furthermore, when processing a long job, a back-end server is not assigned any other jobs.Our approach is motivated by empirical evidence suggesting that the sizes of files traveling on the Internet follow power-law distributions, where long jobs constituting a small fraction of all incoming jobs actually account for a large fraction of the overall load. To gauge the performance of the proposed policy, we exercised it on empirical data traces measured at Internet sites serving the 1998 World Cup. Since the assignment of long jobs incurs computational overhead as well as extra communication overhead, we studied the performance of CDA as function of the fraction of jobs classified as long. Our study shows that classification of even a small fraction of jobs as long can have a profound impact on overall response time performance. More speciafically, our experimental results show that if less than 3% of the jobs are classified as long, then CDA outperforms traditional policies, such as Round-Robin, by two orders of magnitude. From an implementation viewpoint, these results support our contention that CDA-based assignment is a practical policy combining low overhead and greatly improved performance.

A study is made of the limiting behavior of averages from an embedded stochastic process obtained by sampling a discrete-time stochastic process at points of an associated discrete-time stochastic point process. It is determined when the limit of the averages from the embedded process coincides with the limit of the averages from the original process. In a certain stationary Markov framework, this happens if and only if the point process is a Bernoulli sequence with future points being independent of the state of the Markov process. >

This paper presents a stochastic model for the variable bit rate (VBR) video of the entire "Star Wars" movie under a JPEG-like compression. The goal of this work is to develop a methodology for constructing a suite of high-fidelity source models of full-motion video as a traffic benchmark suitable for driving realistic Monte Carlo simulations of broadband telecommunications networks (ATM based B-ISDN). To this end, a transform-expand-sample) TES-based modeling methodology was employed, subject to fidelity criteria requiring the simultaneous capture of both first-order and second-order statistics. The entire movie was modeled as a Markov renewal modulated TES (MRMT) process with class-dependent holding times. The modeling results support the efficacy of the modeling methodology and suggest that high-fidelity compact source models of full-motion video can be developed by applying this methodology to other types of movies under a variety of coding schemes.

PASTA (Poisson Arrivals See Time Averages) is a term coined by R. Wolff in his well known 1982 paper. In keeping with Wolff's terminology, we use the term anti-PASTA to refer to the following converse of PASTA. Given that arrivals do indeed see time averages, when must the arrival process necessarily be Poisson? We show that anti-PASTA is satisfied in a pure-jump Markov process, provided that the arrival process corresponds to a subset of the Markov process jumps.

This paper considers a regular Markov process with continuous parameter, countable state space, and stationary transition probabilities, and defines a class of traffic processes over it. The possibility that multiple traffic processes constitute mutually independent Poisson processes is investigated. A variety of independence conditions on a traffic process and the underlying Markov process are shown to lead to Poisson-related properties; these conditions include weak pointwise independence, and pointwise independence. Some examples of queueing-theoretic applications are given. For the class of traffic processes considered here in a queueing-theoretic context, Muntz's M M property, Gelenbe and Muntz's notion of completeness, and Kelly's notion of quasi-reversibility are shown to be essentially equivalent to pointwise independence of traffic and state. The relevance of the theory to queueing network decomposition is pointed out.

A Markov step process Z equipped with a possibly non-denumerable state space X can model a variety of queueing, communication and computer networks. The analysis of such networks can be facilitated if certain traffic flows consist of mutually independent Poisson processes with respective deterministic intensities λ i (t). Accordingly, we define the multivariate counting process N = (N 1, N 2, · ·· N c) induced by Z; a count in Ni occurs whenever Z jumps from x (χ into a (possibly empty) target set . We study N through the infinitesimal operator à of the augmented Markov process W = (Z, N), and the integral relationship connecting à with the transition operator T t of W. It is then shown that Ni depends on a non-negative function ri defined on χ; ri (x) may be interpreted as the expected rate of increase in Ni , given that Z is in state x. A multivariate N is Poisson (i.e., composed of mutually independent Poisson streams N i ) if and only if simultaneous jumps are impossible in a certain sense, and if the conditional expectation E[r i (Z(t) | 𝒩 i ] = E[r i (Z(t))] for i = 1, 2, ···, c and each t ≧ 0, where 𝒩 i is the σ-algebra σ{N(s), s ≦ t}. Necessary and sufficient conditions are also specified that, for each s ≦ t, the variates [N i (t)-N i (s)] are mutually independent Poisson distributed; this involves a weakened version of E[r i (Z(v)) | N(v) – N(u)] = E [r i (Z(v))] for i = 1, 2, ···, c and all 0 ≦ u ≦ v. It is shown that the above criteria are automatically met by the more stringent classical requirement that N(t) and Z(t) be independent for each t ≧ 0.

Burke and Reich independently showed that the output of an M/M/1 queue in equilibrium is a Poisson process. Consequently, analysis of series (tandem) exponential servers with a Poisson input stream can be reduced to consideration of a series of M/M/1 queues. This work generalizes the above results to so-called Jackson networks, consisting of exponential servers with mutually independent Poisson exogenous inputs and random customer routings permitting customer feedback. We prove that traffic on all exit arcs of a network in equilibrium is Poisson; moreover, the customer streams leaving any exit set are mutually independent. Here an exit arc is a path from server node i such that a customer moving along the arc cannot return to i; an exit set V is a set of server nodes such that customers departing V can never re-enter V. As a special case, the traffic streams leaving a Jackson network in equilibrium are mutually independent Poisson processes. In contrast, traffic on non-exit arcs is non-Poisson, and indeed non-renewal. A canonical decomposition of the server nodes is defined as a partition of the server node set into components C*q, each consisting of communicating servers. We show that the set of all exit arcs coincides with the arcs emanating from the C*q. Finally, for a Jackson network in equilibrium, each C*q is itself a Jackson network in equilibrium.

Consider a counting process {N(t)>0}. In the one-dimensional case it is shown that the set of distributions of N(t) for t>0. This result is a "marginal"version of the characterization of a point process by its stochastic intensity. It is shown that the correspondng results have to be modifed in the multi-dimensional case. These results are particularized to the case of point processes with Poisson marginals.

We consider a queueing network with types of customers. Poisson arrivals, type dependent routing and state dependent service. A number of stochastic aspects relating to sojourn times are investigated. Included are limiting state distributions imbedded at customer move times, mean sojourn times, and sojourn time distributions along overtake-free paths. It is shown that Reich's results extend to overtake-free paths yielding limiting sojourn time distributions which correspond to the sum of exponential independent stages of sojourn in individual nodes. The analysis is bused solely on considerations of population distributions through conditioning on customers' itineraries in the network.

The equilibrium behavior of Jackson queueing networks (Poisson arrivals, exponential servers and Bernoulli switches) has recently been investigated in some detail. In particular, it was found that in equilibrium, the traffic processes on the so-called exit arcs of a Jackson network with single server nodes constitute Poisson processes—a result extending Burke's theorem from single queues to networks of queues. A conjecture made by Burke and others contends that the traffic processes on non-exit arcs cannot be Poisson in equilibrium. This paper proves this conjecture to be true for a variety of Jackson networks with single server nodes. Subsequently, a number of characterizations of the equilibrium traffic streams on the arcs of open Jackson networks emerge, whereby Poisson-related stochastic properties of traffic streams are shown to be equivalent to a simple graph-theoretical property of the underlying arcs. These results then help to identify some inherent limitations on the feasibility of equilibrium decompositions of Jackson networks, and to point out conditions under which further decompositions are ‘approximately’ valid.

This paper proposes a methodology for computing numerical bounds on cumulative-time (i.e., the time spent in a specified set of states before entering another specified set of states) distributions over discrete state Markov processes. The methodology uses randomization procedures to compute results for appropriately defined transient Markov processes; the transient distribution computed is equivalent to the requisite cumulative-time distribution. A queueing application of the methodology to delay times in queueing networks is outlined and its efficacy is appraised by comparing the results with a sojourn time for a problem with a known distribution.

This paper relates the reversibility of certain discrete state Markovian queueing networks — the class of quasi-reversible networks — to the reversibility of the underlying switching process. Quasi-reversible networks are characterized by a product form equilibrium state distribution. When the state can be represented by customer totals at each node, the reversibility of the state process is equivalent to the reversibility of the switching process. More complicated quasi-reversible networks require additional conditions, to ensure the reversibility of the network state process.

A Markov step process Z equipped with a possible non-denumerable state space x can model a variety of queueing, communication and computer networks. The analysis of such networks can be facilitated if certain traffic flows consist of mutually independent Poisson processes. A multivariate N is Poisson (i.e., composed of mutually independent Poisson streams N sub i) if each r sub i (Z) is stationary, and r sub i(Z(t)) is independent of N(t) for each i and each t greater than or = 0. The latter is already much less restrictive than the independent of N(t) and Z(t), but it is able to find even weaker hypotheses which are both necessary and sufficient for N to be Poisson.

Let {Xt}t>0 be a Markov jump process and {Tn}n=0∞ a subset of the jump epochs of the process {Xt}t>0. The main results of this paper are computable formulae for the transient and invariant distributions of {XTn}n=0∞ and {XTn̄}n=0∞. We also characterize when the invariant distributions of {Xt}t>0 and {XTn}n=0∞ are the same and show that in this case {Tn}n=0∞ is a Poisson process. The results are applied to a variety of discrete-slate queueing networks to obtain their state distribution as seen by customers in arrival streams, departure streams, and traffic streams on the arcs. The main conclusion drawn is that for many traffic streams, the invariant distribution seen by customers in that stream coincides with the invariant distribution of {Xt}t>0 provided the customer in motion is excluded.