Gt/Gt/1队列模型稳态性能指标的研究

期刊菜单

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

DOI:10.12677/PM.2018.86095,PDF,HTML,XML,下载: 1,150浏览: 2,363
作者:王军霞,刘建民,尉茜茜：长安大学理学院，陕西西安
关键词:稳态；单服务台队列；布朗运动；收敛极限；Steady-State；Single-Server Queue；Brownian Motion；Convergence Limit

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

Abstract:For the Gt/Gt/1single-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

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

1. 引言

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

2. G_t/G_t/1队列模型

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

$Λ (t) \equiv \int_{0}^{t} λ (s) d s$ ,

到达率满足：

$\bar{λ} \equiv \lim_{t \to \infty} \frac{Λ (t)}{t}$ ,

在不考虑顾放弃的情况下，假设 $\bar{λ} = 1$ 。

到达过程满足：

$A (t) \equiv N_{a} (Λ (t)) = N_{a} (\int_{0}^{t} λ (s) d s)$ ,

其中 $N_{a}$ 是随机计数过程，满足泛函强大数定理(FSLLN)和泛函中心极限定理(FCLT)，即当 $n \to \infty$ 时，在D空间中，

, ${\hat{N}}_{a, n} \Rightarrow c_{a} B_{a}$ ,

这里 ${\bar{N}}_{a, n} \equiv \frac{N_{a} (n t)}{n}$ ， ${\hat{N}}_{a, n} \equiv \frac{N_{a} (n t) - n t}{\sqrt{n}}$ ，e是恒等函数， $e (t) = t (t \geq 0)$ ， $B_{a}$ 是标准的布朗运动。

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

${\bar{N}}_{s, n} \to e$ ,,

这里 ${\bar{N}}_{s, n} \equiv \frac{N_{s} (n t)}{n}$ ， ${\hat{N}}_{s, n} \equiv \frac{N_{s} (n t) - n t}{\sqrt{n}}$ ， $B_{s}$ 是标准的布朗运动，且独立于 $B_{a}$ 。

3. 主要结论及讨论

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

${\bar{λ}}_{n} (t) \equiv λ_{n} (n t)$ , ${\bar{Λ}}_{n} (t) \equiv \frac{Λ_{n} (n t)}{n}$ .

则有 ${\bar{Λ}}_{n} (t) = \int_{0}^{t} {\bar{λ}}_{n} (s) d s$ 。

另外，为了后续研究的方便，对累积到达函数 $Λ_{n} (t)$ 在时间 $n t$ 通过增量 $\sqrt{n}$ 进行刻画，即 $\forall u, - \infty < u < + \infty$ ，当 $n \to \infty$ 时，有：

${\tilde{Λ}}_{n, t} (u) \equiv \frac{Λ_{n} (n t + u \sqrt{n}) - Λ_{n} (n t)}{\sqrt{n}}$ , $t \geq 0$ , $n \geq 1$ .

假设在D空间中，当 $n \to \infty$ 时， ${\bar{λ}}_{n} \to λ_{f}$ ， ${\bar{Λ}}_{n} \to Λ_{f}$ 。

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

${\hat{Λ}}_{n} (t) \equiv \frac{Λ_{n} (n t) - n Λ_{f} (t)}{\sqrt{n}}$ ,

假设 ${\hat{Λ}}_{n} \to Λ_{d}$ ， $Λ_{d}$ 为连续函数。

到达过程满足：

$A_{n} (t) \equiv N_{a} (Λ_{n} (t)) = N_{a} (\int_{0}^{t} λ_{n} (s) d s)$ ,

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

${\bar{A}}_{n} (t) \equiv \frac{N_{a} (Λ_{n} (n t))}{n}$ , ${\hat{A}}_{n} (t) \equiv \frac{A_{n} (n t) - n Λ_{f} (t)}{\sqrt{n}}$ ,

${\tilde{A}}_{n, t} (u) \equiv \frac{A_{n} (n t + u \sqrt{n}) - A_{n} (n t)}{\sqrt{n}}$ , $t \geq 0$ , $n \geq 1$ .

定理1 (到达过程的极限)：在以上刻画的前提下，在D空间中，当 $n \to \infty$ 时，

