ABSTRACT

In this paper, we considered an M/M/1 retrial queue with working vacation and feedback. In order to obtain the necessary and sufficient condition for system to be stable, the matrix-analytic method is used. The stationary probability distribution and some performance measures were also derived. Then we give the conditional stochastic decomposition for the queue length in the orbit when the server is busy. Finally, the model parameters on the system's characteristics are presented by some numerical examples.

Keywords:Retrial, Working Vacation, Collision, Conditional Stochastic Decomposition

带有反馈的M/M/1重试工作休假排队模型

李俊潼，李涛，徐金萍

山东理工大学数学与统计学院，山东 淄博

收稿日期：2019年1月22日；录用日期：2019年2月6日；发布日期：2019年2月13日

摘 要

研究带有反馈、重试和工作休假的M/M/1排队模型：当系统为空时，服务员进入工作休假，以低速率提供服务，若顾客到达时服务员忙，则顾客进入重试组等待，接收服务完毕的顾客以概率p离开系统或以概率 $\bar{p}\left(\bar{p}=1-p\right)$ 返回系统重新排队。对该模型，运用拟生灭过程和矩阵几何解的方法，得到平稳队长及一些相应指标，并给出队长分解，最后，利用数值例子进行解释。

关键词 :重试，工作休假，反馈，随机条件分解

Copyright © 2019 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在我们日常生活中，经常会出现拥挤堵塞的情况，比如电话占线、银行服务、交通堵塞等情况，排队论就是解决这类问题的有效工具。

在排队论的研究进程中，有关休假系统和重试系统已经被广泛研究，我们可以通过Tian和Zhang [1] 了解到一些基本模型。休假排队策略允许服务员在某些时刻不接待顾客，这些暂时停止提供服务的状态统称为休假；重试就是指当顾客到达系统时发现服务员正在工作，那么顾客就会进入到一个重试组(通常称之为orbit)等待，过一段时间之后再重新向服务员发出服务请求。关于重试的一些文献可以参考 [2] [3] [4] 。而在普通休假的基础上，Servi和Finn [5] 首次提出了工作休假的概念，并研究了带有工作休假的M/M/1模型，工作休假是指在休假过程中，服务员不完全停止服务，而是转为低速率提供服务。在此基础上，Do [6] 研究了带有重试和工作休假的M/M/1排队模型。当下，将重试和工作休假结合的模型研究已经非常广泛，一些其他有价值的结论可以参考Li et al. [7] 。在实际的应用中，顾客的行为是多样的，顾客接受服务后也可能重新回到系统再次申请服务，这种情况可以用具有“反馈”的排队系统描述。如多路的远程通讯系统，如果给用户端的消息出错，那么用户端则会向服务器重新发送一次服务请求。2002年B. Krishna Kumar等 [8] 研究了顾客有伯努利反馈、服务器有启动失败且重试时间服从一般分布的M/G/1重试排队系统。2005年Kailash C. Madan和Mohammad Al-Rawwash [9] 研究了有顾客反馈的M/G/1可选择单重休假排队系统。

本文主要研究带有反馈的M/M/1重试工作休假排队模型。采用嵌入Markov链法，给出系统存在稳态的充要条件，求出了平均队长等系统指标，此外还讨论了稳态下队长的随机条件分解，最后对给定的某些数值做出图形变换趋势及解释。

2. 模型描述

我们考虑研究带有反馈的M/M/1重试工作休假排队模型，关于模型的一些细节描述如下：

1) 顾客的到达时间服从参数为 $\lambda$ 的泊松过程。

2) 正常服务期，服务员的服务速率服从参数为 $\mu$ 的指数分布，当重试组中没有顾客时，服务员开始一段时间为V的工作休假，且工作休假时间服从参数为 $\theta$ 的指数分布。在工作休假期间，服务员以低速率 $\eta$ 提供服务，且 $\eta <\mu$ 。当一个工作休假结束，若重试组中有顾客，则开始一个新的忙期，若重试组中没有顾客，则开始一个新的工作休假。

