• Название:

    (5) questa 2008 58 a

  • Размер: 0.29 Мб
  • Формат: PDF
  • или

    Queueing Syst (2008) 58: 65–76
    DOI 10.1007/s11134-007-9059-0

    The M/M/∞ queue in a random environment
    G. Falin

    Received: 24 November 2006 / Revised: 20 November 2007 / Published online: 25 January 2008
    © Springer Science+Business Media, LLC 2008

    Abstract We consider the M/M/∞ queueing system with arrival and service rate
    depending on the state of an auxiliary semi-Markov process (which can be viewed
    as an external environment) and find the mean number of customers in the system in
    steady state. In a particular case when the external environment can be only in two
    states we find the distribution of the number of customers in the system.
    Keywords Infinite server queue · Random environment
    Mathematics Subject Classification (2000) 60K25 · 60K37 · 90B22

    1 Introduction
    Stochastic models whose parameters vary randomly over time depending on the state
    of some external stochastic process (random environment) are of great interest for
    applications. Such models arise naturally in operations research, biology, the reliability theory, the queueing theory. Our contribution is motivated by a recent paper by
    M. Baykal-Gursoy and W. Xiao [1] who considered an infinite-server queue with service rate varying depending on the state of an alternating renewal process C(t) with
    two states, say 0 and 1, and exponentially distributed sojourn times of the process
    in the states (C(t) can be also viewed as a continuous-time Markov chain with two
    states). This model could be used, for example, to evaluate the influence of incidents
    on the congestions of vehicles on a part of a highway. The state 0 means normal
    traffic flow and the state 1 means traffic flow with a lower speed after an incident.
    G. Falin ()
    Department of Probability, Mechanics and Mathematics Faculty, Moscow State University, Moscow
    119992, Russian Federation
    e-mail: gennadi_falin@mtu-net.ru

    66

    Queueing Syst (2008) 58: 65–76

    In the present paper we consider a more general model when the external environment C(t) is a general semi-Markov process. Besides we assume that the state of
    the external environment affects both the service rate and the arrival rate of the main
    infinite-server queue.

    2 Model description
    The model under discussion consists of two parts: an external environment and a
    service system.
    As a model of the external environment we consider a semi-Markov process C(t)
    with a finite state space S. The stochastic dynamic of the process C(t) is defined by
    functions Aij (x), i, j ∈ S, that can be thought of as follows. Suppose that the process
    C(t) has just changed its state to i. Then Aij (x) is the probability that the sojourn
    time in the state i is less than x and the new state of the process is j .
    The variables rij = Aij (+∞), i, j ∈ S, can be viewed as one-step transition probabilities of the embedded Markov chain. We assume that this chain is irreducible and
    denote by πi , i ∈ S, its stationary distribution.
    
    The distribution function of the sojourn time in the state i is Ai (x) = j Aij (x).
     +∞
     +∞
    Let mi = 0 xdAi (x) > 0 and vi = 0 x 2 dAi (x) be the first and the second
     +∞
     +∞
    moments of the sojourn time and mij = 0 xdAij (x), vij = 0 x 2 dAij (x).
     ∞ −sx
    Let also αij (s) = 0 e dAij (x) be the Laplace-Stieltjes transform of the func∞
    
    tion Aij (x) and αi (s) = 0 e−sx dAi (x) = j αij (s) be the Laplace-Stieltjes transform of the sojourn time distribution function Ai (x).
    To deal with a Markov process we introduce a supplementary variable ξ(t) as the
    elapsed sojourn time of the process C(t) in the current state.
    The service system consists of an infinite number of homogeneous servers. When
    the state of the process C(t) is i, customers arrive according to a Poisson flow with
    rate λi and are served with rate μi .
    Let N (t) be the number of customers in the system at time t. For the model under
    consideration the three-dimensional process (C(t), ξ(t), N (t)) is Markovian.
    We will study the system in steady state which exists iff at least one of the rates
    μi is positive. To prove this fact consider the embedded process N (ηk ), where ηk is
    the time of the kth visit of the process C(t) to a fixed environment state i. It is easy
    to see that the sequence of random variables {N (ηk )} forms a discrete-time Markov
    chain and
    N (ηk+1 ) = N (ηk ) + Ak − Bk ,
    where Ak is the number of customers which arrived in the system during period
    [ηk ; ηk+1 ] and Bk is the number of customers which left the system during this period.
    The random variable Ak does not depend on events which have occurred before epoch
    ηk and has finite mean. The random variable Bk depends on the history of the system
    before time ηk only
     ∞through N (ηk ) and its conditional mean value E(Bk |N (ηk ) = n)
    is not less than n 0 (1 − e−μi x )dAi (x) = n(1 − αi (μi )). Thus the mean draft
    xn ≡ E(N (ηk+1 ) − N (ηk )|N (ηk = n)) ≤ EAk − n(1 − αi (μi ))

    Queueing Syst (2008) 58: 65–76

    67

    and if μi > 0 then limn→∞ xn = −∞. Therefore if at least one of the rates μi is
    positive we can guarantee that the embedded Markov chain {N (ηk )} is ergodic. This
    in turn yields ergodicity of the original process (C(t), ξ(t), N (t)).

    3 The mean number of customers in the system
    Theorem 1 The mean number of customers in the system in steady state is
    
    (πi λi Di + Mi zi )
    ,
    EN (t) = i 
    i πi mi

    (1)

    where
    
    Mi =
    
    Di =

    1−αi (μi )
    ,
    μi
    mi ,

    if μi > 0,
    if μi = 0,
    
    
    mi − 1−αμi i(μi ) , if μi > 0,

    1
    μi
    1
    2 vi ,

    if μi = 0,

    and the variables zi can be found as the solution of the following set of linear equations:
    
    
    πj λj Mj i +
    zj αj i (μj ),
    (2)
    zi =
    j

    where

    j

    
    Mj i =

    rj i −αj i (μj )
    ,
    μj

    mj i ,

    if μj > 0,
    if μj = 0.

    Proof Let
    pin (x)dx = P (C(t) = i, x < ξ(t) < x + dx, N (t) = n)
    be the stationary joint distribution of the number of customers in the system, the state
    of the external environment and the elapsed sojourn time.
    In a general way we obtain the following equations of statistical equilibrium:
    
    (x) = − (λi + nμi + ai (x)) pin (x) + λi pi,n−1 (x) + (n + 1)μi pi,n+1 (x),
    pin
      +∞
    dAj i (x)
    ,
    pj n (x)
    pin (0) =
    1 − Aj (x)
    0
    j

    A (x)

    where ai (x) = 1−Ai i (x) is the instantaneous intensity of transition from the state i
    given that the elapsed sojourn time in the state equals x.

    68

    Queueing Syst (2008) 58: 65–76

    For the generating functions
    pi (z, x) =

    +∞
    

    zn pin (x)

    n=0

    these equations give:
    ∂pi (z, x)
    ∂pi (z, x)
    = − (λi − λi z + ai (x)) pi (z, x) + (μi − μi z)
    ,
    ∂x
    ∂z
      +∞
    dAj i (x)
    .
    pj (z, x)
    pi (z, 0) =
    1 − Aj (x)
    0

    (3)
    (4)

    j

    Introduce new unknown functions qi (z, x) by
    pi (z, x) = (1 − Ai (x)) qi (z, x).
    For (3) becomes:
    ∂qi (z, x)
    ∂qi (z, x)
    = −(λi − λi z)qi (z, x) + (μi − μi z)
    .
    ∂x
    ∂z

    (5)

    This equation is well-known in queueing theory. It describes the generating function
    of the number of customers at time x in the M/M/∞ queue with arrival rate λi and
    service rate μi . Its solution is given by





    λi
    qi (z, x) = qi (1 − (1 − z)e−μi x , 0) · exp
    (z − 1) 1 − e−μi x , if μi > 0,
    μi
    and
    qi (z, x) = qi (z, 0) · exp (λi (z − 1)x) ,

    if μi = 0.

    Since pi (z, 0) = qi (z, 0), this gives dependence of pi (z, x) on x:
    if μi > 0, then








    λi
    −μi x
    −μi x
    pi (z, x) = (1 − Ai (x)) · pi 1 − (1 − z)e
    ,
    , 0 · exp
    (z − 1) 1 − e
    μi
    (6)
    and if μi = 0, then
    pi (z, x) = (1 − Ai (x)) · pi (z, 0) · exp (λi (z − 1)x) .

    (7)

    When z = 1 both (6) and (7) give:
    pi (1, x) = (1 − Ai (x)) · pi (1, 0).
    Thus,

    
    pi (1) ≡
    0

    +∞

    pi (1, x)dx = mi · pi (1, 0),

    (8)

    (9)

    Queueing Syst (2008) 58: 65–76

    69

    so that
    pi (1, x) =

    1 − Ai (x)
    pi (1).
    mi

    (10)

    Using relation (8) we get from (4):
    pi (1, 0) =

    

    pj (1, 0)rj i .

    j

    Thus pi (1, 0) = Const · πi and therefore
    pi (1) = Const · πi mi .
    Since

    
    i

    pi (1) = 1, we find the constant:
    1
    .
    π
    i i mi

    Const = 
    Finally,

    πi mi
    pi (1) = P (C(t) = i) = 
    ,
    j πj mj

    (11)

    πi
    .
    j πj mj

    pi (1, 0) = 

    Relation (11) is well-known from the general theory of semi-Markov processes.
    Now differentiate (6), (7) and (4) with respect to z at the point z = 1:

    ∂pi (1, x)
    λi

    = (1 − Ai (x))
    1 − e−μi x · pi (1, 0)
    ∂z
    μi
    + (1 − Ai (x)) e−μi x

    ∂pi (1, 0)
    ,
    ∂z

    if μi > 0,

    ∂pi (1, x)
    = (1 − Ai (x)) λi x · pi (1, 0)
    ∂z
    ∂pi (1, 0)
    , if μi = 0,
    + (1 − Ai (x))
    ∂z
    
    ∂pi (1, 0)  +∞ ∂pj (1, x) dAj i (x)
    =
    .
    ∂z
    ∂z
    1 − Aj (x)
    0
    j

    Substituting (12), (13) into (14) gives:
     ∂pj (1, 0)
    ∂pi (1, 0) 
    =
    αj i (μj ).
    λj Mj i pj (1, 0) +
    ∂z
    ∂z
    j

    j

    (12)

    (13)
    (14)

    70

    Queueing Syst (2008) 58: 65–76

    The mean number
    of customers in the system in steady state, EN(t), can be obtained
    
    as the sum i Ni , where
    

    +∞

    Ni ≡
    0

    Thus,

    ∂pi (1, x)
    ∂pi (1, 0)
    dx = λi Di pi (1, 0) + Mi
    .
    ∂z
    ∂z

    
    πi λi Di  ∂pi (1, 0)
    .
    EN(t) = i
    +
    Mi
    ∂z
    i πi mi
    i

    ∂pi (1,0)
    ∂z

    

    Introducing zi =
    · j πj mj completes the proof.
    It should be noted that variables Mi , Di and Mij considered as functions of the
    parameter μi are continuous at the point μi = 0.
    Using a similar approach one can get the variance of the number of customers in
    the system in steady state. The analysis is along the lines of the proved theorem, but
    it is necessary to differentiate equations (3), (4) twice with respect to z at the point
    z = 1. The formula for V arN (t) is not given here because of its complexity.
    
    3.1 The environment with two states
    Consider now the case when the state space of the process C(t) consists of two points,
    say, 0 and 1. In the context of transportation the state 0 could be thought of as normal
    traffic flow and the state 1 means traffic flow with a lower speed after an incident (the
    partial failure of the group of servers).
    Without loss of generality we may assume that the transition matrix (rij ) is



    0 1
    ,
    1 0

    so that α01 (s) = α0 (s), α10 (s) = α1 (s), π0 = π1 = 12 .
    In this case the set of linear equations (2) can be easily solved which gives the
    following result.
    Theorem 2 If the external environment is an alternating renewal process then for
    μ0 , μ1 > 0


    m0
    m1
    λ1
    λ0
    +
    EN(t) =
    μ0 m0 + m1 μ1 m0 + m1



    λ1
    1
    1
    (1 − α0 (μ0 ))(1 − α1 (μ1 ))
    λ0
    1
    (15)
    +


    1 − α0 (μ0 )α1 (μ1 )
    m0 + m1 μ1 μ0
    μ0 μ1
    and for μ0 > 0, μ1 = 0
    EN(t) =

    λ0
    λ1 m1
    +
    μ0 m0 + m1




    1
    λ1 v 1
    α0 (μ0 )
    +
    .
    + m1
    μ0
    1 − α0 (μ0 )
    2(m0 + m1 )

    (16)

    Queueing Syst (2008) 58: 65–76

    71

    4 The environment with two states, exponential distribution of “normal”
    periods and full interruption of service during “failure”
    Under additional assumptions it is possible to find the distribution of the number
    of customers in the system in steady state. Assume, for example, that μ1 = 0 (full
    interruption of service when the state of the external environment is 1, i.e. the whole
    group of servers is down) and the sojourn time of the process C(t) in the state 0
    (the state of “normal” functioning of the system) is exponentially distributed with
    parameter f = m10 . Then the following theorem holds.
    Theorem 3 Assume that
    • the state space of the process C(t) consist of two points: S = {0, 1},
    • the sojourn time of the process C(t) in the state 0 (the state of “normal” functioning of the system) is exponentially distributed with parameter f = m10 ,
    • μ1 = 0 (during the “failure” periods service is fully interrupted).
    Then the generating function of the number of customers in the system in steady
    state is

    
    λ0
    N (t)
    = exp
    (z − 1) · F (z) · G(z),
    (17)
    p(z) ≡ Ez
    μ0
    where
    F (z) =

    m0
    m1
    +
    ϕ(z),
    m0 + m1 m0 + m1

    1 − α1 (λ1 − λ1 z)
    ,
    m1 (λ1 − λ1 z)

    
    
    λ1 m1 z
    G(z) = exp
    ϕ(u)du .
    μ0 m0 1
    ϕ(z) =

    (18)
    (19)
    (20)

    Proof In the case under consideration general equations (3), (4) become:
    ∂p0 (z, x)
    ∂p0 (z, x)
    = − (λ0 − λ0 z + f ) p0 (z, x) + (μ0 − μ0 z)
    ,
    ∂x
    ∂z
    ∂p1 (z, x)
    = − (λ1 − λ1 z + a1 (x)) p1 (z, x),
    ∂x
     +∞
    p1 (z, x)a1 (x)dx,
    p0 (z, 0) =

    (21)
    (22)
    (23)

    0

    
    p1 (z, 0) =

    +∞

    p0 (z, x)f dx ≡ f · p0 (z).

    (24)

    0

    As we have shown (see (7)), p1 (z, x) depends on x as follows:
    p1 (z, x) = (1 − A1 (x)) · p1 (z, 0) · exp (λ1 (z − 1)x) ,

    (25)

    72

    Queueing Syst (2008) 58: 65–76

    so that (23) becomes
    p0 (z, 0) = α1 (λ1 − λ1 z)p1 (z, 0).

    (26)

    Now integrate (21) with respect to x from x = 0 to +∞:
    −p0 (z, 0) = − (λ0 − λ0 z + f ) p0 (z) + (μ0 − μ0 z)

    ∂p0 (z)
    .
    ∂z

    Using (26) and (24) we can transform this relation to the following differential equation:


    dp0 (z)
    λ0
    f α1 (λ1 − λ1 z) − 1
    =
    · p0 (z).
    +
    dz
    μ0 μ0
    z−1
    Here the function
    α1 (λ1 − λ1 z) − 1
    z−1
    is defined at the point z = 1 as limz→1 f (z) = λ1 m1 .
    We can solve this simple differential equation, which yields

    
    λ0
    p0 (z) = p0 (1) exp
    (z − 1) · G(z),
    μ0
    f (z) =

    (27)

    where the function G(z) is defined by (20).
    Using relation (25) we have:
     +∞
    1 − α1 (λ1 − λ1 z)
    1 − α1 (λ1 − λ1 z)
    p1 (z) ≡
    = fp0 (z)
    ,
    p1 (z, x)dx = p1 (z, 0)
    λ

    λ
    z
    λ1 − λ1 z
    1
    1
    0
    so that


    1 − α1 (λ1 − λ1 z)
    p(z) ≡ p0 (z) + p1 (z) = 1 + f
    · p0 (z).
    λ1 − λ1 z

    Since p0 (1) =



    m0
    m0 +m1 ,

    this completes the proof.

    1
    1
    If the process C(t) is pure Markovian, i.e. α0 (s) = 1+m
    , α1 (s) = 1+m
    , and
    0s
    1s
    λ0 = λ1 = λ, then (15) and (17) give the corresponding results of paper [1].
    

    5 Stochastic decomposition
    Now consider (17) in more detail. The right-hand side of the equation consist of three
    multipliers.
    The first one, exp{ μλ00 (z − 1)}, is the generating function of a random variable
    ν1 which has Poisson distribution with parameter μλ00 . The variable ν1 describes the
    number of customers in the stationary M/M/∞ system without failures.
    The function ϕ(z) can be rewritten as follows:
     +∞
    1 − A1 (x)
    ϕ(z) =
    eλ1 x(z−1)
    dx.
    m1
    0

    Queueing Syst (2008) 58: 65–76

    73

    Thus ϕ(z) is the generating function of a random variable ν2 which has randomized
    Poisson distribution with parameter λ1 χ , where the random variable χ has density
    1
    m1 (1 − A1 (x)):
    ϕ(z) = Ezν2 ,
     +∞
    (λ1 x)n −λ1 x 1 − A1 (x)
    e
    dx.
    P (ν2 = n) =
    n!
    m1
    0
    The random variable χ describes the elapsed time from the last failure given the
    group of servers is down, so that the random variable ν2 describes the total number
    of arrivals during this time.
    Thus the second multiplier, F (z), is the generating function of random variable
    ζ ν2 , where the random variable ζ is a Bernoulli random variable which has the same
    distribution as the external environment:
    m1
    m0
    ,
    P (ζ = 1) =
    ,
    P (ζ = 0) =
    m0 + m1
    m0 + m1
    and random variables ζ and ν2 are independent.
    The third multiplier, G(z), can be rewritten as
    G(z) = eaψ(z)−a ,
    where a =

    λ1 m1
    μ0 m0

    and
    

    ψ(z) = 1 +

    z

    ϕ(u)du = 1 +

    1

    =


    
    n=0

    =E

     z


    un P (ν2 = n)du

    1 n=0


    
    n
    P (ν2 = n)
    P (ν2 = n) +
    zn+1
    n+1
    n+1
    n=0

    + zν2 +1

    ν2
    .
    ν2 + 1

    Thus G(z) is the generating function of a certain random variable ν3 , which has
    1
    the compound Poisson distribution with the Poisson parameter a = μλ10m
    m0 and the
    z
    claim size generating function ψ(z) = 1 + 1 ϕ(u)du:
    ν3 = γ1 + · · · + γν ,
    where ν, γ1 , γ2 , . . . are independent, and
    a n −a
    e , n ≥ 0,
    n!
    1
    P (γk = n) = P (ν2 = n − 1),
    n
    ν2
    .
    P (γk = 0) = E
    ν2 + 1
    P (ν = n) =

    if n ≥ 1,

    74

    Queueing Syst (2008) 58: 65–76

    It should be noted that the third multiplier, G(z), equals
    
    
    p0 (z)
    = E zN (t) |C(t) = 0
    p0 (1)
    if the parameter λ0 = 0. Thus the distribution of the random variable ν3 coincides
    with the conditional distribution of the number of customers in the corresponding
    M/M/∞ system with λ0 = 0 given that the system is in the “normal” state.
    Therefore (17)–(20) directly yield the following result about stochastic decomposition of the number of customers in the system for the case under consideration.
    Theorem 4 Under the assumptions of Theorem 3 the number of customers in the
    system in steady state can be represented as a sum
    ν1 + ζ ν2 + ν3 ,
    where random variables ν1 , ζ , ν2 , ν3 are independent and have the following distributions:
    λ0
    μ0 :

    • ν1 —Poisson distribution with parameter
    P (ν1 = n) =

    (λ0 /μ0 )n −λ0 /μ0
    e
    n!

    • ν2 —randomized Poisson distribution with parameter λ1 χ , where the random variable χ has density m11 (1 − A1 (x)):
    
    P (ν2 = n) =

    +∞

    0

    (λ1 x)n −λ1 x 1 − A1 (x)
    e
    dx
    n!
    m1

    • ζ —the same distribution as the external environment: P (ζ = 0) =
    1
    ,
    1) = m0m+m
    1

    m0
    m0 +m1 , P (ζ

    • ν3 —the compound Poisson distribution with the Poisson parameter a =
    the claim size generating function

    ν2 +1
    ψ(z) = E ν2 +z
    ν2 +1 :

    λ1 m1
    μ0 m0

    =

    and

    ν3 = γ1 + · · · + γν ,
    where ν, γ1 , γ2 , . . . are independent, and
    a n −a
    e ,
    n!
    = ψ(z).

    P (ν = n) =
    Ezγk

    It should be noted that this decomposition differs from the stochastic decomposition established in [1].

    Queueing Syst (2008) 58: 65–76

    75

    5.1 The moments
    Our result on stochastic decomposition is very useful, in particular, for obtaining
    explicit formulas for moments of the number of customers in the system in steady
    state.
    Theorem 5 Under the assumptions of Theorem 3,
    EN (t) =
    Var N (t) =

    λ0
    λ1 m1
    λ1 v 1
    ,
    +
    +
    μ0 μ0 m0 2(m0 + m1 )

    (28)

    λ2 v 1
    λ21 σ1
    λ0
    λ1 m1
    +
    + 1
    +
    μ0 μ0 m0 2μ0 m0 3(m0 + m1 )
    +

    λ21 v12
    λ1 v 1

    .
    2(m0 + m1 ) 4(m0 + m1 )2

    (29)

    Proof The stochastic decomposition yields:
    EN(t) = Eν1 + Eζ · Eν2 + Eν3 .
    Since
    Eν1 =

    λ0
    ,
    μ0

    Eζ = P (ζ = 1) =
    

    

    Eν2 = ϕ (1) =

    m1
    ,
    m0 + m0

    +∞

    λ1 x
    0

    Eν3 = Eν · Eγ =

    1 − A1 (x)
    λ1 v 1
    dx =
    ,
    m1
    2m1

    λ1 m1
    · 1,
    μ0 m0

    we get (28). Note that the same formula follows from (15).
    For the variance we have:
    Var N (t) = Var ν1 + Var(ζ ν2 ) + Var ν3 .
    Since ν1 has a Poisson distribution, its variance is equal to the parameter of the distribution, i.e.
    Var ν1 =

    λ0
    .
    μ0

    Now calculate Var(ζ ν2 ). First note that
    Var(ζ ν2 ) = Eζ · Eν22 − (Eζ · Eν2 )2
    = Eζ · E(ν2 (ν2 − 1)) + Eζ · Eν2 − (Eζ · Eν2 )2 .

    76

    Queueing Syst (2008) 58: 65–76

    But



    E ν2 (ν2 − 1) = ϕ  (1) =

    

    +∞
    0

    where

    

    +∞

    σ1 =

    λ21 x 2

    λ2 σ 1
    1 − A1 (x)
    dx = 1 ,
    m1
    3m1

    x 3 dA1 (x).

    0

    Thus,
    Var(ζ ν2 ) =

    λ21 σ1
    λ21 v12
    λ1 v 1
    .
    +

    3(m0 + m1 ) 2(m0 + m1 ) 4(m0 + m1 )2

    Now calculate Var ν3 . It is well-known that for the compound Poisson distribution the second central moment, i.e. variance, can be expressed through the second
    moment about the origin of the claim size distribution as follows:
    Var ν3 = aEγ 2 .
    Since
    Eγ 2 = ψ  (1) + ψ  (1) = ϕ  (1) + ϕ(1) = Eν2 + 1 =

    λ1 v 1
    + 1,
    2m1

    we have:
    Var ν3 =
    After some algebra we get (29).

    λ2 v 1
    λ1 m1
    + 1
    .
    μ0 m0 2μ0 m0
    

    References
    1. Baykal-Gursoy, M., Xiao, W.: Stochastic decomposition in M/M/∞ with Markov modulated service
    rates. Queueing Syst. 48, 75–88 (2004)