多服務(wù)臺中流失比例的高負(fù)荷極限的模擬仿真

張瑩+劉建民

摘 ?要： 為了得到多服務(wù)臺隊列中流失率的高負(fù)荷極限，通過對有顧客流失的[G/G/1/K]隊列進行推廣得到[G/GI/m/K]隊列，在高負(fù)荷條件下，獲得了有[m]個服務(wù)臺的隊列系統(tǒng)中隊長過程、流失過程的極限定理與流失比例的高負(fù)荷極限。以[M/M/m/K]隊列為例，用Matlab編程進行模擬仿真，驗證了理論結(jié)果的合理性，這是分析多服務(wù)臺隊列系統(tǒng)的一種新方法。

關(guān) 鍵 詞： [G/GI/m/K]隊列; 高負(fù)荷; 隊長過程; 流失比例; 模擬仿真

中圖分類號： TN911?34 ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2014）24?0028?03

Analog simulation for heavy?traffic limit of loss proportion in many?server queues

ZHANG Ying， LIU Jian?min

（College of Science， Changan University， Xian 710064， China）

Abstract： To get the heavy?traffic limit for the loss proportion in many?server queues， the model of [G/G/1/K]queue with customer loss is extended to the model of[G/GI/m/K]. The limit theorems for the queue?length process， loss process and the heavy?traffic limit for the loss proportion in the system were obtained under the condition of heavy traffic. Taking the[M/M/m/K]queue as an example， the analog simulation was conducted with Matlab programming to verify the reasonability of the theoretical result. It is a new way to analyze the many?server queues.

Keyword： [G/GI/m/K]queue; heavy?traffic; queue?length process; loss proportion; simulation

0 ?引 ?言

在現(xiàn)實生活中大家經(jīng)常遇到的是多服務(wù)臺排隊系統(tǒng)且隊伍較長的現(xiàn)象，例如銀行和醫(yī)院中的排隊現(xiàn)象，這其實就是高負(fù)荷條件下的多服務(wù)臺排隊系統(tǒng)。在高負(fù)荷情況下研究多服務(wù)臺的排隊系統(tǒng)已有很多文章，如Whitt研究了帶放棄的多服務(wù)臺的流體模型[1]，Whitt給出[G/GI/n/m]隊列的擴散逼近[2]。Whitt和Hal fin研究了多指數(shù)服務(wù)臺隊列的高負(fù)荷極限[3]。Whitt研究有阻塞的服務(wù)系統(tǒng)的高負(fù)荷極限，討論了局部高負(fù)荷極限[4]。Whitt研究了單服務(wù)臺隊列中流失比例的高負(fù)荷極限[5]。關(guān)于高負(fù)荷條件下多服務(wù)臺排隊系統(tǒng)的模擬仿真研究的也比較多，例如霍明的并聯(lián)多服務(wù)臺排隊系統(tǒng)的仿真建模研究[6]以及鄧年華的基于Matlab的多服務(wù)臺排隊系統(tǒng)的計算機模擬[5]，陳實的多服務(wù)臺混合制排隊模型[M/G/s/k]的仿真研究[7]。本文是在高負(fù)荷情況下，對有顧客流失的[G/GI/m/K]隊列模型進行了研究，給出隊長過程、流失過程及流失比例的高負(fù)荷極限，同時給出基于Matlab編程的仿真算法，進行模擬仿真。

1 ?模型建立

本文研究的是[G/GI/m/K]隊列模型，一個一般平穩(wěn)到達(dá)過程，到達(dá)率為[λ]，獨立同分布的服務(wù)時間且服從一般分布，[m]個服務(wù)臺，平均服務(wù)率為[μii=1，2，…，m]，等待空間的額外最大容量為[K]，服務(wù)規(guī)則為先到先服務(wù)（FCFS）。設(shè)到達(dá)過程與服務(wù)過程是相互獨立的，服務(wù)強度為[ρ]，則有：

[ρ=λμ1+μ2+…+μm] （1）

設(shè)[Uk，V1，k，V2，k，…，Vm，k：k≥1]是一非負(fù)隨機變量序列，其中[Uk]表示的是第[k-1]個顧客與第[k]個顧客的到達(dá)時間間隔，[Vi，ki=1，2，…，m]表示的是第[i]個服務(wù)臺潛在服務(wù)時間序列，則相應(yīng)的部分和為：

[Suk=U1+U2+…+Uk] （2）

[Svi，k=Vi，1+Vi，2+…+Vi，k; ? i=1，2，…，m] （3）

且：

[Su0=Svi，0=U0=Vi，0=0] （4）

相應(yīng)的計數(shù)過程為：