3) 当顾客到达系统发现服务员在忙，则顾客进入重试组等待，重试组中的顾客只有排在队列最前面的才能对服务器进行重试，直到重试成功并接受服务，重试时间服从参数为 $\alpha$ 的指数分布。

4) 顾客接受服务完毕后瞬间以概率 $p\left(0\le p\le 1\right)$ 离开系统，或以概率 $\bar{p}\left(\bar{p}=1-p\right)$ 返回重试组重新排队等待服务。

另外，我们假设顾客的到达时间、重试时间以及系统的休假时间、正常工作期和工作休假期的服务时间都是相互独立的。

令 $Q\left(t\right)$ 表示t时刻重试组中的顾客数， $J\left(t\right)$ 表示t时刻服务员的状态，则服务员的四个状态如下：

$J\left(t\right)=\{\begin{array}{l}1,工作休假期,服务员忙\\ 2,工作休假期,服务员闲\\ 3,正常工作期,服务员忙\\ 4,正常工作期,服务员闲\end{array}$

则随机过程 $\left\{Q\left(t\right),J\left(t\right)\right\}$ 是一个以 $\Omega =\left\{\left(n,j\right),n=0;j=1,2,3\right\}\cup \left\{\left(n,j\right),n\ge 1;j=1,2,3,4\right\}$ 为状态空间的拟生灭(QBD)过程。

该过程的最小生成元矩阵可以写成分块模式如下：

$\tilde{Q}=\left(\begin{array}{ccccc}{B}_1& A_0& & & \\ A_2& A_1& A_0& & \\ & A_2& A_1& A_0& \\ & & \ddots & \ddots & \ddots \end{array}\right)$

其中

$B_1=\left(\begin{array}{cccc}-\left(\lambda +\eta +\theta \right)& p\eta & \theta & 0\\ \lambda & -\lambda & 0& 0\\ 0& p\mu & -\left(\lambda +\mu \right)& 0\\ 0& 0& 0& 0\end{array}\right)$

$A_0=\left(\begin{array}{cccc}\lambda & \bar{p}\eta & 0& 0\\ 0& 0& 0& 0\\ 0& 0& \lambda & \bar{p}\mu \\ 0& 0& 0& 0\end{array}\right)$

$A_2=\left(\begin{array}{cccc}0& 0& 0& 0\\ \alpha & 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& \alpha & 0\end{array}\right)$

$A_1=\left(\begin{array}{cccc}-\left(\lambda +\eta +\theta \right)& p\eta & \theta & 0\\ \lambda & -\left(\lambda +\alpha +\theta \right)& 0& \theta \\ 0& 0& -\left(\lambda +\mu \right)& p\mu \\ 0& 0& \lambda & -\left(\lambda +\alpha \right)\end{array}\right)$

3. 系统存在稳态的充要条件及稳态队长

定理1：QBD过程 $\left\{Q\left(t\right),J\left(t\right)\right\}$ 正常返的充分必要条件是 $\mu \alpha >\left(\lambda +\bar{p}\mu \right)\left(\lambda +\mu \right)$ 。

证明：首先，我们假设

$A=A_0+A_1+A_2=\left(\begin{array}{cccc}-\left(\eta +\theta \right)& \eta & \theta & 0\\ \lambda +\alpha & -\left(\lambda +\alpha +\theta \right)& 0& \theta \\ 0& 0& -\mu & \mu \\ 0& 0& \lambda +\alpha & -\left(\lambda +\alpha \right)\end{array}\right)$

根据文献 [10] ，定理7.3.1，对行列式进行变换得到QBD正常返条件为：

${\pi }^{\text{*}}\left(\begin{array}{cc}0& 0\\ \alpha & 0\end{array}\right)e>{\pi }^{\text{*}}\left(\begin{array}{cc}\lambda & \bar{p}\mu \\ 0& 0\end{array}\right)e$

其中e为单位列向量， ${\pi }^{\text{*}}$ 为 ${\pi }^{*}\left(\begin{array}{cc}-\mu & \mu \\ \lambda +\alpha & -\left(\lambda +\alpha \right)\end{array}\right)=0$ ， ${\pi }^{\text{*}}e=1$ 的唯一解。经过运算可得QBD的正常返条件为 $\mu \alpha >\left(\lambda +\bar{p}\mu \right)\left(\lambda +\mu \right)$ 。证毕。

定理2：当 $\mu \alpha >\left(\lambda +\bar{p}\mu \right)\left(\lambda +\mu \right)$ 时，矩阵方程 $R^2{A}_2+R{A}_1+A_0=0$ 有最小非负解：

$R=\left(\begin{array}{cccc}{r}_1& r_2& r_3& r_4\\ 0& 0& 0& 0\\ 0& 0& r_5& r_6\\ 0& 0& 0& 0\end{array}\right)$

其中

$r_1=\frac{\left[\left(\lambda +\eta +\theta \right)\left(\lambda +\alpha +\theta \right)-\bar{p}\eta \alpha -p\eta \lambda \right]-\sqrt{\Delta }}{2p\eta \alpha },$

$r_2=\frac{\bar{p}\eta +r_{1}p\eta }{\lambda +\alpha +\theta },$

$r_3=\frac{r_1{r}_2\alpha \theta +r_2\theta }{\left(\lambda +\mu \right)\left(\lambda +\alpha \right)-p\mu -p\mu \lambda -\left(r_6\alpha -r_1\theta \right)\left(\lambda +\alpha \right)},$

$r_4=\frac{r_2\theta +r_{3}p\mu }{\lambda +\alpha },$

$r_5=\lambda \left(\lambda +\alpha +\bar{p}\mu \right),$

$r_6=\lambda p\mu +\bar{p}p{\mu }^2,$

$\Delta ={\left[\bar{p}\eta \alpha -\left(\lambda +\eta +\theta \right)\left(\lambda +\alpha +\theta \right)+p\eta \lambda \right]}^2-4p\eta \alpha \lambda \left(\bar{p}\eta +\lambda +\alpha +\theta \right).$

证明：根据 $A_0,A_1,A_2$ 的结构，我们假设 $R=\left(\begin{array}{cc}{R}_{11}& R_{12}\\ 0& R_{22}\end{array}\right)$ ，其中 $R_{11}$ ， $R_{12}$ 和 $R_{22}$ 都是 $2\times 2$ 的矩阵。把R带入方程 $R^2{A}_2+R{A}_1+A_0=0$ 中得到一系列方程

$\{\begin{array}{l}\left(\begin{array}{cc}0& 0\\ 0& 0\end{array}\right)=R_{11}^2\left(\begin{array}{cc}0& 0\\ \alpha & 0\end{array}\right)+R_{11}\left(\begin{array}{cc}-\left(\lambda +\eta +\theta \right)& p\eta \\ \lambda & -\left(\lambda +\alpha +\theta \right)\end{array}\right)+\left(\begin{array}{cc}\lambda & \bar{p}\eta \\ 0& 0\end{array}\right),\\ \left(\begin{array}{cc}0& 0\\ 0& 0\end{array}\right)=\left(R_{11}{R}_{12}+R_{12}{R}_{22}\right)\left(\begin{array}{cc}0& 0\\ \alpha & 0\end{array}\right)+R_{11}\left(\begin{array}{cc}\theta & 0\\ 0& \theta \end{array}\right)+R_{12}\left(\begin{array}{cc}-\left(\lambda +\mu \right)& p\mu \\ \lambda & -\left(\lambda +\alpha \right)\end{array}\right),\\ \left(\begin{array}{cc}0& 0\\ 0& 0\end{array}\right)=R_{22}^2\left(\begin{array}{cc}0& 0\\ \alpha & 0\end{array}\right)+R_{22}\left(\begin{array}{cc}-\left(\lambda +\mu \right)& p\mu \\ \lambda & -\left(\lambda +\alpha \right)\end{array}\right)+\left(\begin{array}{cc}\lambda & \bar{p}\mu \\ 0& 0\end{array}\right).\end{array}$

由第一个方程，我们可以得到 $R_{11}=\left(\begin{array}{cc}{r}_1& r_2\\ 0& 0\end{array}\right)$ ，同理 $R_{22}=\left(\begin{array}{cc}{r}_5& r_6\\ 0& 0\end{array}\right)$ 可以由第三个方程解得，将 $R_{11}$ 和 $R_{22}$ 代入第二个方程，可以经过计算得到 $R_{12}=\left(\begin{array}{cc}{r}_3& r_4\\ 0& 0\end{array}\right)$ 。证毕。

在稳态条件下，我们有

${\pi }_n=\left({\pi }_{n1},{\pi }_{n2},{\pi }_{n3},{\pi }_{n4}\right),n\ge 0,$

${\pi }_{nj}=P\left\{Q=n,J=j\right\}=\underset{t\to \infty }{\lim }P\left\{Q\left(t\right)=n,J\left(t\right)=j\right\},\left(n,j\right)\in \Omega ,$

值得注意的是，当重试组中没有顾客时，正常工作期服务员忙的概率是0，因此 ${\pi }_{04}=0$ 。

定理3：如果 $\mu \alpha >\left(\lambda +\bar{p}\mu \right)\left(\lambda +\mu \right)$ ，则QBD过程 $\left\{Q\left(t\right),J\left(t\right)\right\}$ 的平稳分布由下式给出：

$\{\begin{array}{l}{\pi }_{n1}={\pi }_{01}{r}_1^n,n\ge 1,\\ {\pi }_{n2}={\pi }_{01}{r}_1^{n-1}{r}_2,n\ge 1,\\ {\pi }_{n3}={\pi }_{01}\left[\frac{r_3}{r_5-r_1}\left(r_5^n-r_1^n\right)\right]+{\pi }_{03}{r}_5^n,n\ge 1,\\ {\pi }_{n4}={\pi }_{01}\left[r_4{r}_1^{n-1}+\frac{r_3{r}_6}{r_5-r_1}\left(r_5^{n-1}-r_1^{n-1}\right)\right]+{\pi }_{03}{r}_5^{n-1}{r}_6,n\ge 1,\end{array}$ (1)

并且

$\{\begin{array}{l}{\pi }_{02}=\frac{\left(\lambda +\eta +\theta \right)+r_2\alpha }{\lambda }{\pi }_{01},\\ {\pi }_{03}=\frac{r_4\alpha +\theta }{\left(\lambda +\mu \right)-r_6\alpha }{\pi }_{01}.\end{array}$ (2)

其中 ${\pi }_{01}$ 可由归一化条件求得。

证明：由

${\pi }_n=\left({\pi }_{n1},{\pi }_{n2},{\pi }_{n3},{\pi }_{n4}\right)={\pi }_0{R}^n=\left({\pi }_{01},{\pi }_{02},{\pi }_{03},{\pi }_{04}\right)R^n,n\ge 0$

$R^n=\left(\begin{array}{cccc}{r}_1^n& r_1^{n-1}{r}_2& \frac{r_3}{r_5-r_1}\left(r_5^n-r_1^n\right)& r_4{r}_1^{n-1}+\frac{r_3{r}_6}{r_5-r_1}\left(r_5^{n-1}-r_1^{n-1}\right)\\ 0& 0& 0& 0\\ 0& 0& r_5^n& r_5^{n-1}{r}_6\\ 0& 0& 0& 0\end{array}\right),n\ge 1$

将 $R^n$ 代入上述方程，我们可以得到(1)式。并且 ${\pi }_0$ 满足下述方程：

${\pi }_0\left(B_1+R{A}_2\right)=0.$ (3)

通过(3)式我们可以计算得到(2)式。

再由

${\displaystyle \underset{j=1}{\overset{4}{\sum }}{\displaystyle \underset{n=0}{\overset{\infty }{\sum }}{\pi }_{nj}}}=1,$

我们得到 ${\pi }_{01}={\left(1+x+y+z\right)}^{-1}$ 。

其中

$x=\frac{\left(1-r_1\right)\left(\lambda +\eta +\theta +r_2\alpha \right)+\left(r_1+r_2+r_4\right)\lambda }{\lambda \left(1-r_1\right)},$

$y=\frac{\left(r_4\alpha +\theta \right)\left(1-r_5+r_5{r}_6\right)}{\left(1-r_5\right)\left(\lambda +\mu -r_6\alpha \right)},$

$z=\frac{r_3\left(r_5-r_1\right)+r_3{r}_6\left(r_1+r_5\right)}{\left(1-r_5\right)\left(1-r_1\right)\left(r_5-r_1\right)}.$

证毕。

服务员不同状态下的概率如下：

$P_1=P\left\{J=1\right\}={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}{\pi }_{n1}}=\frac{1}{1-r_1}{\pi }_{01},$

$P_2=P\left\{J=2\right\}={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}{\pi }_{n2}}=\frac{r_2}{\left(1-r_1\right)r_1}{\pi }_{01},$

$P_3=P\left\{J=3\right\}={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}{\pi }_{n3}}=\left[\frac{r_3}{\left(1-r_5\right)\left(1-r_1\right)}+\frac{r_4\alpha +\theta }{\left(1-r_5\right)\left[\left(\lambda +\mu \right)-r_6\alpha \right]}\right]{\pi }_{01},$

$P_4=P\left\{J=4\right\}={\displaystyle \underset{n=1}{\overset{\infty }{\sum }}{\pi }_{n4}}=\left\{\frac{r_4}{\left(1-r_1\right)r_1}+\frac{r_3{r}_6\left(r_1+r_5-1\right)}{\left(1-r_1\right)\left(1-r_5\right)r_1{r}_5}+\frac{r_6\left(r_4\alpha +\theta \right)}{\left(1-r_5\right)r\left[\left(\lambda +\mu \right)-r_6\right]}\right\}{\pi }_{01}.$

服务员忙时的概率为：

$P_b=P\left\{J=1\right\}+P\left\{J=3\right\}=P_1+P_3.$

服务员闲时的概率为：

$P_c=P\left\{J=2\right\}+P\left\{J=4\right\}=P_2+P_4=1-P_b.$

用L表示重试组中的顾客数，我们可以得到

$\begin{array}{l}E\left[L\right]={\displaystyle \underset{n=1}{\overset{\infty }{\sum }}n\left({\pi }_{n1}+{\pi }_{n2}+{\pi }_{n3}+{\pi }_{n4}\right)}\\ =\frac{\left(r_1+r_2+r_4\right){\left(1-r_5\right)}^2+\left(1-r_1{r}_5\right)r_3+\left(2-r_1-r_5\right)r_3{r}_6}{{\left(1-r_5\right)}^2{\left(1-r_1\right)}^2}{\pi }_{01}+\frac{r_5+r_6}{{\left(1-r_5\right)}^2}{\pi }_{03}.\end{array}$

用 $\tilde{L}$ 表示系统中的顾客数，我们可以得到

$E\left[\tilde{L}\right]={\displaystyle \underset{n=1}{\overset{\infty }{\sum }}n\left({\pi }_{n2}+{\pi }_{n4}\right)}+{\displaystyle \underset{n=0}{\overset{\infty }{\sum }}\left(n+1\right)\left({\pi }_{n1}+{\pi }_{n3}\right)}=E\left[L\right]+P_1+P_3=E\left[L\right]+P_b.$

4. 随机条件分解

引理1：如果 $\mu \alpha >\left(\lambda +\bar{p}\mu \right)\left(\lambda +\mu \right)$ ，令 $Q_0$ 表示服务员忙时带有反馈和重试的M/M/1排队系统重试组中的条件队长，则 $Q_0$ 有概率母函数如下：

$G_{Q_0}\left(z\right)=\frac{1-r_5}{1-r_{5}z}.$

证明：证明过程与文献 [11] 中引理1相似，此处我们省略证明过程。

令 $Q_b$ 表示本系统orbit中服务忙时的条件队长，如果 $\mu \alpha >\left(\lambda +\bar{p}\mu \right)\left(\lambda +\mu \right)$ ，我们可以得到

$\begin{array}{l}{G}_{Q_b}\left(z\right)={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}P\left\{Q_b=n\right\}}\cdot z^n={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}\frac{{\pi }_{n1}+{\pi }_{n3}}{P_b}}\cdot z^n\\ =\frac{1-r_5}{1-r_{5}z}\cdot \frac{\left[1-r_{5}z+r_{3}z+d\left(1-r_{1}z\right)\right]{\pi }_{01}}{\left(1-r_{1}z\right)\left(1-r_5\right)P_b}=G_{Q_0}\left(z\right)G_{Q_c}(z)\end{array}$

