有限容量多服務員排隊系統全忙期分布函數的一種直觀計算途徑

余玅妙, 唐建芳

(1.四川師范大學數學科學學院，成都 610066; 2.四川輕化工大學數學與統計學院，自貢 643000)

0 引言

經典排隊系統中，忙期是指顧客到達空閑服務臺至服務臺再次空閑的這段時間。它在排隊模型性能分析中起到了刻畫系統運行效率的作用。同時，由于對排隊系統忙期的研究有助于人們在實踐中高效規劃和管理有限的服務資源，因此服務員忙期作為重要的系統績效指標一直以來受到眾多學者的關注。就多服務員隊列而言，根據忙期中是否所有服務員都在持續繁忙，還是僅有部分服務員繁忙這兩種情況，多服務員隊列的忙期有兩種不同的定義方式，即部分忙期和全忙期。具體來講，在具有c個平行同質服務員的排隊系統中，部分忙期定義為從發現系統為空的顧客到達開始，到首個使系統徹底變空的顧客離開為止的這段時間。而由Kiefer 和Wolfowitz[1]提出的全忙期概念則被定義為從促使c個服務員中最后一個空閑服務員進入繁忙狀態的顧客到達時刻起，到隨后c個服務員中的某個服務員變空閑為止的這段時間。在過去的幾十年中，針對無限緩沖空間多服務員隊列忙期概率密度函數及數字特征的求解涌現出了大量的優秀成果。通過建立反映修正隊長演化過程的微分差分方程組，Chaudhry 和Templeton[2]考察了經典M/M/c排隊系統忙期的概率密度函數。在此研究的助推下，許多學者先后利用連分式方法、特征函數與矩母函數聯合變換方法對多服務員隊列的忙期進行了深入的分析，取得了一系列研究成果[3–11]。

另一方面，隨著位相型分布理論的蓬勃發展，具有有限容量的馬氏排隊系統的忙期長度可被視為具有唯一吸收態的Markov 鏈的吸收時間。因此，首達時間分析方法在過去很長一段時間中被認為是研究該類系統忙期分布的一個有力工具。在眾多關于Markov 鏈理論的學術專著中，也對如何計算有限狀態Markov 鏈的首達吸收態時間分布有著清晰而詳盡的闡述[12–14]。但任何研究過度依賴于一種方法未必是一件好事，尤其對工程技術人員而言，他們更樂于接受簡潔且通俗易懂的方法。本文正是著眼于上述觀點，力圖使用Laplace 變換特征根及留數定理，呈現一種分析多服務員有限緩沖隊列忙期分布函數的直觀方法。值得一提的是，著名排隊論專家Chaudhry 教授近期與他的合作者關于顧客等待時間分布函數的研究成果[15–16]給本文帶來了諸多有益啟示。我們正是利用他們的思路，將研究進一步延伸至M/M/c/K隊列中另一重要指標，即服務員全忙期的分析中，為研究復雜多服務員排隊系統全忙期分布函數提供了一種易于理解的備選分析方法。

文章整個分析過程將從全忙期分布函數的Laplace-Stieltjes 變換B?K,c(s)的遞推表達式入手；再通過使用上述Laplace-Stieltjes 變換的特征根來獲取系統服務員全忙期的分布函數。為便于理解，現簡要給出該排隊系統的模型描述。本文考慮一個具有c(1≤c<∞)個平行同質服務員的排隊系統，他們的服務時間均服從參數為μ的指數分布。顧客以參數為λ的Poisson 流到達，系統中有K(K>c ≥1)個位置可供顧客占用。若到達顧客發現K個位置已全部占用，則自動離開系統不再回來，若有空閑位置則進入服務系統接受服務。進一步，假設模型描述中所涉及到的隨機變量均相互獨立。

1 全忙期Laplace-Stieltjes 變換的遞推公式

本節將利用子全忙期和全忙期之間的一個重要關系來建立全忙期分布函數的Laplace-Stieltjes 變換的簡明遞推公式。有了這個遞推公式，即可通過一些基本的代數運算獲得B?K,c(s)的明確的解析表達式。為證明下述定理，令隨機變量Si(i=1,2,···,c)代表顧客在第i個服務員處的服務時間，BK,c(t)表示M/M/c/K隊列的全忙期概率分布函數?？紤]到數學軟件編程計算之需，定理的主要結果以迭代形式呈現并給出初始項B?c+1,c(s)。

定理1 令Bc+m,c表示有限緩沖M/M/c/c+m排隊系統的全忙期(m=1,2,···,Kc)。記分布函數BK,c(t)的Laplace-Stieltjes 變換為