有如下的泛函强大数定理： ${\bar{A}}_{n} = {\bar{N}}_{a, n} \circ {\bar{Λ}}_{n} \to Λ_{f}$ 。

以及泛函中心极限定理： ${\hat{A}}_{n} = {\hat{N}}_{a, n} \circ {\bar{Λ}}_{n} + {\hat{Λ}}_{n} \Rightarrow c_{a} B_{a} \circ Λ_{f} + Λ_{d}$ ，

${\tilde{A}}_{n, t} (u) \to λ_{f} (t) u$ .

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

且由 ${\bar{N}}_{a, n} \to e$ ， ${\bar{N}}_{a, n} \equiv \frac{N_{a} (n t)}{n}$ ，得

${\bar{A}}_{n} (t) \equiv \frac{N_{a} (Λ_{n} (n t))}{n} = \frac{n {\bar{N}}_{a, n} (\frac{Λ_{n} (n t)}{n})}{n} = {\bar{N}}_{a, n} (\frac{Λ_{n} (n t)}{n}) = {\bar{N}}_{a, n} \circ {\bar{Λ}}_{n} \to Λ_{f}$ ,

又由 ${\hat{N}}_{a, n} \Rightarrow c_{a} B_{a}$ ， ${\hat{N}}_{a, n} \equiv \frac{N_{a} (n t) - n t}{\sqrt{n}}$ ，得：

$\begin{array}{l} {\hat{A}}_{n} (t) \equiv \frac{A_{n} (n t) - n Λ_{f} (t)}{\sqrt{n}} = \frac{A_{n} (n t)}{\sqrt{n}} - \sqrt{n} Λ_{f} (t) = \frac{N_{a} (Λ_{n} (n t))}{\sqrt{n}} - \sqrt{n} Λ_{f} (t) \\ = \frac{\sqrt{n} {\hat{N}}_{a, n} (\frac{Λ_{n} (n t)}{n}) + Λ_{n} (n t)}{\sqrt{n}} - \sqrt{n} Λ_{f} (t) = {\hat{N}}_{a, n} (\frac{Λ_{n} (n t)}{n}) + \frac{Λ_{n} (n t)}{\sqrt{n}} - \sqrt{n} Λ_{f} (t) \\ = {\hat{N}}_{a, n} ({\bar{Λ}}_{n} (t)) + \frac{Λ_{n} (n t) - n Λ_{f} (t)}{\sqrt{n}} = {\hat{N}}_{a, n} \circ {\bar{Λ}}_{n} (t) + {\hat{Λ}}_{n} (t) \\ \Rightarrow c_{a} B_{a} \circ Λ_{f} + Λ_{d} \end{array}$

由 ${\hat{N}}_{a, n} \Rightarrow c_{a} B_{a}$ ，以及胎紧性，有： $\frac{N_{a} (n t + u \sqrt{n}) - N_{a} (n t)}{\sqrt{n}} \Rightarrow u$ ，进而得：

$\begin{array}{l} {\tilde{A}}_{n, t} (u) \equiv \frac{A_{n} (n t + u \sqrt{n}) - A_{n} (n t)}{\sqrt{n}} \\ = \frac{N_{a} (Λ_{n} (n t + u \sqrt{n})) - N_{a} (Λ_{n} (n t))}{\sqrt{n}} \\ = \frac{N_{a} (Λ_{n} (n t) + λ_{f} (t) u \sqrt{n} + ο (\sqrt{n})) - N_{a} (Λ_{n} (n t))}{\sqrt{n}} \\ \Rightarrow λ_{f} (t) u \end{array}$

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

当 $t \geq 0$ 时， ${\hat{Q}}_{n} (t) \equiv \frac{Q_{n} (n t)}{\sqrt{n}}$ ， ${\hat{W}}_{n} (t) \equiv \frac{W_{n} (n t)}{\sqrt{n}}$ 。

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

定理2 (虚等待时间的高负荷极限)：假定系统开始为空，在以上刻画的基础上，且满足以上到达函数，则在 $D^{2}$ 空间中，当 $n \to \infty$ 时，有 $({\hat{Q}}_{n}, {\hat{W}}_{n}) \Rightarrow (\hat{Q}, \hat{W})$ ，这里当 $t \geq 0$ 时，， $\hat{Q} (t) \equiv R (Λ_{f} (t); - 1, c_{a}^{2} + c_{s}^{2})$ ，对于每一个，当时，。

