PM  >> Vol. 8 No. 6 (November 2018)

    Gt/Gt/1队列模型稳态性能指标的研究
    Study on Steady-State Performance Measures of the Gt/Gt/1 Queue Model

  • 全文下载: PDF(530KB) HTML   XML   PP.706-711   DOI: 10.12677/PM.2018.86095  
  • 下载量: 183  浏览量: 259  

作者:  

王军霞,刘建民,尉茜茜:长安大学理学院,陕西 西安

关键词:
稳态单服务台队列布朗运动收敛极限Steady-State Single-Server Queue Brownian Motion Convergence Limit

摘要:

针对到达率随时间变化的单服务台Gt/Gt/1队列模型,假定等待空间无限,在给定到达率函数的基础上,应用随机过程极限和概率测度收敛的相关知识,得到该队列模型各稳态性能指标的收敛极限。

For the Gt/Gt/1 single-server queue model with time-varying arrival rate, we suppose that the waiting space is infinite. By combining the knowledge of the Stochastic-Process Limit and the Convergence of Probability Measures, then the convergence limits of the steady-state performance measures in the queue model are obtained on the basis of a given arrival rate function

1. 引言

排队论主要研究各种排队系统在排队等待中的概率特性,应用领域非常广泛,国内外学者针对不同的排队模型做了大量的研究。Ward通过奥伦斯坦–乌伦贝克过程,得到了稳态下单服务台队列的扩散逼近 [1] 以及负荷过程和队长过程的收敛极限 [2] 。文献 [3] [4] 研究了高负荷下单服务台队列的队长和溢出过程的极限。在高负荷条件下,Liu等研究了到达率随时间变化的网络队列模型 [5] ,Whitt研究了到达临界点的单服务台队列 [6] 。另外,Ma [7] 和Dong [8] 分别对单服务台和多服务台的周期到达队列模型做了一定的研究,并对模型进行数值模拟,更加直观地验证了所得结论。Baccelli等 [9] 和Stanford [10] 在平稳状态下研究了一个服务台的队列性能,得到了有关数量分布的积分方程。本文在前人研究的基础上,运用中心极限定理以及连续映射定理等 [11] [12] 相关知识,研究到达率随时间变化的Gt/Gt/1队列模型,得到队列模型的各种性能指标(到达过程、队长过程和虚等待时间)的收敛极限。

2. Gt/Gt/1队列模型

考虑一般的单服务台Gt/Gt/1队列模型,假定等待空间无限,到达率随时间变化,到达率为 λ ( t ) ,服务率为 μ ( t ) ,负荷强度为 ρ ( t ) λ ( t ) μ ( t ) ( t 0 ) 。A表示到达计数过程, Λ 表示累积到达函数,当 时,

Λ ( t ) 0 t λ ( s ) d s ,

到达率满足:

λ ¯ lim t Λ ( t ) t ,

在不考虑顾放弃的情况下,假设 λ ¯ = 1

到达过程满足:

A ( t ) N a ( Λ ( t ) ) = N a ( 0 t λ ( s ) d s ) ,

其中 N a 是随机计数过程,满足泛函强大数定理(FSLLN)和泛函中心极限定理(FCLT),即当 n 时,在D空间中,

, N ^ a , n c a B a ,

这里 N ¯ a , n N a ( n t ) n N ^ a , n N a ( n t ) n t n ,e是恒等函数, e ( t ) = t ( t 0 ) B a 是标准的布朗运动。

另外,假设服务是由随机计数过程 N s (独立于 N a )产生的, N s 同样满足泛函强大数定理(FSLLN)和泛函中心极限定理(FCLT),即当 n 时,在D空间中,

N ¯ s , n e , ,

这里 N ¯ s , n N s ( n t ) n N ^ s , n N s ( n t ) n t n B s 是标准的布朗运动,且独立于 B a

3. 主要结论及讨论

考虑一系列模型中的第n个模型,下面建立与到达过程有关的高负荷极限,对于单服务台的高负荷极限,通常使负荷强度逐渐趋于1,这里当 n 时,令 ρ n = 1 1 n 。当 t 0 n 1 时,对到达函数 λ n ( t ) 和累积到达函数 Λ n ( t ) 进行流体刻画,分别为:

λ ¯ n ( t ) λ n ( n t ) , Λ ¯ n ( t ) Λ n ( n t ) n .

则有 Λ ¯ n ( t ) = 0 t λ ¯ n ( s ) d s