則可使用以下迭代公式計算B?K,c(s)：

證明 在M/M/c/K隊列中，當最后一個空閑的服務員進入繁忙狀態時，其中某位顧客將在時間χc后結束服務并離開系統，這里χc= min(S1,S2,···,Sc)。在此期間，系統最多允許K-c個顧客進入隊列等候。由于全忙期的持續時間與顧客的服務順序無關，故可假想服務員能夠按照自己的意愿選擇適當的服務順序。為分析之需，我們將先到先服務(FCFS)規則更改為后到先服務(LCFS)規則。在這種服務方式下，對全忙期BK,c的分析就會與M/M/c/K-l+1(1≤l ≤K-c)系統全忙期的分析發生重要的關聯，這一點將在后文分析中結合圖示給出全面闡述。另外，如果在χc期間到達的顧客少于K-c個，那么變空閑的服務員將立即開始為在χc時間內到達的最后一個顧客提供服務。

不失一般性，假設變空閑的繁忙服務員即將開始為第(K-c)位顧客提供服務。如果在這個顧客的服務時間內有更多的服務員由繁忙轉為空閑可用，那么他們將為第(K-c)位顧客的所有后代提供服務，直到沒有此類后代可供服務為止。這里，第(K-c)位顧客的后代指的是那些可以進入緩沖空間等待，且發現所有c個服務員均在忙碌的顧客(包括后代的后代，即子子孫孫)。我們把完成這些顧客服務所需的時間稱為由第(K-c)位顧客產生的子全忙期(注意一個后代的后代所需的服務時間已被計入其中)。當上述子全忙期結束后，一個可用服務員將開始為第(K-c-1)位顧客提供服務，此后若有其他空閑可用服務員出現，他們將為所有在第(K-c-1)位顧客的子全忙期中進入隊列的后代提供服務，這里后代的定義與前述完全一致?？臻e的可用服務員將一直沿用此服務方式，最終服務完第1 位顧客及其他的所有后代子孫。令DK,c,j(j=0,1,2,···,K-c)表示M/M/c/K隊列中由第j位顧客產生的子全忙期的長度，注意在后文分析中，我們取DK,c,0= 0。因此，根據服務時間的獨立同分布性質和指數分布的無記憶性，我們將整個全忙期BK,c分解為

其中N(χc)表示在隨機時間長度χc內到達系統的顧客數量(包括到達后發現系統已滿并因此被阻擋而未能進入隊列的顧客)，其中H(x)表示Heaviside 階躍函數，按常規定義

通過考慮在服務時間χc內到達的顧客數量，并使用全期望分解技術，我們可以獲得隨機變量BK,c的分布函數的Laplace-Stieltjes 變換如下

從方程(1)中注意到，為了獲得B?K,c(s)的解析表達，須逐一確定D?K,c,l(s)(l= 1,2,···,K-c)，而以下事實對解決上述問題起著至關重要的作用。如果BL,c(c

這里舉一個例子來幫助讀者理解這個事實?？紤]一個簡單的M/M/3/7 排隊，并假設在服務時間χ3內有兩個顧客加入隊列，其中χ3=min(S1,S2,S3)。從圖1(a)和圖1(b)可以看出，當空閑的服務員開始為第二位顧客和他的后代子孫服務時，第一位顧客總是占據著等待隊列的第一個位置。因此，在M/M/3/7 隊列中，由第二位顧客產生的子全忙期D7,3,2與M/M/3/6 隊列的全忙期B6,3分布完全相同。利用DK,c,l和BK-l+1,c之間的這一關系，方程(1)可以改寫成如下適合遞推計算的形式

圖1 D7,3,2 與B6,3 具有相同概率分布的圖示說明

利用Mathematica 軟件包強大的符號計算能力，可以迭代給出B?c+2,c(s)和B?c+3,c(s)，并最終獲得B?K,c(s)的解析表達式。此外，我們還注意到，全忙期分布函數的Laplace-Stieltjes 變換具有有理結構形式，即

其中多項式QL,c(s)的次數總是高于多項式PL,c(s)的次數。這意味著我們可以通過使用部分分式分解技巧和留數計算規則來反演相應的Laplace-Stieltjes 變換，以獲得全忙期的概率分布函數。詳細的過程將在下一節中呈現。

2 全忙期分布函數

