基于排隊(duì)系統(tǒng)的隊(duì)長管理分析

張笑雨，郭永江

(北京郵電大學(xué) 理學(xué)院，北京 100876)

在大多數(shù)的排隊(duì)系統(tǒng)研究中，人們對(duì)實(shí)際值的極限關(guān)注度不高，例如，隊(duì)列長度的有限性、顧客在隊(duì)伍中等待時(shí)間的有限性.現(xiàn)實(shí)中，顧客在隊(duì)列中等待時(shí)間超過一個(gè)極限值，就變得不耐煩而離開隊(duì)伍.這種現(xiàn)象在通信系統(tǒng)中經(jīng)常遇到，在通信網(wǎng)絡(luò)中，用戶可能在接收到信息之前就變得不耐心，從而導(dǎo)致資源被無效占用.

在分組交換網(wǎng)絡(luò)中，交換節(jié)點(diǎn)的緩沖區(qū)容量是有限的，所以只有當(dāng)?shù)竭_(dá)的客戶的數(shù)據(jù)包加入節(jié)點(diǎn)中已存在的數(shù)據(jù)包后的大小小于總?cè)萘繒r(shí)，才會(huì)被接受.由于輸出速率是恒定的，這就相當(dāng)于對(duì)等待時(shí)間有限制.對(duì)于等待時(shí)間有限的系統(tǒng)：

1)用戶的等待時(shí)間或逗留(等待+服務(wù))時(shí)間是有限的；

2)用戶在到達(dá)系統(tǒng)時(shí)可以計(jì)算其預(yù)期等待時(shí)間和預(yù)期效用，若預(yù)期效用為非負(fù)，則其選擇進(jìn)入系統(tǒng)，否則選擇離開.

結(jié)合這兩個(gè)特點(diǎn)就有了不耐煩顧客的排隊(duì)系統(tǒng).

本文考慮了一個(gè)單服務(wù)器的排隊(duì)系統(tǒng)，顧客(不耐煩)按照速率為λ的泊松到達(dá)接受服務(wù)，服務(wù)時(shí)間是獨(dú)立同分布的速率為μ的指數(shù)分布，每個(gè)到達(dá)的顧客最多等待一個(gè)速率為γ的指數(shù)分布時(shí)間，若在此時(shí)間內(nèi)沒有接受到服務(wù)，則會(huì)選擇離開.

P·Naor[1]研究了在指數(shù)分布服務(wù)的條件下，一般顧客的排隊(duì)模型，并解決了隊(duì)列中最多可容納人數(shù)的近似值.Barrer (1957)[2]、Gnedenko和Kovalenko[3]研究了在指數(shù)分布服務(wù)的條件下不耐煩顧客的排隊(duì)模型.Hokstad[4]研究了在確定性分布服務(wù)的條件下一個(gè)密切相關(guān)的模型.Daley[5]研究了GI/G/1隊(duì)列得出進(jìn)入系統(tǒng)的顧客如果需要等待很長時(shí)間，顧客可能會(huì)在開始服務(wù)之前或者完成服務(wù)后離開系統(tǒng).Charlot和Pujolle[6]給出了一般單服務(wù)器隊(duì)列的遍歷條件.Stanford[7]和Bezalel[8]等文獻(xiàn)解決了單服務(wù)器排隊(duì)系統(tǒng)中的一些特殊分布模型.

本文得到了M/M/1+M排隊(duì)中最大隊(duì)列的近似值.在排隊(duì)系統(tǒng)中，接受服務(wù)的顧客通常會(huì)對(duì)服務(wù)系統(tǒng)的兩個(gè)屬性進(jìn)行評(píng)估，一個(gè)是凈貨幣收益，另一個(gè)是預(yù)期等待時(shí)間.這兩個(gè)屬性決定了顧客是應(yīng)該加入排隊(duì)系統(tǒng)還是不加入.在文獻(xiàn)[9]中，顧客的效用被簡單的建模為凈貨幣收益減去等待時(shí)間的費(fèi)用.根據(jù)Abdellaoui和Kemel[10]的研究雖然時(shí)間和金錢是不等同的，但時(shí)間可以一定的金錢來衡量.我們用θ來記單位時(shí)間的費(fèi)用.

