International Journal of Stochastic Analysis
Volume 2012, Issue 1 109417
Research Article
Open Access

Performance Analysis of Production Systems with Correlated Demand via Diffusion Approximations

Yingdong Lu, 

Corresponding Author

Yingdong Lu

Business Analytics and Mathematical Sciences, IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA watson.ibm.com

Search for more papers by this author
First published: 31 December 2012
https://doi.org/10.1155/2012/109417
Academic Editor: Enzo Orsingher

Abstract

We investigate the performance of a production system with correlated demand through diffusion approximation. The key performance metric under consideration is the extreme points that this system can reach. This problem is mapped to a problem of characterizing the joint probability density of a two-dimensional Brownian motion and its coordinate running maximum. To achieve this goal, we obtain the stationary distribution of a reflected Brownian motion within the positive quarter-plane, which is of independent interest, through investigating a solution of an extended Helmhotz equation.

1. Introduction

There are extensive studies on some classic one-dimensional models in the field of operations research, most notably, the work on the behavior and scheduling of single-server queuing system, as well as the understanding of performance and management of single-item inventory system. Probabilistic tools and techniques such as random walks and integral transformations are traditionally used in analyzing them. More recently, concepts and methodologies in dynamical systems and diffusion processes are brought in through fluid and diffusion approximations, and they extend our understanding and capability of analyzing and control of these systems substantially.

While highly desirable, extending these studies to their multidimensional counterparts is a rather difficult problem. Extensions of classic probabilistic methods and techniques, such as random walk and integral transform, introduce a new level of complication that requires deeper understanding in algebraic and complex geometry for their general treatment. For the approximations methods, their multidimensional counterparts, multidimensional dynamical systems, and multidimensional diffusion processes, also pose significant barriers for either qualitative understanding and quantitative computation. While a general and sophisticated methodology is lacking, some very interesting results have been obtained in establishing convergence results that lay the foundation to both fluid and diffusion approximation schemes. Meanwhile, the quantitative aspect of the problem seriously lagged behind, and results in approximation and control of multidimensional systems are very limited. This calls for more focus be put on computational efforts on such system, so that new tools and techniques can be added to the arsenal of attacking these problem.

In this paper, we aim at extend some theoretical and computational understanding to a simple but representative two-dimensional operations research model. Not only can it serve as a building block for analyzing much more complicated systems, but also provides insights to the understanding of basic structure of general systems with correlated demand. This model is motivated by several typical applications in production systems and scheduling. In such a system, it is very common that one resource is demanded by multiple demand processes, similarly, one class of customer demand could contain a combination of different products. The correlation induced by this commonality poses difficulty even for the simplest version of the model. In this paper, after briefly introducing the mathematical model and stochastic processes that characterize the basic underlying relationship, we provide an diffusion approximation to the stochastic processes in the form of a reflected two-dimensional Brownian motion, which is just an abstraction of previous known results in various forms. Then our main effort will be concentrated on the analysis of some key quantities of this diffusion process. More specifically, we are interested at the joint probability density of the Brownian motion and its coordinate running maximum. To produce the computational result, we relate its computation to finding a proper solution to a classic elliptic partial differential equation, the extended Helmhotz equation.

The rest of the paper will be organized as follows, in Section 2, we will introduce the mathematical model and some preliminary results; in Section 3 we will present the a key Brownian bridge argument; then, in Section 4, we solve an extended Helmhotz equation related to the invariant measure; in Section 5, we present the final calculation results for the probability density, and we conclude the paper with come comments on related future works in Section 6.

2. Model