其中， $d=\frac{\lambda +\theta +r_{1}p\eta +r_2\alpha }{\mu }$ 。

因此， $Q_b$ 可以写成两个独立变量的和： $Q_b=Q_0+Q_c$ ，其中 $Q_0$ 可以由引理1得到，并且 $Q_0$ 服从参数为 $1-r_5$ 的指数分布，附加队长 $Q_c$ 也有函数 $G_{Q_c}\left(z\right)$ 。

5. 数值例子

这一部分，在系统稳态的条件下，我们给出一些数值例子来解释平均稳态队长 $E\left[L\right]$ 和服务员忙时的概率 $P_b$ 。在不作为研究变量的情况下，我们给变量赋值为 $\lambda =0.8$ ， $\theta =0.2$ ， $\alpha =0.6$ ， $\mu =2.4$ ， $\eta =0.7$ 。

图1. 重试参数 $\alpha$ 对重试组队长的影响

图2. 重试时间对服务员忙时的概率的影响

图1和图2展示了 $\alpha$ 对队长 $E\left[L\right]$ 和服务员忙时的概率 $P_b$ 的影响，随着 $\alpha$ 的增加，也就意味着重试时间减少。当服务员空闲时，到达的顾客和重试的顾客竞争接受服务，因此，重试时间越短，服务员忙的概率越大，导致 $P_b$ 增加，而队长 $E\left[L\right]$ 减小。我们也可以看出随着p的增加队长 $E\left[L\right]$ 减小，而 $P_b$ 则呈现相反的趋势。