Bulow[11]和Stokey[12]研究了策略性顧客在排隊(duì)系統(tǒng)中的重要性，Aviv和Pazga[13]提出如果顧客是有策略性的，那么系統(tǒng)就會(huì)損失20%的收益.Liu和Zhang[14]研究了顧客面對(duì)兩個(gè)排隊(duì)系統(tǒng)的模型，Koszegi和Rabin[15]給出了有策略的顧客的效應(yīng)函數(shù).本文在此基礎(chǔ)上給出了相應(yīng)的效應(yīng)函數(shù).

1 模型的建立

本文考慮一個(gè)單服務(wù)員的排隊(duì)服務(wù)系統(tǒng)M/M/1+M，顧客按照速率為λ的泊松到達(dá)從系統(tǒng)外部到達(dá)系統(tǒng).假設(shè)排隊(duì)的空間是有限的，最大可容N個(gè)位置，即系統(tǒng)中最多有(N+1)個(gè)顧客.當(dāng)顧客到達(dá)系統(tǒng)發(fā)現(xiàn)排隊(duì)位置數(shù)量為N時(shí)就會(huì)選擇離開.服務(wù)規(guī)則假設(shè)為先到先服務(wù)，即一個(gè)顧客到達(dá)系統(tǒng)，如果系統(tǒng)為空則進(jìn)入服務(wù)，否則在隊(duì)尾排隊(duì)等待服務(wù). 假設(shè)顧客是不耐煩的，即每個(gè)到達(dá)系統(tǒng)的顧客在排隊(duì)中的等待時(shí)間最長為一個(gè)均值為1/γ的指數(shù)分布，等待1/γ時(shí)間之后如果還不能進(jìn)入服務(wù)則選擇離開系統(tǒng).假設(shè)顧客的等待時(shí)間是獨(dú)立同分布的.當(dāng)然，如果在等待時(shí)間內(nèi)進(jìn)入了服務(wù)，則會(huì)在服務(wù)完成后離開系統(tǒng).無論顧客是否接受完服務(wù)，我們假設(shè)顧客離開系統(tǒng)不再返回.假設(shè)顧客的服務(wù)時(shí)間獨(dú)立同分布，服從均值為1/μ的指數(shù)分布.假設(shè)到達(dá)過程、等待時(shí)間序列和服務(wù)時(shí)間序列相互獨(dú)立.最后假設(shè)顧客的信息是對(duì)稱的，即每個(gè)人都知道彼此是不耐煩的顧客，且等待時(shí)間和接受服務(wù)的時(shí)間都是獨(dú)立同分布的.

基于M/M/1+M的模型假設(shè)，令L={L(t)∶t≥0}，其中L(t)表示t時(shí)刻系統(tǒng)中的顧客數(shù)，則L為馬氏過程，其狀態(tài)轉(zhuǎn)移速率見圖1.

圖1 狀態(tài)轉(zhuǎn)移速率Figure 1 State transition rate

假設(shè)系統(tǒng)處于穩(wěn)態(tài)，定義Pn為穩(wěn)態(tài)下系統(tǒng)中有n(0≤n≤N+1)個(gè)顧客的概率，則平衡方程如下所示：

λp0=μp1+γp1,
(λ+γ+μ)p1=μp2+λp0+2γp2,
?
(λ+nγ+μ)pn=μpn+1+λpn-1+(n-1)γpn+1,

n=1,2,…,N，又因?yàn)閜0+p1+…+pN+1=1,pi≥0,i=0,1,…,N+1，解平衡方程得平穩(wěn)分布為：

π≡(p0,p1,…,pN+1)，

其中

(1)