Suppose that there are two types of products, type 1 and type 2. Each of them is supplied by an independent renewal process. Let us denote them as A1(t) and A2(t), respectively. Statistically, we only require that the interarrival time follows a distribution with finite second moments. Meanwhile, there are two classes of demand, a class-(1) demand requires one unit of type 1 product, a class-(2) demand requires one unit of type 1 product, and a class-(1,2) demand requires one unit of each product 1 and 2. Note that class-(1,2) demand can only be fulfilled when both two types of products are provided. If any of the product requirement can not be satisfied, the demand will be backlogged. Although the model is quite simplistic on the surface, it embodies the basic structure and trade-off for many widely considered systems, for example, assemble-to-order systems in inventory management and queuing systems with flexibility servers. Results on this problem can have many indications to the understanding of those more complicated systems.

Diffusion approximation can be obtained for this system, see, for example [1, 2], the limiting process is a two-dimensional Brownian motion with correlation. One of the most important problems for characterizing the process is the probabilistic distribution of the coordinate running maximum. For many applications, the coordinate running maximums are closely related to the capacity provisioning since they represent how far the process will reach at different directions. For probability theory, it is also a fundamental problem. And this will be the focus of the paper.

From now on, we will focus on the calculation of the probability density function calculation. More specifically, let (X1(t), X2(t)) be a two-dimensional Brownian motion with constant correlation ρ > 0 and initial state (X1(0), X2(0)) = (0,0). Therefore, we have , , for i = 1,2, and . For detailed properties of such process, see, for example, [3]. A quantity that of general interest is, for z ≥ x and w ≥ y and any fixed time t0 > 0
(2.1)
where Mi(t) are the running maximum for Xi(t) for i = 1,2 respectively, that is Mi(t) = sup 0≤s≤t {Xi(s)}. It is easy to see that we can just focus on the case of t0 = 1, general case can be easily obtained through scaling. To be more specific, we have, for any t0,
(2.2)
because (X1(t), X2(t)) and have the same law due to the scaling invariant property of Brownian motion.

In the case of one-dimensional Brownian motion, the density of the Brownian motion and its running maximum is a classical result obtained through reflection principle. In two dimension, the dependence between the two coordinates creates a barrier for generalizing the result easily. In this paper, first, we convert the calculation of the quantity (2.1) to the calculation of density function of the invariant measure for a reflected two-dimensional Brownian motion in the positive orthant with negative drifts through a Brownian bridge argument; then we obtain a Laplace transform of the invariant measure of a reflected two-dimensional Brownian motion in the positive orthant with negative drifts through solving a partial differential equation.

3. A Brownian Bridge Argument

There are many different approaches to the classic problem of the joint distribution of a standard Brownian motion and its running maximum, see, for example, [4]. Here we introduce an approach connecting probability laws of a conditional Brownian motion to a Brownian bridge. To the best of our knowledge, no similar approaches appeared before in the literature. A standard Brownian motion, X(t), which starts at 0, conditioning on the event that it ends at x at time 1, has the same law as
(3.1)
where W(t) is a standard Brownian bridge, that is, a Brownian motion satisfies W(0) = W(1) = 0. Therefore, from the representation of Brownian bridge, we have, for t ∈ [0,1],
(3.2)
where B(t) is a standard Brownian motion, means equal in distribution. Thus, for any z ≥ x, the event of
(3.3)
will have the same probability as,
(3.4)
Apply a variable transform s = 1/t − 1, we get,
(3.5)
or equivalently,
(3.6)
This probability of the above event is equivalent to the stationary distribution of B(s) − zs reflected at zero, which, in turn, equals
(3.7)
Take derivative with respect to z, we have,
(3.8)
So,
(3.9)
This is consistent with the classic results obtained from other approaches such as the reflection principle.
For the two-dimensional Brownian motion, applying the same argument, calculating
(3.10)
for z ≥ x and w ≥ y can be reduced to calculating
(3.11)
Apply the construction of reflected Brownian motion through maximum of Brownian motion with negative drift, see, for example, [5], as well as the two-dimensional version of P. Lévy theorem, see [3], we can conclude that (3.11) is the same as
(3.12)
where is a two-dimensional Brownian motion with negative drifts that reflected at the two positive axes. To be more precise,
(3.13)
where (W1, W2) is a two-dimensional driftless Brownian motion with covariance matrix,
(3.14)
and Li(t),   i = 1,2 are the local time defined as
(3.15)
where θ1 = −z, θ2 = −w. Therefore, following the same logic, to obtain (3.10), we need to compute the stationary distribution of .