[At=maxk≥0：Suk≤t] （5）

[Nit=maxk≥0：Svi，k≤t， ?t≥0] （6）

令[N]為疊加過程，定義為：

[Nt=N1t+N2t+…+Nmt， ? t≥0] ? ? （7）

由以上的定義可知：[At]表示的是[0，t]內(nèi)共到達(dá)的顧客數(shù)，[Nt]表示的是[0，t]內(nèi)共服務(wù)完的顧客數(shù)，記[Qt]為[t]時刻的隊長，[Lt]為[0，t]內(nèi)共流失的顧客數(shù)，考慮一個上面描述的隊列系統(tǒng)序列，則相應(yīng)的刻畫隨機過程為時間用[n]來刻畫，空間用[cn]來刻畫，[t]表示向下取整：

[Sunt=c-1nSun，nt-λ-1nnt] （8）

[Svn，it=c-1nSvn，i，nt-μ-1n，intAnt=c-1nAnnt-λnnt] （9）

[Nn，it=c-1nNn，int-μn，int] （10）

[Nnt=c-1nNnnt-μnnt] （11）

[Qnt=c-1n?Qnnt] （12）

[Lnt=c-1n?Lnnt] （13）

式中[μn=μn，1+…+μn，m]。

為了陳述結(jié)論，令[?]表示依分布收斂，[D≡D0，+∞，R，M1≡D，M1]表示在[M1]拓?fù)湎略赱0，+∞]上除0點外左極限存在的右連續(xù)實值函數(shù)空間，[Dk=D，M1k]為[k]維[D]乘積空間，[Dm+1，WM1]表示的是在[WM1]拓?fù)湎碌腫m+1]維[D]乘積空間，[Discx]表示函數(shù)[x]的不連續(xù)點的集合，[=d]表示依分布相等，[e]表示在[D]上的恒等函數(shù)，即[et=t]，[x?y]表示復(fù)合函數(shù)。

令[?0，ψL0：D→D2]的一維反射映射，且在0處有下界，滿足：

[?0x=x+ψL0x]

且令[?0，k，ψL0，ψUk：D→D3]的二維反射映射，且在0處有下界，在[k]處有上界，滿足[8]：

[?0，kx=x+ψL0x-ψUkx]

式中：[ψL0x]為下界修正函數(shù);[ψUkx]為上界修正函數(shù)。

2 ?[G/GI/m/K]隊列的隨機過程極限

2.1 ?隊長過程與流失過程的隨機過程極限

定理1 （隊長過程與流失過程的高負(fù)荷極限） 考慮上面所述的[G/GI/m/K]隊列模型序列，假定系統(tǒng)初始狀態(tài)為空，在[Dm+1，WM1]上：

[Sun，Svn，1，Svn，2，…，Svn，m?Su，Sv1，Sv2，…，Svm] （14）

設(shè)[cn→∞]， [ncn→∞]，[μn，i→μi，0<μi<∞]，有：[ηn=n?μn-λncn→η， ?-∞<η<+∞] （15）

[Kncn→k， ?0

且假定：

[PSu0=0=PSvi0=1] （17）

[PDiscSvi?μie?DiscSvj?μje=?=1] （18）

[PDiscSvi?μie?DiscSu=?=1] （19）

則有：

[Qn，Ln?Q，L= ? ? ??0，ki=1mSvi-Su-ηe，ψUki=1mSvi-Su-ηe] （20）

2.2 ?流失比例的探究

因為[Lt]表示的是[[0，t]]內(nèi)共流失的顧客數(shù)，記[Πt]為[[0，t]]內(nèi)的流失比例，則[Πt=Ltmax1，At]，且其相應(yīng)刻畫隨機過程為[Πnt=nΠnntcn]

定理2：在定理1的條件下，若在[D0，∞，R，M1]上：

[Πn?Π] （21）

其中[Πt=Ltt]，[t≥0]，假定當(dāng)[t>0]時，[Pt∈DiscL=0]，對于所有的[t>0]，當(dāng)[n→∞]時：

[ncnΠnnt?Πt] （22）

且：

[Πnntμn-λn?Πtη] （23）

式中[η]是式（15）中的極限，若當(dāng)[t→∞]時[Πt?π]，則有：

[ncnΠnnt?π] （24）

式中[π]是某一確定的流失比例。

3 ?模擬仿真

3.1 ?算法設(shè)計

為了方便排隊系統(tǒng)的信息記錄及仿真算法的研究，本文構(gòu)建這樣一個狀態(tài)矩陣A為一個[8×s]矩陣，[s]為考慮的[0，t]到達(dá)的前[s]個顧客，矩陣的每一列存放著一名顧客的所有信息及此顧客到達(dá)時系統(tǒng)的狀態(tài)，則以第[i]列為例，矩陣每一行所存放的具體信息如表1所示。

在算法中：[r]表示平均到達(dá)率;[μ]表示平均服務(wù)率;[k]為等待空間容量;[m]為服務(wù)臺數(shù);[loss]為流失比例。根據(jù)到達(dá)過程產(chǎn)生顧客的間隔到達(dá)時間，則可得到每個顧客的到達(dá)時刻，并初始化矩陣A的第一行，根據(jù)服務(wù)時間服從的分布產(chǎn)生顧客的服務(wù)時間，流失比例的計算應(yīng)用第2節(jié)中的定義式。

表1 狀態(tài)矩陣A

由于前[m]個顧客到達(dá)時均不需要排隊，因此可初始化矩陣A的前[m]列。當(dāng)?shù)赱ii>m]個顧客到達(dá)系統(tǒng)時，會遇到如三種情況：情況1為 顧客到達(dá)時有空閑的服務(wù)臺，顧客不需要等待直接接受服務(wù);情況2為顧客到達(dá)時無空閑服務(wù)臺，顧客進入等待隊列;情況3為顧客到達(dá)時等待空間已滿，顧客被阻塞而流失。這樣通過對顧客的到達(dá)進行分析，得到相應(yīng)的數(shù)量指標(biāo)，同時初始化矩陣A。

