Statistics and Application
Vol. 08  No. 01 ( 2019 ), Article ID: 28953 , 11 pages
10.12677/SA.2019.81019

M/M/1 Queue with Negative Customers and Feedback and N-Policy under Bernoulli Schedule

Jinping Xu1, Juntong Li1, Tao Li1, Zhenzhen Xu2

1School of Mathematics and Statistics, Shandong University of Technology, Zibo Shandong

2Weifang Medical University, Weifang Shandong

Received: Feb. 2nd, 2019; accepted: Feb. 14th, 2019; published: Feb. 21st, 2019

ABSTRACT

In this paper, we study an M/M/1 queue with negative customers and feedback and N-policy under Bernoulli schedule. Negative customer removes positive customer being service at the head of the queue. During a normal period, when the system becomes empty, the server either begins an ordinary vacation with probability α ( 0 α 1 ) or takes a working vacation with probability β ( β = 1 α ). When a positive customer completes his/her service, s/he may leave the system with probability p ( 0 p 1 ) or return to the back of the queue waiting for another service with probability p ¯ ( p ¯ = 1 p ). When a vacation ends, if there are at least N customers in the system, the server switches to the normal working level. Otherwise, the server begins another vacation. Using quasi birth and death (QBD) process and matrix geometric solution method, we obtain the steady-state distribution for the queue length. Finally, some numerical examples are presented to show the effect of some parameters on the expected queue length.

Keywords:Bernoulli Schedule, Negative Customers, Ordinary Vacation, Working Vacation, Matrix Geometric Solution

Bernoulli机制下的带有负顾客、反馈和N策略的M/M/1休假排队

徐金萍1,李俊潼1,李涛1,徐真真2

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

2潍坊医学院,山东 潍坊

收稿日期:2019年2月2日;录用日期:2019年2月14日;发布日期:2019年2月21日

摘 要

本文研究在Bernoulli机制下的带有负顾客、反馈和N策略的M/M/1休假排队系统,负顾客抵消队首正在接受服务的正顾客。在正规期,若系统中没有正顾客,服务台以概率 α ( 0 α 1 ) 进入普通休假,或以概率 β ( β = 1 α ) 进入工作休假。顾客在服务完成后以概率 p ( 0 p 1 ) 永远离开系统,或者以概率 p ¯ ( p ¯ = 1 p ) 反馈到队尾继续等待服务。在休假期间,当顾客数大于等于N时,休假期结束。反之,则服务台继续休假。利用拟生灭过程和矩阵几何解的方法,得到了系统的稳态队长。最后,通过数值例子来说明一些参数对系统的影响。

关键词 :Bernoulli机制,负顾客,普通休假,工作休假,矩阵几何解

Copyright © 2019 by author(s) 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] 。在2002年,Servi和Finn [2] 首次提出半休假策略并研究了M/M/1/MV排队,即在休假期间服务员以低于正常期的服务率接待顾客,而不是对顾客完全停止服务,这类休假叫做工作休假(Working Vacation, WV)。这意味着,在休假期间仍保持一部分服务能力用于接待顾客,另一部分服务能力可进行缓冲调整或用于其他辅助任务。与经典的休假排队相比,工作休假可以更有效地保证系统的运行,达到减少系统损耗和减轻系统负载的双重作用,即在系统中,当主要工作相对较少时,可从事其他辅助工作。若是休假期间的服务率减小为零时,工作休假排队就变成了经典休假排队。因此,工作休假排队是经典休假排队的一种推广,工作休假策略允许服务员灵活的在高低速服务中转换,使得服务系统更加的接近实际,应用更广泛。对于工作休假排队模型,许多学者将它进行了推广。Wu和Takagi [3] 将M/M/1/MV排队模型扩展到M/G/1/MV排队模型,Baba [4] 利用矩阵几何解法研究了工作休假的GI/M/1排队模型,Krishnamoorthy 和Sreenivasan [5] [6] 分析了M/M/2的工作休假排队模型。