证明：首先刻画到达和服务过程，当、 $n \geq 1$ 时，

${\hat{A}}_{n} (t) \equiv \frac{N_{a} (n t) - n t}{\sqrt{n}}$ ，

${\hat{S}}_{n} (t) \equiv \frac{N_{s} (n t / ρ_{n}) - n t}{\sqrt{n}} = \frac{N_{s} (n t / ρ_{n}) - n t / ρ_{n}}{\sqrt{n}} + \frac{\sqrt{n}}{\sqrt{n} - 1} t$ ，

所以当 $n \to \infty$ 时，在空间中，

$({\hat{A}}_{n}, {\hat{S}}_{n}) \Rightarrow (B_{a}, B_{s} + e)$ ，

其中 $B_{a}$ 和 $B_{s}$ 是相互独立的布朗运动，

因此在D空间中， ${\hat{A}}_{n} - {\hat{S}}_{n} \Rightarrow B_{a} - B_{s} - e$ ，

其次应用 [11] 中的定理9.3.4以及连续映射定理，当 $n \to \infty$ 时，得：

${\hat{Q}}_{n} \Rightarrow R (\cdot) \equiv R (\cdot; - 1, c_{a}^{2} + c_{s}^{2})$ ，且 ${\hat{Q}}_{n} \Rightarrow R (Λ_{f} (\cdot))$ 。

$D_{n} (t)$ 代表第n个系统中的离去过程，

$\begin{matrix} {\hat{W}}_{n} (t) \equiv \frac{W_{n} (n t)}{\sqrt{n}} = \inf {u \geq 0 : D_{n} (n t + u \sqrt{n}) - D_{n} (n t) \geq Q_{n} (n t)} \\ = \inf {u \geq 0 : (D_{n} (n t + u \sqrt{n}) - D_{n} (n t)) / \sqrt{n} \geq Q_{n} (n t) / \sqrt{n}} \\ = \inf {u \geq 0 : {\hat{D}}_{n, t} (u) \geq {\hat{Q}}_{n} (t)} \end{matrix}$ ,

其中 ${\hat{D}}_{n, t} (u) \equiv \frac{D_{n} (n t + u \sqrt{n}) - D_{n} (n t)}{\sqrt{n}}$ 。

在D空间中，当 $n \to \infty$ 时， ${\hat{Q}}_{n} \Rightarrow R (Λ_{f} (\cdot))$ 。

$B_{n} (t)$ 是 $[0, t]$ 时间内忙的服务台。

$D_{n} (n t) = N_{s} (ρ_{n}^{- 1} B_{n} (Λ_{n} (n t)))$ , $t \geq 0$

根据 ${\tilde{Λ}}_{n, t} (u) \to λ_{f} (t) u$ 以及 [11] 中的定理9.3.4，可得：

$\frac{B_{n} (Λ_{n} (n t + u \sqrt{n})) - B_{n} (Λ_{n} (n t))}{\sqrt{n}} \to u λ_{f} (t)$ ,

由 ${\bar{N}}_{s, n} \to e$ ， ${\hat{N}}_{s, n} \Rightarrow c_{s} B_{s}$ 得 ${\hat{D}}_{n, t} (u) \to u λ_{f} (t)$ 。

由 ${\hat{Q}}_{n} \Rightarrow \hat{Q}$ ，及 $\hat{W} (t) \equiv \frac{\hat{Q} (t)}{λ_{f} (t)}$ ， $\hat{Q} (t) \equiv R (Λ_{f} (t); - 1, c_{a}^{2} + c_{s}^{2})$ ，得：

对于每一个 $T > 0$ ，当时， $\sup_{0 \leq t \leq T} {| {\hat{W}}_{n} (t) - ({\hat{Q}}_{n} (t) / λ_{f} (t)) |} \Rightarrow 0$ .

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

在 $D^{2}$ 空间中，当 $n \to \infty$ 时，有 $({\hat{Q}}_{n}, {\hat{W}}_{n}) \Rightarrow (\hat{Q}, \hat{W})$ 。

4. 总结

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

参考文献

参考文献

[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

为你推荐

友情链接