3.2 ?算例分析

現(xiàn)在給出算例分析，以[M/M/m/K]為例：考慮一[M/M/m/K]隊列的模型序列，在第[n]個模型中：令刻畫常數(shù)[cn=n]，顧客的平均到達(dá)率[r=m?1+1n]，各個服務(wù)臺的平均服務(wù)率都相同為[u=1]，則服

務(wù)強度為[ρ=rm]，令等待空間容量[k=30]，[s=n]，即考慮在[0，t]內(nèi)到達(dá)的前[n]個顧客。

3.2.1 ?對顧客基本信息的分析

對到達(dá)的前100個顧客進行分析（m=100）如圖1所示。從圖1中的（a）部分可得到當(dāng)顧客的離開時刻與到達(dá)時刻相同時，則該顧客為被阻塞而流失的顧客;從（c）部分可得到當(dāng)顧客的等待時長為0時，主要為兩種情況：顧客到達(dá)時有空閑的服務(wù)臺顧客直接接受服務(wù);顧客到達(dá)等待空間已滿，顧客因被阻塞而流失;而 （d）、（e）、（f）部分分別表示了顧客到達(dá)時系統(tǒng)的隊長、流失顧客數(shù)及流失率。

圖1 到達(dá)前100個顧客分析圖

3.2.2 ?探討流失比例[loss]與[m，n]的關(guān)系

模擬在[n]與[m]取不同的值的情況下的流失比例（橫坐標(biāo)均為時間，縱坐標(biāo)均為流失比例），如圖2所示。

在圖2中，當(dāng)[n]的取值相同服務(wù)臺數(shù)[m]不同時，服務(wù)強度相同但平均到達(dá)率不同;當(dāng)服務(wù)臺數(shù)[m]相同[n]取不同的數(shù)值時，平均到達(dá)率不同從而服務(wù)強度不同。服務(wù)強度與流失比例對比，如表2所示。

由于到達(dá)時間間隔與服務(wù)時間均為產(chǎn)生的隨機數(shù)，每次的模擬結(jié)果均不相同且有時相差很大，但是當(dāng)[n=10 ?000]時，可觀察到流失比例基本上趨近于一個確定值，當(dāng)[n]取值更大時，通過多次的模擬計算，也可得到同樣的結(jié)論，這與推論結(jié)論相符，所以建立的仿真算法是有效且可行的。

圖2 n，m取值不同時的流失比例

4 ?結(jié) ?語

本文給出[G/GI/m/K]隊列在高負(fù)荷下隊長過程、流失過程及流失比例的高負(fù)荷極限，并且以[M/M/m/K]為例，給出關(guān)于流失比例的模擬仿真。根據(jù)[K]的不同取值可被應(yīng)用到不同的隨即服務(wù)系統(tǒng)，當(dāng)[K=m]時，可被應(yīng)用到呼叫中心服務(wù)系統(tǒng)，當(dāng)[K>m]且為具體某一個值時可被應(yīng)用到隨機服務(wù)系統(tǒng)（如銀行系統(tǒng)）。通過對更新方法與隨機數(shù)產(chǎn)生的方法，該仿真算法還可被應(yīng)用到其他的隊列系統(tǒng)，如[G/M/m/K]或[M/G/m/K]等隊列系統(tǒng)，顯然當(dāng)[m=1]時為單服務(wù)臺隊列系統(tǒng)。