由平穩(wěn)分布得系統(tǒng)中的平均顧客數(shù)為

(2)

若一個(gè)顧客進(jìn)入排隊(duì)系統(tǒng)后并且最終獲得服務(wù)，則會(huì)獲得收益R，支付平均等待時(shí)間成本θw，即其最終獲得的效用為R-θw；若一個(gè)顧客進(jìn)入排隊(duì)系統(tǒng)后最終沒有獲得服務(wù)，則獲得收益0，支付平均等待時(shí)間成本θ/γ，即其最終獲得的效用為-θ/γ，其中w是平均等待時(shí)間，θ為單位時(shí)間等待成本.

假設(shè)R≥θ/μ，即若顧客進(jìn)入系統(tǒng)后不需要排隊(duì)直接接受服務(wù)，其效用為正.若R<θ/μ顧客進(jìn)入系統(tǒng)的效用為負(fù)，故所有的顧客都不會(huì)選擇進(jìn)入系統(tǒng).

本文主要在個(gè)人最優(yōu)和整體最優(yōu)兩方面對(duì)顧客的行為進(jìn)行研究.首先給出顧客的個(gè)人效用隨著n增大而減小，其中n為排在隊(duì)列中的第n個(gè)顧客，當(dāng)n足夠大時(shí)顧客的個(gè)人效用為負(fù)值，顧客不會(huì)選擇進(jìn)入系統(tǒng)，故該排隊(duì)系統(tǒng)可以設(shè)置有限的排隊(duì)位置.其次給出顧客的整體效用在n=1時(shí)是正，當(dāng)n趨于無窮時(shí)為負(fù)值，故一定存在第n*個(gè)顧客，使得前n*個(gè)顧客的整體效用為正，第(n*+1)個(gè)顧客的整體效用為負(fù)值.

2 個(gè)人最優(yōu)

當(dāng)一個(gè)顧客到達(dá)排隊(duì)系統(tǒng)時(shí)，他/她有兩種選擇，排隊(duì)加入系統(tǒng)或者選擇不排隊(duì)直接離開.當(dāng)顧客選擇排隊(duì)加入系統(tǒng)時(shí)就會(huì)消耗一些時(shí)間成本，但與一般不帶有不耐煩排隊(duì)系統(tǒng)不同的是，該顧客如果最終得到服務(wù)將獲得收益R，損失等待成本θ/γ；如果不能耐心等待而選擇中途離開則得到負(fù)收益：即等待引起的損失.當(dāng)顧客選擇不排隊(duì)直接離開時(shí)就不會(huì)獲得任何的收益和損失.因此，顧客的個(gè)人效用包含其加入系統(tǒng)后獲得的收益R和在系統(tǒng)內(nèi)逗留的時(shí)間成本.假設(shè)顧客按照其效用選擇排隊(duì)和不排隊(duì)，即個(gè)人效用為非負(fù)時(shí)會(huì)選擇加入，否則會(huì)離開.我們的目的是優(yōu)化顧客的個(gè)人效用.

本文在穩(wěn)態(tài)下描述個(gè)人效用，下面首先分析排隊(duì)的穩(wěn)態(tài)行為.

為了表示出來第n個(gè)顧客的具體個(gè)人效用，給出以下引理.

證明為了確定Wn的一個(gè)表達(dá)式，利用獨(dú)立指數(shù)隨機(jī)變量的最小值獨(dú)立于它們大小排序，并且該最小值的速率等于它們速率的和，直到第(n-1)個(gè)顧客進(jìn)入排隊(duì)系統(tǒng)的時(shí)間是這n個(gè)隨機(jī)變量的最小值加上以后的附加指數(shù)時(shí)間即第n個(gè)顧客的不耐煩時(shí)間，因?yàn)橹笖?shù)隨機(jī)變量是無記憶性的，可得

迭代上式有

從而可得結(jié)果.

在上式中用(n-1)代替n后

同樣道理可得

