田龙妹,赵 宁,刘文奇

(昆明理工大学 理学院,云南 昆明 650500)

为了提高随机服务系统中顾客的满意度,本文研究可购买优先权的M/G/1排队系统的顾客进队策略,即顾客到达系统后可以通过购买优先权获得优先服务的资格。

具有优先权队列的排队系统在通信、计算机网络以及各大主题游乐园被广泛应用[1-5],自20世纪60年代起得到很多学者关注。Hassin[6]研究了具有优先权的M/M/1排队系统,得到在完全可见情形下顾客选择进入优先权队列的纯阈值策略和混合阈值策略;Lillo[7]研究了具有优先权的M/G/1排队系统的优化运行策略,证明了平稳最优策略是一个双阈值控制策略;黄文业等[8]研究了非抢占的具有优先权的M/G/1排队系统,得出系统稳定条件下优先权队列和普通队列的各种指标的理论结果。

具有优先权的重申队列排队系统是一类特殊的有优先权的排队系统,顾客到达系统后如果发现服务器繁忙,则进入重申队列并任意排序,重申队列的顾客在经历某个随机时间后重新访问服务器。通常首次访问系统的顾客被赋予优先权,相对重申队列的顾客优先获得服务[9]。Choi[9]研究了具有重申队列系统以及优先权的M/G/1排队系统,得到优先权队列和重申队列中请求的联合母函数。Iravani[4]研究了带优先权且顾客没有耐心的排队问题,得到平稳状态下系统的性能指标。Shan[10]研究了具有抢占优先权和重申队列的M/G/1排队系统,得到优先权队列和重申队列的平稳概率分布和一些性能指标。

近年来,排队系统在很多领域得到广泛应用。王小农等[11]研究了自动化立体车库中的M/G/N排队系统,分析了车位分配时顾客排队队长及出入车库的效率等问题;曹雷等[12]基于排队系统相关理论,研究了导弹防御系统的效能问题,得出有效提高导弹防御系统效能的措施。Xu等[13]研究了完全不可见情形下具有抢占优先权的M/G/1排队系统,得到了纳什均衡策略和社会最优策略。

现实中有的服务被中断后能够比较容易启动后续的服务,例如清洗汽车的服务,这类服务系统可以采用抢占优先权的服务规则。然而有的服务中断成本较高,例如芯片加工过程涉及很多化学反应,如果加工过程被中断,可能导致元件性能下降,甚至报废,为了避免较大的损失,这类服务一般采取非抢占的服务规则;另外,在大型娱乐公园,例如过山车、海盗船,如果娱乐过程中被中断,会引起顾客恐惧和不适,这类服务一般也采取非抢占的服务规则。除此之外,在现实生活存在很多非抢占的服务。基于此,本文研究非抢占优先权的M/G/1排队系统,通过顾客的个体收益函数分析这类排队系统的进队策略,提高系统中顾客的满意度。

本文第1节介绍可购买优先权的M/G/1排队系统。第2节对完全可见情形进行描述,并从个体平均收益的角度给出优先权队列的阈值。第3节对完全不可见情形进行描述,并给出进入优先权队列的最优概率。第4节通过数值实验分析了完全可见情形下优先权队列的阈值与购买优先权价格的关系,以及完全不可见情形下进入优先权队列的策略与购买优先权价格的关系。第5节为结论。

1 模型描述

2 完全可见情形

在完全可见情形下,到达顾客可以观察到系统中优先权队列和普通队列的顾客数,以及服务器中的客户类型。当服务器空闲时,到达顾客最优选择进入普通队列;当系统忙碌并且普通队列非空时,到达顾客根据系统中顾客的队长选择是否进入优先权队列。进入优先权队列需要额外支付ξ的费用。

定理1在完全可见的具有非抢占优先权的M/G/1排队系统中,假设某顾客到达系统时观察到系统的状态为(n1,n2,1),该顾客在系统中单位时间的逗留成本为C,则存在阈值

(1)若n1≤K*,则顾客进入优先权队列的平均收益非负;

(2)若n1>K*,则顾客进入优先权队列的平均收益小于零。

证明假设顾客到达时发现系统状态为(n1,n2,1)时,该顾客选择进入优先权队列的平均收益函数为

(1)

令G(n1,n2,1)≥0,得

3 完全不可见情形