參考文獻(xiàn)

[1] WHITT W. Fluid models for multi?server queues with abandonment [J]. Operations Research， 2006， 54（1）： 37?54.

[2] WHITT W. A diffusion approximation for the [G/GI/n/m] queue [J]. Operations Research， 2004， 52（6）： 922?941.

[3] HALFIN S， WHITT W. Heavy?traffic limits for queues with many exponential servers [J]. Operations Research， 1981， 29（3）： 567?588.

[4] WHITT W. Heavy?traffic approximations for service systems with blocking [J]. AT&T Bell Laboratories Technical Journal， 1984， 63（5）： 689?708.

[5] WHITT W. Heavy?traffic limits for loss proportions in single?server queues [J]. Queueing Systems， 2004， 46： 507?536.

[6] 霍明.并聯(lián)多服務(wù)臺多服務(wù)臺排隊系統(tǒng)的仿真建模研究[J].廣東科技，2012（15）：198?200.

[7] 鄧壽年，姜培華，何廣.基于Matlab的多服務(wù)臺排隊系統(tǒng)的計算機模擬[J].安慶學(xué)院學(xué)報，2011，17（3）：61?63.

[8] WHITT W. Stochastic?process limits [M]. New York： Springer?Verlag， 2002.

[9] 陳實.多服務(wù)臺混合制排隊模型[M/G/s/k]的仿真研究[J].現(xiàn)代電子技術(shù)，2010，33（3）：142?149.

[10] BILLINGSLEY P. Convergence of probability measures [M]. 2nd ed. New York： Wiley， 1999.

圖1 到達(dá)前100個顧客分析圖

3.2.2 ?探討流失比例[loss]與[m，n]的關(guān)系

模擬在[n]與[m]取不同的值的情況下的流失比例（橫坐標(biāo)均為時間，縱坐標(biāo)均為流失比例），如圖2所示。

在圖2中，當(dāng)[n]的取值相同服務(wù)臺數(shù)[m]不同時，服務(wù)強度相同但平均到達(dá)率不同;當(dāng)服務(wù)臺數(shù)[m]相同[n]取不同的數(shù)值時，平均到達(dá)率不同從而服務(wù)強度不同。服務(wù)強度與流失比例對比，如表2所示。

由于到達(dá)時間間隔與服務(wù)時間均為產(chǎn)生的隨機數(shù)，每次的模擬結(jié)果均不相同且有時相差很大，但是當(dāng)[n=10 ?000]時，可觀察到流失比例基本上趨近于一個確定值，當(dāng)[n]取值更大時，通過多次的模擬計算，也可得到同樣的結(jié)論，這與推論結(jié)論相符，所以建立的仿真算法是有效且可行的。

圖2 n，m取值不同時的流失比例

4 ?結(jié) ?語

本文給出[G/GI/m/K]隊列在高負(fù)荷下隊長過程、流失過程及流失比例的高負(fù)荷極限，并且以[M/M/m/K]為例，給出關(guān)于流失比例的模擬仿真。根據(jù)[K]的不同取值可被應(yīng)用到不同的隨即服務(wù)系統(tǒng)，當(dāng)[K=m]時，可被應(yīng)用到呼叫中心服務(wù)系統(tǒng)，當(dāng)[K>m]且為具體某一個值時可被應(yīng)用到隨機服務(wù)系統(tǒng)（如銀行系統(tǒng)）。通過對更新方法與隨機數(shù)產(chǎn)生的方法，該仿真算法還可被應(yīng)用到其他的隊列系統(tǒng)，如[G/M/m/K]或[M/G/m/K]等隊列系統(tǒng)，顯然當(dāng)[m=1]時為單服務(wù)臺隊列系統(tǒng)。

參考文獻(xiàn)

[1] WHITT W. Fluid models for multi?server queues with abandonment [J]. Operations Research， 2006， 54（1）： 37?54.

[2] WHITT W. A diffusion approximation for the [G/GI/n/m] queue [J]. Operations Research， 2004， 52（6）： 922?941.

[3] HALFIN S， WHITT W. Heavy?traffic limits for queues with many exponential servers [J]. Operations Research， 1981， 29（3）： 567?588.

[4] WHITT W. Heavy?traffic approximations for service systems with blocking [J]. AT&T Bell Laboratories Technical Journal， 1984， 63（5）： 689?708.