另外,为了后续研究的方便,对累积到达函数 Λ n ( t ) 在时间 n t 通过增量 n 进行刻画,即 u , < u < + ,当 n 时,有:

Λ ˜ n , t ( u ) Λ n ( n t + u n ) Λ n ( n t ) n , t 0 , n 1 .

假设在D空间中,当 n 时, λ ¯ n λ f Λ ¯ n Λ f

累积到达函数 Λ n ( t ) 的扩散刻画如下

Λ ^ n ( t ) Λ n ( n t ) n Λ f ( t ) n ,

假设 Λ ^ n Λ d Λ d 为连续函数。

到达过程满足:

A n ( t ) N a ( Λ n ( t ) ) = N a ( 0 t λ n ( s ) d s ) ,

根据以上到达函数的刻画,接下来对到达过程进行刻画,如下:

A ¯ n ( t ) N a ( Λ n ( n t ) ) n , A ^ n ( t ) A n ( n t ) n Λ f ( t ) n ,

A ˜ n , t ( u ) A n ( n t + u n ) A n ( n t ) n , t 0 , n 1 .

定理1 (到达过程的极限):在以上刻画的前提下,在D空间中,当 n 时,

有如下的泛函强大数定理: A ¯ n = N ¯ a , n Λ ¯ n Λ f

以及泛函中心极限定理: A ^ n = N ^ a , n Λ ¯ n + Λ ^ n c a B a Λ f + Λ d

A ˜ n , t ( u ) λ f ( t ) u .

证明:根据文献 [11] 中13.2以及连续映射定理,

且由 N ¯ a , n e N ¯ a , n N a ( n t ) n ,得

A ¯ n ( t ) N a ( Λ n ( n t ) ) n = n N ¯ a , n ( Λ n ( n t ) n ) n = N ¯ a , n ( Λ n ( n t ) n ) = N ¯ a , n Λ ¯ n Λ f ,

又由 N ^ a , n c a B a N ^ a , n N a ( n t ) n t n ,得:

A ^ n ( t ) A n ( n t ) n Λ f ( t ) n = A n ( n t ) n n Λ f ( t ) = N a ( Λ n ( n t ) ) n n Λ f ( t ) = n N ^ a , n ( Λ n ( n t ) n ) + Λ n ( n t ) n n Λ f ( t ) = N ^ a , n ( Λ n ( n t ) n ) + Λ n ( n t ) n n Λ f ( t ) = N ^ a , n ( Λ ¯ n ( t ) ) + Λ n ( n t ) n Λ f ( t ) n = N ^ a , n Λ ¯ n ( t ) + Λ ^ n ( t ) c a B a Λ f + Λ d

N ^ a , n c a B a ,以及胎紧性,有: N a ( n t + u n ) N a ( n t ) n u ,进而得:

A ˜ n , t ( u ) A n ( n t + u n ) A n ( n t ) n = N a ( Λ n ( n t + u n ) ) N a ( Λ n ( n t ) ) n = N a ( Λ n ( n t ) + λ f ( t ) u n + ο ( n ) ) N a ( Λ n ( n t ) ) n λ f ( t ) u

接下来刻画队长和虚等待时间:

t 0 时, Q ^ n ( t ) Q n ( n t ) n W ^ n ( t ) W n ( n t ) n

R ( t ; a , b ) 是漂移系数为a,扩散系数为b的反射布朗运动。

定理2 (虚等待时间的高负荷极限):假定系统开始为空,在以上刻画的基础上,且满足以上到达函数,则在 D 2 空间中,当 n 时,有 ( Q ^ n , W ^ n ) ( Q ^ , W ^ ) ,这里当 t 0 时, Q ^ ( t ) R ( Λ f ( t ) ; 1 , c a 2 + c s 2 ) ,对于每一个,当时,

证明:首先刻画到达和服务过程,当 n 1 时,

A ^ n ( t ) N a ( n t ) n t n

S ^ n ( t ) N s ( n t / ρ n ) n t n = N s ( n t / ρ n ) n t / ρ n n + n n 1 t

所以当 n 时,在空间中,

( A ^ n , S ^ n ) ( B a , B s + e )

其中 B a B s 是相互独立的布朗运动,

因此在D空间中, A ^ n S ^ n B a B s e

其次应用 [11] 中的定理9.3.4以及连续映射定理,当 n 时,得:

Q ^ n R ( ) R ( ; 1 , c a 2 + c s 2 ) ,且 Q ^ n R ( Λ f ( ) )