图3. 重试参数 $\eta$ 对重试组队长的影响

图4. 工作休假服务速率 $\eta$ 对服务员忙时的概率的影响

在图3和图4中，我们根据不同工作休假服务速率变化给出了队长 $E\left[L\right]$ 和服务员忙时的概率 $P_b$ 的变化曲线。我们可以看到，随着工作休假服务速率 $\eta$ 的增加，队长 $E\left[L\right]$ 和概率 $P_b$ 都减小，原因是在工作休假期间，服务员没有完全停止工作，而是以低速率继续提供服务，导致曲线呈下降趋势。并且我们可以知道 $p=1$ ，相当于顾客没有反馈行为，因此p越大，对系统的影响越小。

6. 结论

本文讨论了带有反馈、重试和工作休假的M/M/1排队模型，运用矩阵几何解得到系统稳态分布，以及系统稳态队长和忙期概率等指标。最后，通过数值例子分析重试以及工作休假对稳态队长和忙期概率的影响，为决策者做出决策从而使系统达到最优提供了理论依据。

文章引用

李俊潼,李 涛,徐金萍. 带有反馈的M/M/1重试工作休假排队模型
An M/M/1 Retrial Queue with Working Vacation and Feedback[J]. 应用数学进展, 2019, 08(02): 210-218. https://doi.org/10.12677/AAM.2019.82024

参考文献