[5] WHITT W. Heavy?traffic limits for loss proportions in single?server queues [J]. Queueing Systems， 2004， 46： 507?536.

[6] 霍明.并聯(lián)多服務(wù)臺多服務(wù)臺排隊系統(tǒng)的仿真建模研究[J].廣東科技，2012（15）：198?200.

[7] 鄧壽年，姜培華，何廣.基于Matlab的多服務(wù)臺排隊系統(tǒng)的計算機模擬[J].安慶學(xué)院學(xué)報，2011，17（3）：61?63.

[8] WHITT W. Stochastic?process limits [M]. New York： Springer?Verlag， 2002.

[9] 陳實.多服務(wù)臺混合制排隊模型[M/G/s/k]的仿真研究[J].現(xiàn)代電子技術(shù)，2010，33（3）：142?149.

[10] BILLINGSLEY P. Convergence of probability measures [M]. 2nd ed. New York： Wiley， 1999.

圖1 到達(dá)前100個顧客分析圖

3.2.2 ?探討流失比例[loss]與[m，n]的關(guān)系

模擬在[n]與[m]取不同的值的情況下的流失比例（橫坐標(biāo)均為時間，縱坐標(biāo)均為流失比例），如圖2所示。

在圖2中，當(dāng)[n]的取值相同服務(wù)臺數(shù)[m]不同時，服務(wù)強度相同但平均到達(dá)率不同;當(dāng)服務(wù)臺數(shù)[m]相同[n]取不同的數(shù)值時，平均到達(dá)率不同從而服務(wù)強度不同。服務(wù)強度與流失比例對比，如表2所示。

由于到達(dá)時間間隔與服務(wù)時間均為產(chǎn)生的隨機數(shù)，每次的模擬結(jié)果均不相同且有時相差很大，但是當(dāng)[n=10 ?000]時，可觀察到流失比例基本上趨近于一個確定值，當(dāng)[n]取值更大時，通過多次的模擬計算，也可得到同樣的結(jié)論，這與推論結(jié)論相符，所以建立的仿真算法是有效且可行的。

圖2 n，m取值不同時的流失比例

4 ?結(jié) ?語

本文給出[G/GI/m/K]隊列在高負(fù)荷下隊長過程、流失過程及流失比例的高負(fù)荷極限，并且以[M/M/m/K]為例，給出關(guān)于流失比例的模擬仿真。根據(jù)[K]的不同取值可被應(yīng)用到不同的隨即服務(wù)系統(tǒng)，當(dāng)[K=m]時，可被應(yīng)用到呼叫中心服務(wù)系統(tǒng)，當(dāng)[K>m]且為具體某一個值時可被應(yīng)用到隨機服務(wù)系統(tǒng)（如銀行系統(tǒng)）。通過對更新方法與隨機數(shù)產(chǎn)生的方法，該仿真算法還可被應(yīng)用到其他的隊列系統(tǒng)，如[G/M/m/K]或[M/G/m/K]等隊列系統(tǒng)，顯然當(dāng)[m=1]時為單服務(wù)臺隊列系統(tǒng)。

參考文獻(xiàn)

[1] WHITT W. Fluid models for multi?server queues with abandonment [J]. Operations Research， 2006， 54（1）： 37?54.

[2] WHITT W. A diffusion approximation for the [G/GI/n/m] queue [J]. Operations Research， 2004， 52（6）： 922?941.

[3] HALFIN S， WHITT W. Heavy?traffic limits for queues with many exponential servers [J]. Operations Research， 1981， 29（3）： 567?588.

[4] WHITT W. Heavy?traffic approximations for service systems with blocking [J]. AT&T Bell Laboratories Technical Journal， 1984， 63（5）： 689?708.

[5] WHITT W. Heavy?traffic limits for loss proportions in single?server queues [J]. Queueing Systems， 2004， 46： 507?536.

[6] 霍明.并聯(lián)多服務(wù)臺多服務(wù)臺排隊系統(tǒng)的仿真建模研究[J].廣東科技，2012（15）：198?200.

[7] 鄧壽年，姜培華，何廣.基于Matlab的多服務(wù)臺排隊系統(tǒng)的計算機模擬[J].安慶學(xué)院學(xué)報，2011，17（3）：61?63.

[8] WHITT W. Stochastic?process limits [M]. New York： Springer?Verlag， 2002.

[9] 陳實.多服務(wù)臺混合制排隊模型[M/G/s/k]的仿真研究[J].現(xiàn)代電子技術(shù)，2010，33（3）：142?149.

[10] BILLINGSLEY P. Convergence of probability measures [M]. 2nd ed. New York： Wiley， 1999.