4. Stationary Distribution

To calculate the stationary distribution of the reflected Brownian motion , we make use the following result from Harrison and Williams [6].

Theorem 4.1. Functions and are the density of the stationary distribution of X(t) on the orthant and the boundary, if and only if the following basic adjoint relationship (BAR) is satisfied:

(4.1)
where
(4.2)
is the infinitesimal generator and vj(z) is the surface measures defined on the boundary such that the normal vector is pointed inward.

Remark 4.2. Notice that the boundary in the problem we study consists of the two axis. So the surface measure is basically the Lebesgue measure on ℝ1 with the orientation that guarantees that the normal vector points towards the inside of the orthant.

The main idea in this paper is to find a function u(x, y) such that ℒu = e−zx−wy for any pair (w, z), therefore, the first term of (4.1) becomes the Laplace transformation of the stationary distribution, and then to investigate the basic properties of u(x, y) to compute the second term. To find u(x, y), we need to solve the following equation:
(4.3)
Let us first consider the homogeneous version of the equation,
(4.4)
Apply transform,
(4.5)
then, u(ξ, η) satisfies
(4.6)
where and . Let , then v(ξ, η) is the solution of the following problem,
(4.7)
This is so called extended Helmholtz equation. Separation of variables can be applied to obtain the general forms of the solution. Hence, we know that the general solution is
(4.8)
for any constant c1, c2, c3, c4, and . Therefore,
(4.9)
For the inhomogeneous version, it is easy to see that u − (1/(z2 + 2ρzw + w2 − θz − θw))e−zx−wy will be the solution.
Now plug u(x, y) into the BAR (4.1), we have
(4.10)
where and denote the Laplace transform of π(x, y) and σ(x). Given that ci, i = 1, …, 4 and k can be arbitrary, it is necessary that
(4.11)
In fact, they are all in the form of
(4.12)
and A and B satisfy the quadratic equation
(4.13)
which is equivalent to
(4.14)
For any x ∈ ℝ, denote η(x) as the positive conjugate point of x with respect to the curve defined by (4.14). Therefore,
(4.15)
Assume that σ(x) = η(x) −1. It is easy to see that the equation has positive solution only when θi < 0. Hence, we have
(4.16)
Therefore, from (4.10), we obtain the following.

Theorem 4.3. The Laplace transform of the stationary π(x, y) bears the following form:

(4.17)

5. Final Calculations

Recall that our goal is to get an expression for
(5.1)
which is, of course,
(5.2)
The results in the previous section enable us to obtain the Laplace transform of
(5.3)
Apply the Laplace transform with respect to x, y, we get
(5.4)
where is the Laplace transform of . Hence, we obtain the following.

Theorem 5.1. The laplace transform of

(5.5)
with respect (x, y) has the form,
(5.6)

6. Conclusions

We studied a simple but representative operations research model for performance analysis and capacity planning. Through diffusion approximation, we identify the problem of characterizing the joint distribution of a two-dimensional Brownian motion and its coordinate running maximum, which is of independent interests in the theory of probability, as well as other applications. Using some probabilistic techniques, we are able to reduce the problem to the solution of an extended Helmholtz equation, and a careful exam of the solution to this well-known partial differential equation leads to the calculation of the Laplace transform of the desired joint probability distribution.

Standard inversion methods exist for estimating the probabilities from the Laplace transform, in the ongoing research, we are exploring the special structure of our solution, and tailor the inversion method to our special needs, thus provide a very efficient and accurate way of estimating these fundamentally important quantities for both probability theory and operations research.

    The full text of this article hosted at iucr.org is unavailable due to technical difficulties.