具有插隊和止步行為的M/M/1/m+1排隊系統(tǒng)的等待時間分析

張元元吳文青唐應(yīng)輝

(1.西南科技大學理學院,四川 綿陽621010; 2.可視化計算與虛擬現(xiàn)實四川省重點實驗室,四川 成都610068; 3.四川師范大學基礎(chǔ)學院,四川 成都610068)

1.引言

在日常生活中存在著大量服務(wù)和被服務(wù)的現(xiàn)象,當?shù)竭_的顧客不能立即得到服務(wù)的情況下就出現(xiàn)了排隊現(xiàn)象.比如在超市購物的顧客等待收銀臺人員對其進行結(jié)賬服務(wù)、銀行取款時的顧客等待柜臺人員對其辦理相關(guān)業(yè)務(wù)、出現(xiàn)故障的機器等待修理工來修理、電話咨詢服務(wù)中電話占線的問題.然而,當排隊等待的隊列過長,有些顧客可能會不進入系統(tǒng),有些顧客可能會選擇插隊.例如,當處于下課高峰期時,來食堂打飯的同學總是試圖找到隊列前面他認識的同學來完成插隊,從而以較短時間完成服務(wù)離開排隊系統(tǒng).然而有些同學會直接放棄食堂吃飯選擇其他方式就餐.當醫(yī)院出現(xiàn)較多排隊掛號的病人時,一些掛號者會試圖插隊盡快完成掛號,從而達到以相對更早的時間就診的目的,或直接選擇其他醫(yī)院.

1987年,Larson[1]從社會公正現(xiàn)象以及社會心理學的角度將插隊行為引入到排隊系統(tǒng)中,并使用“slips” 和“skips”來具體描述具有插隊行為的排隊系統(tǒng).Kleinrock[2],Afeche和Mendelson[3],以及Lui[4]分析隊列中的顧客其具體的位置由顧客支付金錢多少來決定的排隊模型.通過引入費用函數(shù),作者推導出顧客需支付多少的最優(yōu)取值.另外,Yechiali等人[5?7]根據(jù)實際情況,提出了多隊列輪詢的以色列排隊模型.該模型中的顧客可以根據(jù)每次服務(wù)員服務(wù)完某個顧客后,選擇一個對其有利的隊列進行排隊等待服務(wù).2012 年,余玄少妙[8]從顧客是否履行社會公德的角度考慮了M/M/C排隊模型.利用Laplace-Stielties、負指數(shù)分布理論討論了系統(tǒng)中顧客的等待時間問題,并給出了顧客等待時間上界的一個近似公式.HE和Chavoushi[9]應(yīng)用矩陣分析法分析并討論了具有插隊行為的排隊模型.作者將到達隊列的顧客分成兩類:常規(guī)顧客(normal customer)和插隊顧客(interjecting customer),其中常規(guī)顧客按照到達次序進行服務(wù).若隊列中顧客數(shù)不為0,顧客到隊列末尾排隊等待服務(wù).插隊顧客是指新到顧客為減少個人等待時間,總是試圖插隊到隊列的前面部分,從而以較短時間完成服務(wù).在此基礎(chǔ)上,作者利用矩陣分析方法給出了常規(guī)顧客和插隊顧客在該排隊系統(tǒng)中的平均等待時間的數(shù)值表達式與理論結(jié)果.

本文考慮了具有插隊和止步行為的M/M/1/m+1排隊系統(tǒng)中顧客的等待時間問題.利用負指數(shù)分布、Laplace-Stieltjes變換、全概率公式,給出了處于等待隊列位置n的顧客,任意一個常規(guī)顧客和任意一個插隊顧客的等待時間的表達式和數(shù)值結(jié)果,并在此基礎(chǔ)上,討論了相關(guān)指數(shù)隨系統(tǒng)參數(shù)的變化情況.與文[9-10]不同的是: 當系統(tǒng)中服務(wù)員空閑時,顧客直接進入系統(tǒng)接受服務(wù); 當系統(tǒng)中服務(wù)員繁忙時,到達顧客考慮到插隊情形的發(fā)生,其將以概率b決定進入隊列等候服務(wù),或者以概率1?b止步系統(tǒng).

