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

張元元吳文青唐應輝

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

1.引言

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

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

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

2.模型描述

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

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

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

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

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

現考慮以概率b止步的M/M/1/m+1排隊系統,其狀態轉移圖如圖3.1所示.

圖3.1 止步策略的M/M/1/m+1排隊系統的狀態轉移

為了便于后面研究,記

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

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

?為顧客在隊列中的平均等待時間.根據文[10-11],可得系統穩態狀態概率的方程為

解得

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

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

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

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

進一步,定義

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

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

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

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

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

Research on corresponding views in Qingdao modern urban construction

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

利用負指數分布的的無記憶性,可得

進一步,得

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

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

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

3)當n=m時

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

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

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

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

結合(4.16)和(4.17)式,(4.18)轉化為

當到來的插隊顧客看見服務員處于忙碌狀態并且隊列中等待人數為n(n ≥1)時,那么它將以概率處于隊列中的第k(1≤k ≤n)個位置,以概率插隊不成功而排隊于隊列末尾.

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

由等待位置n顧客的等待時間的相關結果,(4.20)轉化為

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

5.算例分析

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

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

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

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

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

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

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

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

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