反馈机制也是排队论中研究的重要因素,尤其是Bernoulli反馈机制,被广泛应用于计算机分时操作系统和无线电通讯网络系统中。带有反馈的休假排队系统是经典休假排队系统服务机制发生变化的一种推广,即顾客到达系统后并不一定经过一次服务后就离开系统,可能经过多次,服务次数是由反馈机制决定的,详见参考文献 [7] [8] [9] 。刘名威和马永开 [10] 研究了Bernoulli反馈的N策略Geom/G/1排队系统的队长分布,刘红丹等 [11] 研究了有负顾客且Bernoulli反馈的M/M/C工作休假排队系统。

在本文中,我们通过Bernoulli控制策略将普通休假和工作休假结合在一起,即在正规期,若系统中无正顾客,服务员以概率 α 进入普通休假状态,或者以概率 β 进入工作休假状态,其中 0 α , β 1 α + β = 1 。在此情形下,我们还考虑了负顾客、反馈机制和N策略:负顾客抵消队首正在接受服务的正顾客;顾客在服务完成后以概率 p ( 0 p 1 ) 永远离开系统,或者以概率 p ¯ ( p ¯ = 1 p ) 反馈到队尾继续等待服务;在休假期间,当顾客数大于等于N时,休假期结束;反之,则服务台继续休假。

本节以下各节内容安排如下:第2节,我们给出了模型描述,并得到了QBD的正常返条件;第3节,利用最小非负解矩阵R,我们得到了不同状态下队长的平稳分布;第4节,通过数值例子来说明一些参数对系统队长的影响;第5节,结论。

2. 模型的描述

在M/M/1休假排队系统中引入负顾客、反馈机制和N策略,该排队模型具体描述如下:

1) 在系统中具有正、负两类顾客,这两类顾客的到达时间均服从泊松分布,参数分别为 λ ε

2) 负顾客本身不接受服务且带RCH抵消策略,即当负顾客到达时抵消队首正在接受服务的正顾客。若系统中没有正顾客,则负顾客没有影响并自动消失。

3) 在正规期,若系统中没有正顾客时,服务台以概率 α 进入一个随机长度为V的普通休假期,或者以概率 β 进入一个随机长度为W的工作休假期。工作休假时间和普通休假时间分别服从参数为 θ γ 的指数分布。若休假结束时,系统中仍没有顾客,服务台则开始一个新的休假。在工作休假期间,服务台不停止服务,而是以较低的服务速率接待正顾客。在普通休假期间,服务台则停止服务。

4) 在正规期和工作休假期,服务台对正顾客的服务时间分别服从参数为 μ η 的指数分布,其中 μ η

5) 按照先到先服务的原则,正顾客每服务完成一次后,以概率p永远离开系统,或者以概率 p ¯ ( p ¯ = 1 p ) 反馈到队尾等待再一次服务。

6) 系统中引入N策略休假原则:当普通休假和工作休假结束时,如果系统中的顾客数大于或等于N (N事先设定),服务台立刻停止休假进入正规期。如果系统中的顾客数小于N,那么服务台的服务状态不变。

另外,假设正、负顾客到达时间间隔,正规忙期和工作休假期服务时间,普通休假时间,和工作休假时间均相互独立的,服务规则为先到先服务(FCFS)。

Q ( t ) 表示t时刻系统中的正顾客数,