2.模型描述

本文研究具有插隊和止步行為的M/M/1/m+1排隊系統(tǒng)具體描述如下

1) 顧客相繼到達的間隔時間服從參數(shù)為λ的Poisson流,系統(tǒng)中只有一個服務(wù)員,當?shù)竭_顧客遇到系統(tǒng)空閑,則立即接受服務(wù),其服務(wù)時間服從參數(shù)為μ(0<μ<∞)的負指數(shù)分布.

4) 插隊顧客決定插隊時,其插隊位置取決于等待的隊列中顧客數(shù)和顧客的位置.若等待隊列中的顧客數(shù)為k,并且假設(shè)等待位置上的顧客拒絕其插隊行為的概率為ri.因此,插隊顧客成功插隊于位置i的概率為隊列中k個顧客均拒絕其插隊行為,插隊顧客處于位置k+1上的概率為

5) 系統(tǒng)的最大容量為m+1,當m+1個位置均被顧客占領(lǐng)時,新到的顧客自動離開系統(tǒng).

3.具有止步行為的M/M/1/m+1排隊系統(tǒng)排隊指標

現(xiàn)考慮以概率b止步的M/M/1/m+1排隊系統(tǒng),其狀態(tài)轉(zhuǎn)移圖如圖3.1所示.

圖3.1 止步策略的M/M/1/m+1排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移

為了便于后面研究,記

? pn(n=0,1,...,m+1)為平穩(wěn)條件下任意時刻隊長為n的概率;

? qn(n=0,1,...,m)為到達且能進入系統(tǒng)的顧客看到有n個顧客的概率;

?為顧客在隊列中的平均等待時間.根據(jù)文[10-11],可得系統(tǒng)穩(wěn)態(tài)狀態(tài)概率的方程為

解得

4.插隊行為下顧客的等待時間分析

雖然插隊行為對該排隊系統(tǒng)的隊長沒有影響,但在該隊列中顧客等待時間將會受到此插隊行為的干擾.在本節(jié)中,我們對位置n的顧客、常規(guī)顧客與插隊顧客的等待時間進行詳細的討論,同時求解出各個顧客的平均等待時間的具體表達式.在討論之前,先給出幾個需要用到的符號,記

? Wn(n=1,2,...,m): 等待位置n的顧客所需等待時間,Wn(t)=P {Wn≤t},t>0.

? W[N]: 任意一個常規(guī)顧客所需等待時間,W[N](t)=P{W[N]≤t},t>0.

進一步,定義

處于等待隊列位置n(n=1,2,...,m)的顧客的等待時間長短與其位置的變化密切相關(guān).而這種位置變化又取決于其自身所處位置和插隊顧客剩余到達時間和顧客的剩余服務(wù)時間之間的關(guān)系.因此,對處于位置n顧客的隊列序號變化做如下討論:

情形1n=1,2,...,m ?1,即顧客所處位置并非排隊系統(tǒng)的末尾位置,可分為下面兩種:

a)n →n+1: 當前繁忙的服務(wù)員服務(wù)一個顧客的剩余時間大于插隊顧客的剩余到達時間;

b)n →n ?1: 當前繁忙的服務(wù)員服務(wù)一個顧客的剩余時間小于下一個插隊顧客的剩余到達時間.

情形2n=m,即顧客所處位置為隊列末尾,這表明系統(tǒng)中的總顧客數(shù)已經(jīng)為m+1 (一位顧客正在服務(wù),m位顧客處于等待狀態(tài)).此時新到的顧客由于容量的限制不得不直接離開系統(tǒng).因此,位置m顧客的隊列序號變化只能是向前移動一位.注意這里的離開不同于止步行為: 止步行為是到達顧客自己以一定的概率決定是否進入系統(tǒng),而此時的離開是必然事件.

Research on corresponding views in Qingdao modern urban construction