D n ( t ) 代表第n个系统中的离去过程,

W ^ n ( t ) W n ( n t ) n = inf { u 0 : D n ( n t + u n ) D n ( n t ) Q n ( n t ) } = inf { u 0 : ( D n ( n t + u n ) D n ( n t ) ) / n Q n ( n t ) / n } = inf { u 0 : D ^ n , t ( u ) Q ^ n ( t ) } ,

其中 D ^ n , t ( u ) D n ( n t + u n ) D n ( n t ) n

在D空间中,当 n 时, Q ^ n R ( Λ f ( ) )

B n ( t ) [ 0 , t ] 时间内忙的服务台。

D n ( n t ) = N s ( ρ n 1 B n ( Λ n ( n t ) ) ) , t 0

根据 Λ ˜ n , t ( u ) λ f ( t ) u 以及 [11] 中的定理9.3.4,可得:

B n ( Λ n ( n t + u n ) ) B n ( Λ n ( n t ) ) n u λ f ( t ) ,

N ¯ s , n e N ^ s , n c s B s D ^ n , t ( u ) u λ f ( t )

Q ^ n Q ^ ,及 W ^ ( t ) Q ^ ( t ) λ f ( t ) Q ^ ( t ) R ( Λ f ( t ) ; 1 , c a 2 + c s 2 ) ,得:

对于每一个 T > 0 ,当时, sup 0 t T { | W ^ n ( t ) ( Q ^ n ( t ) / λ f ( t ) ) | } 0 .

由联合极限以及 [11] 中的定理11.4.7,得:

D 2 空间中,当 n 时,有 ( Q ^ n , W ^ n ) ( Q ^ , W ^ )

4. 总结

在给定Gt/Gt/1队列模型的到达率函数的基础上,利用泛函中心极限定理、连续映射定理等得到该模型的到达过程、队长过程和虚等待时间的收敛极限,最后运用概率测度收敛和随机过程极限的知识对此做了证明。

参考文献

文章引用:
王军霞, 刘建民, 尉茜茜. Gt/Gt/1队列模型稳态性能指标的研究[J]. 理论数学, 2018, 8(6): 706-711. https://doi.org/10.12677/PM.2018.86095

参考文献

[1] Ward, A.R. and Glynn, P.W. (2003) A Diffusion Approximation for a Markorvian Queue with Reneing. Queuing Systems, 43, 103-128.
[2] Ward, A.R. and Glynn, P.W. (2005) A Diffusion Approximation for a Heavy-Traffic Limits for a GI/GI/1 Queue with Balking or Reneging. Queuing Systems, 50, 371-400.
[3] Jelenkovic, P.R. (1999) Subexponential Loss Rates in GI/GI/1 Queue with Applications. Queuing Systems, 33, 91-123.
[4] Whitt, W. (2004) Heavy-Traffic Limits for Loss Proportions in Single-Server Queues. Queuing Systems, 46, 507-536.
[5] Liu, Y.N. and Whitt, W. (2014) Stabilizing Performance in Networks of Queues with Time-Varying Arrival Rates. Probability in the Engineering and Information Sciences, 28, 419-449.
https://doi.org/10.1017/S0269964814000084
[6] Whitt, W. (2016) Heavy-Traffic Limits for a Single-Server Queue Leading up to a Critical Point. Operations Research Letters, 44, 796-800.
https://doi.org/10.1016/j.orl.2016.10.005
[7] Ma, N. and Whitt, W. (2018) A Rare-Event Simulation Algorithm for Periodic Single-Server Queues. Informs Journal on Computing, 30, 71-89.
https://doi.org/10.1287/ijoc.2017.0766
[8] Dong, J. and Whitt, W. (2015) Using Birth-and-Death Processes to Estimate the Steady-State Distribution of A Periodic Queue. Naval Research Logistics, 62, 664-685.
https://doi.org/10.1002/nav.21672
[9] Baccelli, F., Boyer, P. and Hebuterne, G. (1984) Single-Server Queues with Impatient Customers. Journal of Applied Probability and Advances in Applied Probability, 16, 887-905.
[10] Stanford, R.E. (1979) Renging Phenomena in Single Channel Queue. Mathematics of Operations Research, 4, 162-178.
https://doi.org/10.1287/moor.4.2.162
[11] Whitt, W. (2002) Stochastic-Process Limits. Springer, New York.
[12] Billingsley, P. (1999) Convergence of Probability Measures. 2nd Edition. Wiley, New York.
https://doi.org/10.1002/9780470316962