所謂B?K,c(s)的特征方程即是多項式方程QK,c(s) = 0。為了從BK,c的Laplace-Stieltjes 變換反演出全忙期分布函數BK,c(t)，必須知道特征方程全部的具有負實部的特征根。特征方程QK,c(s) = 0 在復平面上共有K-c+1 個根，在這些根中，我們假定有v個具有負實部的特征根，記作θr, 1≤r ≤v。利用這些特征根，B?K,c(s)可以通過部分分式分解展開寫成如下簡潔的表達形式[15,17]

為得到全忙期的概率密度函數bK,c(t)，對方程(4)實施Laplace 逆變換后，有

這里δ(t)表示Dirac 單位脈沖函數。關于Laplace 逆變換的更多細節，請參考文獻[18]。因此，根據方程(5)，全忙期的概率分布函數可以最終表示為

進一步，利用復分析中極點處的留數計算公式，并注意到B?K,c(s)|s=0= 1，則上述方程(6)中出現的未知常數b0,b1,b2,···,bv可由

加以確定，其中Q′K,c(θr)為多項式函數QK,c(s)在s=θr處的導數。這里可根據方程(7)的第二分支事先求出b1,b2,···,bv，然后再利用上述結果求出未知常數b0。將方程(7)中b0的值代入方程(6)，即有

如上述分析過程所呈現的那樣，我們實質上假設了θr(r= 1,2,···,v)是一系列互異的特征根。如果上述具有負實部的特征根中出現重根的情況，則只需對推導過程稍作修正即可得到該情形下對應的全忙期分布函數[17]。事實上，Tijms[19]和Chaudhry 等人[20]均指出在排隊分析的絕大多數情況下，根方法所依賴的根都具有良好的結構分布，且均為互異的單根。本文受限于篇幅，且考慮到重根情形在實際分析計算中少有發生，因此我們省略了對重根情形的詳細討論。

3 算例展示

本節提供一些典型的數值算例來說明前兩節所得公式的適用性。所有的數值計算均借助于Mathematica 軟件包在一臺配置為Corei7 處理器、頻率為2.6 千兆赫、16 千兆字節DDR3 內存的個人電腦上進行。下面第一個數值算例的目的是驗證前述理論分析結果的正確性。

例1 令c= 1，本文模型退化為Takagi 和Tarabia[21]研究的M/M/1/K隊列。此時所謂的全忙期變為單服務員隊列的經典忙期，Takagi 和Tarabia 在上述工作中報道了服務員忙期長度的一階原點矩為來計算，因此在相同的系統參數下，由方程(9)得到的計算結果應與由方程(10)得到的計算結果完全一致。這也是調試計算程序，檢查計算準確度的一種有效方法?？紤]一個M/M/1/6 排隊系統，設定系統參數μ= 1,λ= 0.8，并由此導出ρ= 0.8。將上述參數代入方程(9)中，可得E[BK,1] = 3.689 280。另一方面，定理1 中的迭代公式促使我們能夠獲得如下的關于B?6,1(s)的解析表示

利用Mathematica 軟件求解上式的特征方程，數值結果表明

將B6,1(t)代入方程(10)中，仍然可得E[BK,1] = 3.689 280。這從一個側面證明了本文理論分析的正確性。

例2 接下來，考慮一個一般的多服務員隊列，設系統參數取值為λ= 1.5,μ= 0.7,c=3,K=7。那么全忙期B7,3的Laplace-Stieltjes 變換由

同樣，將這些值代入方程(8)，得到相應的系數

從而可由方程(8)最終獲得分布函數B7,3(t)的表達式如下

為更加直觀地體現數值計算結果，圖2 中分別給出了M/M/1/6 隊列和M/M/3/7 隊列的全忙期分布函數的圖像。

圖2 M/M/1/6 隊列和M/M/3/7 隊列的全忙期分布函數圖像

4 結論

本文提出了一種較為直觀的方法來計算有限容量多服務員隊列中的全忙期分布函數BK,c(t)。不言而喻，找到分布函數將有助于我們更加全面地掌握隨機變量BK,c中包含的各種概率統計信息。本文所提出的方法簡單易懂，也很容易通過數學軟件編程計算求得其具體的數值結果。整個分析方法主要基于全忙期分布函數的Laplace-Stieltjes 變換遞推式以及該變換所對應的特征方程的負實部特征根，這兩者均可使用成熟的數學軟件包Mathematica 或Maple 輕松方便地求取。

作為本文研究內容的擴展，我們認為文中所呈現的分析技術也可以推廣用來考察離散時間隊列和非馬氏隊列的忙期分布，這些內容將有待于我們在今后的研究中加以解決。