基于排隊(duì)的穩(wěn)態(tài)行為，建立顧客的個(gè)人效用如下.

通過引理2.1和2.2，第n個(gè)進(jìn)入排隊(duì)系統(tǒng)的顧客獲得的個(gè)人效用為

(3)

定義2.1 個(gè)人最優(yōu)是指存在數(shù)n使得位于前n個(gè)位置的顧客會(huì)進(jìn)入系統(tǒng)，位于(n+1)個(gè)位置之后的顧客會(huì)離開系統(tǒng).(一般講個(gè)人最優(yōu)是指的行動(dòng))

(4)

(5)

(6)

(n0-1)

由上式可知vs≥n0，從而[vs]=ns≥n0.

性質(zhì)2.1表明不耐煩顧客排隊(duì)系統(tǒng)的隊(duì)列平均長度小于或等于不帶有不耐煩顧客排隊(duì)系統(tǒng)的隊(duì)列平均長度.這種現(xiàn)象很直觀，因?yàn)樵谂抨?duì)過程中不耐煩顧客的隊(duì)伍里顧客離開的人數(shù)多從而其平均隊(duì)長要更小.

3 整體最優(yōu)

整體效用和個(gè)人效用在概念上有本質(zhì)的區(qū)別，整體效用是指顧客在單位時(shí)間內(nèi)產(chǎn)生的凈收益的預(yù)期綜合，其包括在單位時(shí)間內(nèi)實(shí)際到達(dá)排隊(duì)系統(tǒng)最終接受服務(wù)的顧客獲得的總收益減去單位時(shí)間內(nèi)顧客因排隊(duì)所消耗的時(shí)間成本.本節(jié)對(duì)整體效用進(jìn)行優(yōu)化.

定義3.1 整體最優(yōu)是指存在數(shù)n使得位于前n個(gè)位置的顧客會(huì)進(jìn)入系統(tǒng)，位于(n+1)個(gè)位置之后的顧客會(huì)離開系統(tǒng).

由引理2.2可知在單位時(shí)間內(nèi)，進(jìn)入系統(tǒng)的顧客能夠獲得服務(wù)的平均概率為

(7)

由式(1)、(2)和式(7)可得整體效用為

G=[λ-λpN+1-λ(1-δ)]R-Cx(N).

(8)

上式中等式右側(cè)λ-λpN+1表示單位時(shí)間內(nèi)顧客到達(dá)排隊(duì)系統(tǒng)后能進(jìn)入的人數(shù)，λ(1-δ)表示單位時(shí)間內(nèi)顧客因?yàn)椴荒蜔]有等到接受服務(wù)而離開系統(tǒng)的平均人數(shù)，Cx(N)表示單位時(shí)間內(nèi)顧客排隊(duì)的平均成本.當(dāng)取γ=0時(shí)可得到與P·Naor[1]一樣的結(jié)果.

4 結(jié) 語

在現(xiàn)實(shí)生活中顧客在排隊(duì)時(shí)，其在隊(duì)列中等待時(shí)間超過一個(gè)極限值，就變得不耐煩而離開隊(duì)列.在電話網(wǎng)絡(luò)中，用戶可能在接收到信息之前就變得不耐煩.所以對(duì)于不耐煩顧客的排隊(duì)系統(tǒng)有必要進(jìn)行研究.當(dāng)不耐煩的顧客加入排隊(duì)前會(huì)計(jì)算其效用(包括凈貨幣收益和時(shí)間成本)當(dāng)其效用為非負(fù)時(shí)，才會(huì)確定加入排隊(duì).本文主要解決了排隊(duì)系統(tǒng)在面對(duì)不耐煩的顧客時(shí)，它的緩沖區(qū)可以安排的最優(yōu)排隊(duì)隊(duì)長，這樣就會(huì)減少資源的浪費(fèi)，從而增加排隊(duì)系統(tǒng)的收益.

致謝：本文受國家自然科學(xué)基金11871116資助.