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

　　關 鍵 詞： 科技期刊投稿,[G/GI/m/K]隊列,高負荷,隊長過程,流失比例,模擬仿真

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

　　ZHANG Ying， LIU Jian?min

　　(College of Science， Chang’an University， Xi’an 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 引 言

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

　　1 模型建立

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

　　[ρ=λμ1+μ2+…+μm] (1)

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

　　[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)

　　相應的計數過程為：

　　[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]內共到達的顧客數，[Nt]表示的是[0，t]內共服務完的顧客數，記[Qt]為[t]時刻的隊長， [Lt]為[0，t]內共流失的顧客數，考慮一個上面描述的隊列系統序列，則相應的刻畫隨機過程為時間用[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]。

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

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

　　[?0x=x+ψL0x]

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

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

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

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

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

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

　　[Sun，Svn，1，Svn，2，…，Svn，m?Su，Sv1，Sv2，…，Svm] (14)

　　設[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]]內共流失的顧客數，記[Πt]為[[0，t]]內的流失比例，則[Πt=Ltmax1，At]，且其相應刻畫隨機過程為[Πnt=nΠnntcn]

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

　　[Πn?Π] (21)

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

　　[ncnΠnnt?Πt] (22)

　　且：

　　[Πnntμn-λn?Πtη] (23)

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

　　[ncnΠnnt?π] (24)

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

　　3 模擬仿真

　　3.1 算法設計

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

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

　　表1 狀態矩陣A

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

　　3.2 算例分析

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

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

　　3.2.1 對顧客基本信息的分析

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

　　3.2.2 探討流失比例[loss]與[m，n]的關系

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

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

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

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

　　4 結 語

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

　　參考文獻

　　[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.