在完全不可见情形下,顾客到达系统后不能观察到系统中优先权队列和普通队列中的顾客数,也观察不到服务器服务的顾客类型。假设到达顾客随机选择进入优先权队列和普通队列,其概率分别为q和1-q。该系统的繁忙程度为ρ=λb1,假定系统处于稳定状态,即ρ<1。令系统中第i类顾客数为Ni,平均队长为E(Ni),平均等待时间为E(Wi),i=1,2。

引理1[14]具有非抢占优先权的M/G/1排队系统中,在不可见情形下的优先权顾客和普通顾客的平均等待时间分别为

(2)

由Little法则知E(N1)=λqE(W1),代入式(2)得具有优先权顾客的平均等待时间为

(3)

令N=N1+N2,由均值法得系统中任意顾客的平均等待时间为

(4)

同理,由Little法则得E(N)=λE(W),代入式(4)得

(5)

由于

E(W)=qE(W1)+(1-q)E(W2)

(6)

将式(3)、(5)代入式(6)得

定理2具有非抢占优先权的M/G/1排队系统中,假设到达顾客的单位时间的逗留成本为C,在不可见情形下该顾客的最优进队策略为:

证明在不可见情形下,若顾客选择进入优先权队列的平均等待时间花费为J1=CE(W1),顾客选择进入普通队列的平均等待时间花费为J2=CE(W2)。

如果选择进入优先权队列,则该顾客在系统中的平均等待的费用减少量为

f(q)=J2-J1=C(E(W2)-E(W1))=

(7)

由于函数f(q)关于q单调递增(q∈[0,1]),所以顾客具有拥挤偏好的情形:

4 数值实验

第2节和第3节从理论上分析了具有非抢占优先权的M/G/1排队系统在完全可见和完全不可见情形下顾客的进队策略,本节分别假设服务时间服从指数分布、伽马分布及常数,对理论结果进行数值验证。

4.1 完全可见情形的数值计算

考虑完全可见情形下的M/G/1排队系统,分别假设服务时间服从指数分布X～Exp(3/4)、伽马分布X～Gamma(1/2,3/8)及常数X=4/3。3种服务时间分布下,优先权队列的阈值K*与购买优先权价格ξ的关系如图1所示。

4.2 完全不可见情形的数值计算

由定理2知,在完全不可见情形下顾客的最优进队策略与f(0)、f(1)有关。分别假设服务时间服从指数分布X～Exp(3/4)、伽马分布X～Gamma(1/2,3/8)及常数X=4/3,令C=1。3种服务时间分布下,f(0)、f(1)与系统繁忙程度ρ的关系分别如图2所示。

下面通过数值计算说明3种服务时间分布下的最优进队策略,表1比较了ρ=0.8时顾客的平均剩余服务时间、平均等待时间的费用减少量f(0)、f(1)的值。

表1 ρ=0.8时3种服务时间分布下进队策略的数值分析

由表1可知:

(1)若X=4/3,则有:

(a)当0≤ξ≤32/15时,q=1,顾客进入优先权队列是最优策略,也是占优策略;

(b)当ξ≥32/3时,q=0,顾客进入普通队列是最优策略,也是占优策略;

(2)若X～Exp(3/4),则有:

(a)当0≤ξ≤64/15时,q=1,顾客进入优先权队列是最优策略,也是占优策略;

(b)当ξ≥64/3时,q=0,顾客进入普通队列是最优策略,也是占优策略;

(3)若X～Gamma(1/2,3/8),则有:

(a)当0≤ξ≤32/5时,q=1,顾客进入优先权队列是最优策略,也是占优策略;

(b)当ξ≥32时,q=0,顾客进入普通队列是最优策略,也是占优策略;

5 结束语

本文针对具有非抢占优先权的M/G/1排队系统,分析了完全可见和完全不可见两种情形下顾客购买优先权的策略,得出完全可见情形下顾客进入优先权队列的阈值,完全不可见情形下进入优先权队列的最优进队策略,并通过计算服务时间服从指数分布、伽马分布和常数3种情况下顾客的最优进队策略,验证了完全可见情形下优先权队列的阈值与购买优先权价格呈现线性递减的关系,以及在不可见情形下购买优先权的价格与进入优先权队列的关系。在具有非抢占优先权的随机服务系统中,顾客基于上述讨论的进队策略进队可以有效提高自身获益。

关于具有优先权的M/G/1排队系统的博弈问题,还可推广到多服务器以及节能系统,以及几乎可见和几乎不可见情形下的博弈问题,未来可以对这些问题进行研究。