J ( t ) = { 0 , t 1 , t 2 , t

{ Q ( t ) , J ( t ) } 是一个拟生灭过程,状态空间为

Ω = { ( k , j ) , k 1 , j = 0.1.2 } { ( 0 , 0 ) } { ( 0 , 1 ) }

如果将状态按字典序排列拟生灭过程 { Q ( t ) , J ( t ) } 的最小生成元 Q 可表示为下列分块矩阵形式

Q = 0 1 2 N 2 N 1 N [ A 00 C 0 B 0 A 0 C B A 0 C B A 0 C B A 0 C B A C ] (1)

其中

A 00 =[ λ 0 0 0 0 0 0 0 λ ] C 0 =[ λ 0 0 0 0 0 0 0 λ ]

B 0 =[ 0 0 0 α( pμ+ε ) 0 β( pμ+ε ) 0 0 pη+ε ] A 0 =[ λ 0 0 0 ( λ+pμ+ε ) 0 0 0 ( λ+pη+ε ) ]

C=[ λ 0 0 0 λ 0 0 0 λ ] B=[ 0 0 0 0 pμ+ε 0 0 0 pη+ε ]

A = [ ( λ + γ ) γ 0 0 ( λ + p μ + ε ) 0 0 θ ( λ + p η + ε + θ ) ]

在拟生灭模型的分析中,考虑矩阵二次方程

R 2 B + R A + C = 0 (2)

其中R为率阵,它是二次方程的最小非负解。

定理1 当 ρ = λ p μ + ε < 1 时,方程(2)有最小非负解

R = [ r 1 r 2 0 0 r 3 0 0 r 4 r 5 ]

其中, r 1 = λ λ + γ r 2 = r 3 = λ p μ + ε

r 4 = θ r 5 ( p μ + ε ) ( 1 r 5 ) ,

r 5 = ( λ + p η + ε + θ ) ( λ + p η + ε + θ ) 2 4 λ ( p η + ε ) 2 ( p η + ε ) .

证明:矩阵 A , B , C 都是下三角矩阵,可以设 R = [ R 1 0 R 2 R 3 ] ,其中 R 1 , R 2 , R 3 都是 2 × 2 阶矩阵。将其代

入矩阵方程(2),我们可得:

[ 0 0 0 0 ] = R 1 2 [ 0 0 0 p μ + ε ] + R 1 [ ( λ + γ ) γ 0 ( λ + p μ + ε ) ] + [ λ 0 0 λ ]

[ 0 0 0 0 ] = ( R 2 R 1 + R 3 R 2 ) [ 0 0 0 p μ + ε ] + R 2 [ ( λ + γ ) γ 0 ( λ + p μ + ε ) ] + R 3 [ 0 θ ] ,

[ 0 0 0 0 ] = R 3 2 ( p η + ε ) + R 3 [ ( λ + p η + ε + θ ) ] + λ .

整理得:

λ ( λ + γ ) r 1 = 0

( p μ + ε ) ( r 1 r 2 + r 2 r 3 ) + γ r 1 ( λ + p μ + ε ) r 2 = 0

( p μ + ε ) r 3 2 ( λ + p μ + ε ) r 3 + λ = 0 (3)

( p μ + ε ) ( r 3 r 4 + r 4 r 5 ) + γ r 1 ( λ + p μ + ε ) r 4 + θ r 5 = 0

( p η + ε ) r 5 2 ( λ + p η + ε + θ ) r 5 + λ = 0

解(3)中的第一个方程得。解(3)中的第三个方程得到一个根为 ρ ,另一个根为1(舍去)。要使率阵R有最小非负解,需 r 3 = ρ = λ p μ + ε ρ < 1 。将 r 1 r 3 代入(3)中的第二个方程得 r 2 = λ p μ + ε 。之后再解(3)中的第五个方程得到其中一个根为 r 5 ,另一个根大于1 (舍去),即 r 5 = r = ( λ + p η + ε + θ ) ( λ + p η + ε + θ ) 2 4 λ ( p η + ε ) 2 ( p η + ε ) 。将 r 3 代入(3)中的第四个方程可得 r 4 = θ r 5 ( p η + ε ) ( 1 r 5 ) 。容易验证满足:

( λ + θ ) + ( p η + ε ) ( 1 r ) = p η + ε + θ 1 r = λ r .

证毕。

定理2QBD过程 { Q ( t ) , J ( t ) , t 0 } 正常返当且仅当 ρ = λ p μ + ε 1

证明:首先,假设

G = A + B + C = [ γ γ 0 0 0 0 0 θ θ ]

根据文献 [12] 定理2.5可得,若G不可约, π 是G的平稳概率向量,即 π G = 0 π e = 1 ,则 S P ( R ) 1 ,当且仅当 π B e π C e π = [ 0 1 0 ]

( 0 1 0 ) [ 0 0 0 0 p μ + ε 0 0 0 p η + ε ] [ 1 1 1 ] ( 0 1 0 ) [ λ 0 0 0 λ 0 0 0 λ ] [ 1 1 1 ] .

通过计算求得正常返条件 p μ + ε λ

证毕。

3. 系统队长的性能指标

ρ 1 ( Q , J ) 表示过程 { Q ( t ) , J ( t ) } 的稳态极限,记它的分布为

, π k = ( π k 0 , π k 1 , π k 2 ) , k 1 ,

π k j = P { Q = k , J = j } = lim t P { Q ( t ) = k , J ( t ) = j } , ( k , j ) Ω

定理3当 ρ = λ p μ + ε 1 时, ( Q , J ) 的稳态分布是

k N 1 时,

π k 0 = π N 1 0 r 1 k N + 1 ,

π k 1 = r 2 r 1 r 3 ( r 1 k N + 1 r 3 k N + 1 ) π N 1 0 + r 3 k N + 1 π N 1 , 1 + r 4 r 3 r 5 ( r 3 k N + 1 r 5 k N + 1 ) π N 1 , 2 , (4)

π k 2 = π N 1 , 2 r 5 k N + 1 ;

k N 1 时,

π k 0 = α ( p μ + ε ) λ π 11 , (5)

π k 1 = 1 ρ k 1 ρ π 11 ,其中 ρ = λ p μ + ε (6)

π k 2 = π 12 ( π 12 π 02 ) 1 q k 1 q ,其中 q = λ p η + ε (7)

π N 1 , 0 = π N 2 , 0 , (8)

π N 1 , 1 = λ p μ + ε π N 2 , 1 + λ p μ + ε π N 1 , 0 + r 4 π N 1 , 2 , (9)

π N 1 , 2 = λ λ + p η + ε ( p η + ε ) r 5 π N 2 , 2 ; (10)

π 02 = β ( p μ + ε ) λ ( p η + ε ) K π 11 , (11)

π 12 = K π 02 , (12)

其中 K = q N 1 ( q r 5 ) q ( 1 r 5 ) q N 1 ( q r 5 ) ( 1 r 5 ) ,并且 π 11 可以通过正规化条件获得。

证明:利用矩阵几何解的方法(参考文献 [12] ),我们可以得到

π k = ( π k 0 , π k 1 , π k 2 ) = π N 1 R k N + 1 = ( π N 1 , 0 , π N 1 1 , π N 1 , 2 ) R k N + 1 , k N 1 . (13)

k N 1 时,

R k N + 1 = [ r 1 k N + 1 r 2 r 1 r 3 ( r 1 k N + 1 r 3 k N + 1 ) 0 0 r 3 k N + 1 0 0 r 4 r 3 r 5 ( r 3 k N + 1 r 5 k N + 1 ) r 5 k N + 1 ] (14)

R k N + 1 代入上述方程中,我们可以得到(4)。同时, π 0 , π 1 , , π N 1 满足

( π 0 , π 1 , , π N 1 ) B [ R ] = 0 ,(15)

其中,

B [ R ] = 0 1 2 N 2 N 1 [ A 00 C 0 B 0 A 0 C B A 0 C B A 0 C B A 0 + R B ] (16)

A 0 + R B = [ λ λ 0 0 ( p μ + ε ) 0 0 θ r 5 1 r 5 ( λ + p η + ε ) + ( p η + ε ) r 5 ]

因此,我们可以得到

λ π 00 + α ( p μ + ε ) π 11 = 0 , (17)

λ π 00 λ π 10 = 0 , (18)

λ π k 1 , 0 λ π k 0 = 0 , ( 1 k N 2 ) , (19)

( λ + p μ + ε ) π 11 + ( p μ + ε ) π 21 = 0 , (20)

λ π k 1 , 1 ( λ + p μ + ε ) π k 1 + ( p μ + ε ) π k + 1 , 1 = 0 , ( 1 k N 2 ) , (21)

λ π 02 + β ( p μ + ε ) π 11 + ( p η + ε ) π 12 = 0 , (22)

λ π 02 ( λ + p η + ε ) π 12 + ( p η + ε ) π 22 = 0 , (23)

λ π k 1 , 2 ( λ + p η + ε ) π k 2 + ( p η + ε ) π k + 1 , 2 = 0 , ( 1 k N 2 ) , (24)

λ π N 2 , 0 λ π N 1 , 0 = 0 , (25)

λ π N 2 , 1 + λ π N 1 , 0 ( p μ + ε ) π N 1 , 1 + θ r 5 1 r 5 π N 1 , 2 = 0 , (26)

λ π N 2 , 2 + [ ( p η + ε ) r 5 ( λ + p η + ε ) ] π N 1 , 2 = 0 . (27)

从(17)式到(19)式,我们通过计算可以得到(5)式。从(20)式到(21)式,我们通过计算得到(6)式。(7)式可以从(23)式到(24)式得到。将 r 5 代入(26)式后,并与(25)式和(27)式一起计算,我们可以得到 π N 1 , 0 π N 1 , 2 。通过(7)式、(24)式、(27)式,我们可以得到 π 02 π 12 。在(24)式中,让k等于 N 2 ,利用 π N 3 , 2 π N 2 , 2 π N 1 , 2 ,(12)式可以表示出来。将(12)式代入(22)式中,我们可以将 π 02 π 11 表示出来。最后,我们根据正规化条件

j = 0 2 k = 0 π k j = 1 ,

我们可以求得 π 11

证毕。

由定理3的结果可知,系统处于各个状态的概率为

P { I = 0 } = k = 0 π k 0 = k = 0 N 2 π k 0 + k = N 1 π k 0 = ( α ( p μ + ε ) ( N 1 ) λ + α ( p μ + ε ) λ ( 1 r 1 ) ) π 11 ,

P { I = 1 } = k = 1 π k 1 = k = 1 N 2 π k 1 + k = N 1 π k 1 = ( N 2 ) ( 1 ρ ) ρ + ρ N 2 ( 1 ρ ) 2 π 11 + r 2 ( 1 r 2 ) ( 1 r 1 ) π N 1 , 0 + 1 1 r 3 π N 1 , 1 + r 4 ( 1 r 3 ) ( 1 r 5 ) π N 1 , 2 ,

P { I = 2 } = k = 0 π k 2 = k = 0 N 2 π k 2 + k = N 1 π k 2 = π 02 + ( N 2 ) π 12 + ( N 2 ) ( 1 q ) q + q N 2 ( 1 q ) 2 + 1 1 r 5 π N 1 , 2 .

稳态下系统中的平均顾客数为

E [ L ] = k = 0 k ( π k 0 + π k 2 ) + k = 1 k π k 1 = k = 0 N 2 k ( π k 0 + π k 2 ) + k = 1 N 2 k π k 1 + ( 1 r 3 ) 2 + r 2 ( 2 r 1 r 3 ) ( 1 r 1 ) 2 ( 1 r 3 ) 2 π N 1 , 0 + 1 ( 1 r 3 ) 2 π N 1 , 1 + ( 1 r 5 ) 2 + r 4 ( 2 r 5 r 3 ) ( 1 r 5 ) 2 ( 1 r 3 ) 2 π N 1 , 2 ,

则系统中顾客的等待时间为

E [ W ] = E [ L ] λ .

4. 数值分析

本文中,令 λ = 1.5 η = 0.8 γ = 0.6 N = 2 以平均队长 E ( L ) 作为研究对象,我们给出几个数值实例来演示普通休假状态概率 α 、正规期服务率 μ 对系统的影响。

Figure 1. E ( L ) with change of α (three different of θ )

图1. E ( L ) α 的变化趋势(三种不同的 θ )

μ = 3 ε = 2 p = 0.5 图1描绘了普通休假状态概率 α 对平均队长 E ( L ) 的影响。从图中,我们发现 E ( L ) α 的增大而增大。这是因为服务员在休假期内是不发生服务的,普通休假的概率越大,系统中的顾客数也会越多。而且 θ 越大,工作休假时间越短,系统中的顾客数越少。

Figure 2. E ( L ) with change of α (three different of )

图2. E ( L ) α 的变化趋势(三种不同的 ε )

μ = 3 θ = 0.4 p = 0.5 图2说明在三种不同的负顾客到达率 ε 下,平均队长 E ( L ) 随普通休假状态概率 α 的增大而增大。由于服务员在休假期内是不发生服务的,因此普通休假的概率越大,系统中的顾客数也会越多。因为负顾客会抵消正在服务的顾客,所以负顾客到达率 越大,系统中的顾客数越少。

Figure 3. E ( L ) with change of μ (three different of θ )

图3. E ( L ) μ 的变化趋势(三种不同的 θ )

p = 0.5 α = 0.3 β = 0.7 ε = 2 图3描绘了正规期服务率 μ 对平均队长 E ( L ) 的影响。随着 μ 的增大,我们可以发现平均队长 E ( L ) 在减少。在其他条件相同的情况下,平均队长 E ( L ) θ 的增大而减小。

Figure 4. E ( L ) with change of μ (three different of p)

图4. E ( L ) μ 的变化趋势(三种不同的p)

α = 0.3 β = 0.7 ε = 2 θ = 0.4 图4描绘了正规期服务率 μ 对平均队长 E ( L ) 的影响。随着 μ 的增大,我们可以发现平均队长 E ( L ) 在减少。反馈概率p越大,系统中顾客在服务完成后离开系统的概率就越大,因此在其他条件相同的情况下,系统中的顾客数随着反馈概率p的增大而减少。

5. 结论

本文不同于普通的Bernoulli控制的M/M/1休假模型,而是在此基础上进一步研究了负顾客、反馈机制和N策略对模型的影响。通过对平均队长的分析,可以直观的看到各因素对系统的影响。特别地,当 ε = 0 p = 0 N = 1 时,该系统就退化为普通的Bernoulli控制的M/M/1休假模型。

文章引用

徐金萍,李俊潼,李 涛,徐真真. Bernoulli机制下的带有负顾客、反馈和N策略的M/M/1休假排队
M/M/1 Queue with Negative Customers[J]. 统计学与应用, 2019, 08(01): 165-175. https://doi.org/10.12677/SA.2019.81019

参考文献

  1. 1. Tian, N. and Zhang, Z.G. (2006) Vacation Queueing Models-Theory and Applications. Springer, New York. https://doi.org/10.1007/978-0-387-33723-4

  2. 2. Servi, L.D. and Finn, S.G. (2002) M/M/1 Queues with Working Vacations (M/M/1/WV). Performance Evaluation, 50, 41-52. https://doi.org/10.1016/S0166-5316(02)00057-3

  3. 3. Wu, D.-A. and Takagi, H. (2006) M/G/1 Queue with Mul-tiple Working Vacations. Performance Evaluation, 63, 654-681. https://doi.org/10.1016/j.peva.2005.05.005

  4. 4. Baba, Y. (2005) Analysis of a GI/M/1 Queue with Multiple Working Vacations. Operations Research Letters, 33, 201-209. https://doi.org/10.1016/j.orl.2004.05.006

  5. 5. Krishnamoorthy, A. and Sreenivasan, C. (2012) An M/M/2 Queueing System with Heterogeneous Servers Including one Vacationing Server. Calcutta Statistical Association Bulletin, 64, 253-254. https://doi.org/10.1177/0008068320120105

  6. 6. Krishnamoorthy, A. and Sreenivasan, C. (2012) An M/M/2 Queueing System with Heterogeneous Servers Including One with Working Vacation. International Journal of Sto-chastic Analysis, 2012, Article ID: 145867. https://doi.org/10.1155/2012/145867

  7. 7. Rege, K. (1993) On the M/G/1 Queue with Bernoulli Feedback. Oper-ations Research Letters, 14, 163-170. https://doi.org/10.1016/0167-6377(93)90028-F

  8. 8. Kumar, B.K., Arivudainambi, D. and Krishnamoorthy, A. (2006) Some Results on a Generalized M/G/1 Feedback Queue with Negative Customers. Operations Research Letters, 143, 277-296.

  9. 9. 顾庆凤, 朱翼隽. 具有Bernoulli 反馈的M/M/1 工作休假排队系统[J]. 成都信息工程学院, 2008, 23(4): 465-468.

  10. 10. 刘名威, 马永开. Bernoulli反馈的N策略Geom/G/1排队系统的队长分布[J]. 系统工程, 2008, 26(12): 103-109.

  11. 11. 刘红丹, 吕胜利, 李丹丹. 有负顾客且Bernoulli反馈的M/M/C工作休假排队系统[J]. 郑州大学学报, 2016, 45(2): 14-18.

  12. 12. 田乃硕, 岳德全. 拟生灭过程与矩阵几何解[M]. 北京: 科学出版社, 2002: 22-26.

期刊菜单