用T1表示插隊顧客在前n個位置插隊成功的剩余到達時間,T2表示服務(wù)員服務(wù)一個顧客的剩余時間.記Zn=min(T1,T2)為當前位置n顧客的位置序號改變時間.于是有如下表達式:

利用負指數(shù)分布的的無記憶性,可得

進一步,得

下面分3種情況討論E[Wn]的表達式.

1)當n=1時,由全概率公式得

2)當n=2,3,...,m ?1時,由全概率公式得

3)當n=m時

對式(4.6)-(4.8)進行簡單的代數(shù)處理得

將式(4.10)反復迭代可得,

注意到w0(s)=E[e?sw0]=E[1]=1,將式(4.9)和(4.12)合并為

常規(guī)顧客在其所在排隊系統(tǒng)中遵從先到先服務(wù)(FCFS)的規(guī)則,即當其到達排隊系統(tǒng)時總是在隊列的末尾排隊等待服務(wù).則平均等待時間為

結(jié)合(4.16)和(4.17)式,(4.18)轉(zhuǎn)化為

當?shù)絹淼牟尻狀櫩涂匆姺?wù)員處于忙碌狀態(tài)并且隊列中等待人數(shù)為n(n ≥1)時,那么它將以概率處于隊列中的第k(1≤k ≤n)個位置,以概率插隊不成功而排隊于隊列末尾.

由w[I](s)的定義和全概率公式可得

由等待位置n顧客的等待時間的相關(guān)結(jié)果,(4.20)轉(zhuǎn)化為

式(4.21)求導并令s=0得

5.算例分析

本節(jié)討論排隊系統(tǒng)中位置n顧客的平均等待時間E[Wn],n=1,2,...,m隨著位置n和顧客決定插隊的概率σ,顧客到來強度λ,服務(wù)時間參數(shù)μ的變化情況.進一步,討論任意位置顧客平均等待時間E[W[N]]和插隊顧客平均等待時間E[W[I]]隨系統(tǒng)相關(guān)參數(shù)的變化趨勢.所得結(jié)果見表5.1和圖5.1.

算例1討論M/M/1/45排隊系統(tǒng)中E[Wn],(n=1,2,...),m,E[W[N]],E[W[I]]的數(shù)值結(jié)果.取λ=5.6,b=0.5,μ=3.2,σ=0.5,ri=e?1/i.

利用MATLAB 軟件編寫數(shù)值計算程序,其計算結(jié)果如表5.1.從表5.1可看出,在等待隊列中的位置越靠后,其等待時間越長.由圖5.1知在該系統(tǒng)中,插隊顧客的等待時間期望比常規(guī)顧客的等待時間期望約小于2.7個單位.該結(jié)論不失一般性,即插隊顧客等待時間期望顯然小于常規(guī)顧客.

表5.1 γ 等待隊列位置n的顧客的平均等待時間

圖5.1 E[Wn],E[W[N]],E[W[I]]隨n變化結(jié)果

算例2討論M/M/1/42排隊系統(tǒng)中,客流量強度和顧客插隊概率σ對常規(guī)顧客的平均等待時間E和插隊顧客的平均等待時間的影響情況.取μ=4.0,m=42,b=0.5,ri=e?1/i,λ從1.5變化到3.8,σ從0.32變化到0.8.利用MATLAB軟件編寫數(shù)值計算程序,相應(yīng)的數(shù)值結(jié)果見圖5.2和圖5.3.

圖5.2 E[W[I]]隨λ和σ的變化圖

圖5.3 E[W[N]]隨λ和σ的變化圖

從圖5.2和圖5.3中,可以看出當顧客到達率λ較小時,即在M/M/1/42排隊系統(tǒng)中,顧客到來強度比較小的時候,顧客插隊概率σ對E[W[N]]和E[W[I]]兩者的影響就不太明顯.但當顧客到達率λ增大時,顧客插隊概率σ對E[W[N]]和E[W[I]]兩者的影響就較為明顯.與此同時,將圖5.2和圖5.3作比較,可以發(fā)現(xiàn)插隊顧客的平均等待時間明顯比常規(guī)顧客的平均等待時間減少了約8倍左右.