GI/G/1排隊系統(tǒng)的近似分析

趙 寧，黃小峰，劉文奇

(昆明理工大學1.數(shù)據(jù)科學研究中心；2.理學院，云南 昆明 650500)

現(xiàn)實生活中存在各種各樣的隨機服務系統(tǒng)，排隊論是分析和優(yōu)化隨機服務系統(tǒng)性能的有效工具[1，2]。本文針對到達過程是一般過程，服務時間服從一般分布的GI/G/1排隊系統(tǒng)展開研究，以便為解決諸多實際問題提供理論依據(jù)。

經典的單一服務器的排隊系統(tǒng)已經被廣泛研究，例如M/M/1排隊系統(tǒng)、M/G/1排隊系統(tǒng)、GI/M/1排隊系統(tǒng)等。M/M/1排隊系統(tǒng)可以通過分析相應的馬爾可夫過程求解系統(tǒng)的性能指標(隊長的概率分布、逗留時間分布、忙期等)。關于M/G/1排隊系統(tǒng)，可以通過在顧客離去時刻構造嵌入馬爾可夫鏈，得到排隊系統(tǒng)的平均等待時間[3]。對于GI/M/1排隊系統(tǒng)，可以在顧客的到達時刻構造嵌入馬爾可夫鏈，運用到達過程的Laplace-Stieltjes變換得到GI/M/1排隊系統(tǒng)平均等待時間的解析表達式[3]。

GI/G/1排隊系統(tǒng)通常不具有馬爾可夫性，理論上無法求解系統(tǒng)性能指標的解析表達式，以往關于這一系統(tǒng)的研究主要是近似分析。近似分析方法包括兩類:擴散近似和啟發(fā)式近似。Kobayashi[4]運用高斯過程及其擴散方程，研究了GI/G/1排隊系統(tǒng)及一般排隊網(wǎng)絡中隊長的近似概率分布。Heyman[5]通過構造近似擴散過程，得到了GI/G/1排隊系統(tǒng)的等待時間和隊長分布。Kr?mer和Langenbach-Belz[6]使用啟發(fā)式方法提出了平均等待時間和等待概率的近似表達式。Gelenbe[7]使用不同的擴散近似模型研究了GI/G/1排隊系統(tǒng)平均等待時間的近似。Marchal[8]提出使用到達時間間隔和服務時間分布的一階矩、二階矩相關的近似公式分析一般單服務器排隊系統(tǒng)的平均等待時間。

二階近似在到達時間間隔變化較大時很難獲得較好的近似值，在這種情況下，三階矩對GI/G/1排隊系統(tǒng)的平均等待時間有顯著的影響。Myskja[9，10]基于H2/M/1排隊系統(tǒng)的精確結果，根據(jù)到達時間間隔的一階至三階矩和服務時間的一階、二階矩，提出了GI/G/1排隊系統(tǒng)平均等待時間的啟發(fā)式近似。Myskja[10]指出，如果到達時間間隔不服從H2分布，這種三階近似方法表現(xiàn)不佳。為此，Wu等[11]引進服務時間和到達時間間隔的三階矩，對GI/G/1排隊系統(tǒng)平均等待時間的近似方法進行了改進。雖然Wu等[11]利用三階矩的啟發(fā)式近似方法提高了近似的精度，卻無法分析系統(tǒng)的隊長概率分布。

由于GI/G/1排隊系統(tǒng)通常不具有馬爾可夫性，理論上無法精確求解，本文試圖將到達時間間隔和服務時間近似為滿足馬爾可夫性的隨機變量，從而對系統(tǒng)進行近似分析。如果給定隨機變量的一階至三階矩，Bobbio等[12]提出可以用非周期的相位(Phase type，PH)分布擬合一般分布，Osogami和Harchol-Balter[13]提出了用PH擬合任意分布的算法。此外，通過PH分布，可以構造馬爾可夫到達過程(Markovian arrival process，MAP)。

MAP和PH分布具有馬爾可夫性，被廣泛用于排隊系統(tǒng)的研究。Sreenivasan等[14]研究了具有休假的MAP/PH/1排隊系統(tǒng)。Zhao等[15]研究了具有兩類顧客和自主優(yōu)先權的MAP/PH/1排隊系統(tǒng)。Brugno等[16]研究了具有批量服務的MAP/PH/1排隊系統(tǒng)。Ye等[17]研究了具有休假和有限緩沖區(qū)的離散時間MAP/PH/1排隊系統(tǒng)，得到了系統(tǒng)隊長的穩(wěn)態(tài)概率分布以及損失概率等性能指標。但是目前尚未有學者詳細分析MAP/PH/1排隊系統(tǒng)對GI/G/1排隊系統(tǒng)的逼近效果。

本文將GI/G/1排隊系統(tǒng)通過近似方法構建為MAP/PH/1排隊系統(tǒng)，根據(jù)排隊系統(tǒng)相鄰到達時間間隔的一階至三階矩將到達過程近似為MAP，根據(jù)服務時間的一階至三階矩將其近似為PH分布。利用矩陣幾何解的方法分析相應的MAP/PH/1排隊系統(tǒng)，得到GI/G/1排隊系統(tǒng)性能指標的近似解，并將本文提出的方法與現(xiàn)有的近似方法進行誤差分析。

1 GI/G/1排隊系統(tǒng)描述

本文研究具有一般性的單服務器排隊系統(tǒng)——GI/G/1排隊系統(tǒng)。這一系統(tǒng)中相鄰顧客到達時間間隔XG獨立且服從一般分布，服務時間SG也是獨立同分布的，XG和SG相互獨立。假設XG和SG的i階矩存在，分別記為和，i=1，2，3。XG和SG的平方變異系數(shù)分別是，，且

系統(tǒng)緩沖區(qū)無限大，按照先到先服務的規(guī)則服務。假設系統(tǒng)的到達率為λ，，服務速率為μ，，服務強度ρ=λ/μ，且ρ＜1。

2 GI/G/1排隊系統(tǒng)的近似分析方法

本節(jié)將GI/G/1排隊系統(tǒng)的到達過程近似為MAP，服務時間近似為PH分布，將GI/G/1排隊系統(tǒng)近似為MAP/PH/1排隊系統(tǒng)。通過分析相應的MAP/PH/1排隊系統(tǒng)，得到GI/G/1排隊系統(tǒng)性能指標的近似解。

2.1 服務時間的近似

首先根據(jù)服務時間SG的i階矩(i=1，2，3)，將其分布近似為PH分布，記為(β，T)，其中β為1×n向量，T為n×n矩陣。服從PH分布的服務時間SPH的i階矩為[18]

式中:e為所有元素都為1的列向量。

構造(β，T)的基本原則是SPH的一階至三階矩分別與SG的一階至三階矩相等，即

將E k-1，k(α)表示為PH分布的形式(β，T)如下

將H2(p1，p2；α1，α2)表示為PH分布的形式(β，T)如下

通過求解上述方程組，可得p1，p2，α1，α2，從而得到服務時間的近似PH分布(β，T)。

2.2 到達過程的近似

根據(jù)到達時間間隔XG的i階矩(i=1，2，3)，構造馬爾可夫到達過程(D0，D1)，其中D0和D1是m×m矩陣，D0表示沒有顧客到達的情況下MAP的狀態(tài)轉移速率矩陣，D1表示有顧客到達的情況下MAP的狀態(tài)轉移速率矩陣。到達時間間隔XMAP的i階矩為[19]

式中:λ=πD1e，π(D0＋D1)e=0，πe=1。

構造(D0，D1)的基本原則是XMAP的i階矩與XG的i階矩相等(i=1，2，3)，即

MAP的構造方法可以通過先構造滿足上述條件的PH分布隨機變量XPH，再由PH分布構造MAP。下面分別針對和兩種情況構造MAP。

令D0=T，D1=-Teβ，則(D0，D1)即為到達過程的MAP近似。

通過求解上述方程組，可得p1，p2，α1，α2，從而得到到達時間間隔的近似PH分布(β，T)。令D0=T，D1=-Teβ，則即為到達過程的MAP近似。

2.3 近似穩(wěn)態(tài)概率分布

由2.1節(jié)和2.2節(jié)的方法，可以將GI/G/1排隊系統(tǒng)近似為MAP/PH/1排隊系統(tǒng)。MAP/PH/1排隊系統(tǒng)可以表示為一個連續(xù)時間的三維馬爾可夫過程Z(t)={N(t)，J(t)，K(t)，t≥0}，其中N(t)為t時刻系統(tǒng)的顧客數(shù)，J(t)為t時刻MAP(D0，D1)的狀態(tài)，K(t)為t時刻服務時間PH分布的狀態(tài)。

馬爾可夫過程Z(t)的生成矩陣Q為

式中

式中:?表示Kronecker積，⊕表示Kronecker和。

Q是一個無窮行、無窮列的三對角矩陣，此馬氏鏈可以通過矩陣幾何解的方法計算穩(wěn)態(tài)概率分布Π=(x0，x1，…)。

Π由ΠQ=0和Πe=1唯一確定，x0為1×m向量，x i為1×mn向量(i≥1)，表示系統(tǒng)里有i個顧客的概率向量，x i有以下的矩陣幾何結構

R滿足

通過求解以下方程組，可以得到x0和x1

因此，GI/G/1排隊系統(tǒng)的近似穩(wěn)態(tài)概率分布為Π=(x0，x1，…)。

2.4 性能指標

由GI/G/1排隊系統(tǒng)的近似穩(wěn)態(tài)概率分布，可得如下性能指標:

(1)平均顧客數(shù):E(L)=x1e＋2x2e＋3x3e＋…=x1(I-R)-2e；

(2)平均逗留時間:E(T)=E(L)/λ=x1(IR)-2e/λ；

(3)平均等待時間:E(W)=E(L)/λ-E(SPH)=x1(I-R)-2e/λ-1/μ。

3 平均等待時間的近似方法

關于GI/G/1排隊系統(tǒng)的近似分析方法較多，本節(jié)總結了目前常用的GI/G/1排隊系統(tǒng)平均等待時間的近似方法，依次記為方法1，方法2，…，方法7，將本文提出的方法記為方法8，如表1所示。

表1 GI/G/1排隊系統(tǒng)平均等待時間的近似方法

續(xù)表1

4 數(shù)值試驗

下面通過數(shù)值試驗介紹怎樣使用本文提出的近似方法分析GI/G/1排隊系統(tǒng)的性能指標，并且驗證其準確性。4.1節(jié)通過實例介紹一個GI/G/1排隊系統(tǒng)如何近似為MAP/PH/1排隊系統(tǒng)及其近似分析的效果，4.2節(jié)將本文提出的方法與現(xiàn)有的近似方法進行誤差分析，比較各近似方法的誤差大小。

4.1 實例分析

假設GI/G/1排隊系統(tǒng)的到達時間間隔分布和服務時間分布分別為XG～Gamma(1/5，6/500)，SG～Gamma(10/7，1/7)，即E(XG)=100/6，E(SG)=10，=5，=0.7，ρ=0.6。

根據(jù)第2節(jié)的方法(見式(14))，將到達時間間隔XG近似為超指數(shù)分布，從而得到到達過程MAP(D0，D1)，且

根據(jù)(7)式將服務時間近似為PH分布(β，T)

通過矩陣幾何解的方法(方法8)可求解系統(tǒng)隊長的概率分布如圖1所示，MAP/PH/1的平均等待時間的近似值為=54.454 4。

圖1 隊長的概率分布

對這個系統(tǒng)進行仿真試驗，統(tǒng)計6×107個顧客的平均等待時間，得到平均排隊時間模擬值ˉW=52.170 3。因此，近似值與模擬值的相對誤差為

為了更直觀地觀察方法1—方法8的近似誤差，圖2給出了SG～Gamma(10/7，1/7)，XG～Gamma(1/5，ρ/50)，ρ∈{0.1，0.2，…，0.9}的情況下各種近似方法相對誤差。圖2顯示方法1、2、5相對其他方法誤差較大；除了方法7，其他方法的相對誤差隨著ρ的增大而逐漸減小。

圖2 平均排隊時間相對誤差比較

4.2 近似方法比較

本文采用平均排隊時間的平均相對百分比誤差R作為評價各種近似方法準確性的指標。

以上任意情形下，當ρ取某確定值時，

E(SG)、和這3個參數(shù)有108種組合，即N=108。對任意的參數(shù)組合i∈{1，2，…，108}，根據(jù)表1計算平均排隊時間近似值，與模擬值比較，從而得到方法1—方法8的平均排隊時間的平均相對百分比誤差。情形1—情形4的誤差比較的結果分別如表2—表5所示，其中下劃線“ ”表示對于某個ρ，所有方法中的最小平均相對百分比誤差，例如表2中，當ρ=0.9時，方法8的平均相對百分比誤差為R=0.27%。

表2—表5的數(shù)據(jù)顯示:

(1)除了方法4和方法7，其他方法的平均相對百分比誤差整體上隨著服務強度ρ的增大而減小(見表2—表5)；

(2)啟發(fā)式的近似方法(方法6—方法8)整體上優(yōu)于基于擴散方程的近似方法(方法1-方法3)(見表2—表5)；

(7)當服務強度ρ較大(ρ→1)時，方法8誤差最小(見表2—表5)。

綜上可見，本文提出的方法8在以上4種情形下均表現(xiàn)較優(yōu)，當或ρ→1時，方法8近似效果最好。雖然方法6和方法7在的情況下估計效果較好，但是無法估計系統(tǒng)隊長的概率分布，方法8可以彌補方法6和方法7的不足。

表2 0＜＜1，0＜＜1時平均排隊時間的平均相對百分比誤差比較

表2 0＜＜1，0＜＜1時平均排隊時間的平均相對百分比誤差比較

ρ 方法1/% 方法2/% 方法3/% 方法4/% 方法5/% 方法6/% 方法7/% 方法8/%0.1 307.19 328.90 2451.27 191.33 28.04 581.36 184.60 23.14 0.2 79.27 118.32 579.32 59.33 12.66 208.43 80.76 10.18 0.3 40.17 64.85 263.97 26.30 10.09 122.17 49.97 5.64 0.4 25.58 40.68 148.69 12.53 8.44 84.64 34.71 3.44 0.5 17.82 26.84 91.29 5.88 6.78 63.03 25.28 2.17 0.6 12.51 17.81 57.52 3.09 5.14 48.27 18.62 1.37 0.7 8.56 11.44 35.49 1.81 3.67 36.76 13.48 0.85 0.8 5.29 6.71 20.11 1.07 2.34 26.71 9.21 0.50 0.9 2.47 3.00 8.73 0.56 1.11 16.46 5.25 0.27

表3 0＜＜1，≥1時平均排隊時間的平均相對百分比誤差比較

表3 0＜＜1，≥1時平均排隊時間的平均相對百分比誤差比較

ρ 方法1/% 方法2/% 方法3/% 方法4/% 方法5/% 方法6/% 方法7/% 方法8/%0.1 1109.13 59.90 1362.11 10.91 20.04 79.23 18.51 4.86 0.2 395.43 26.51 483.45 16.25 12.06 31.73 2.99 2.42 0.3 212.07 15.61 259.02 14.35 7.88 18.73 0.75 1.49 0.4 130.27 10.12 159.13 10.85 5.39 12.66 1.79 0.98 0.5 84.39 6.81 103.15 7.63 3.75 9.02 2.23 0.67 0.6 55.14 4.58 67.45 5.10 2.58 6.47 2.24 0.45 0.7 34.87 2.93 42.70 3.23 1.67 4.54 1.93 0.27 0.8 20.15 1.76 24.70 1.77 1.03 2.82 1.50 0.26 0.9 8.95 0.94 10.97 0.76 0.66 1.39 0.98 0.45

表4 ≥1，0＜＜1時平均排隊時間的平均相對百分比誤差比較

表4 ≥1，0＜＜1時平均排隊時間的平均相對百分比誤差比較

ρ 方法1/% 方法2/% 方法3/% 方法4/% 方法5/% 方法6/% 方法7/% 方法8/%0.1 78.61 70.47 43.69 59.21 81.95 73.32 50.96 71.27 0.2 64.92 56.05 38.21 40.01 71.73 52.86 15.00 50.39 0.3 53.01 45.18 32.30 26.72 62.83 32.63 5.86 31.35 0.4 42.74 36.25 26.67 17.14 54.37 17.38 5.81 17.65 0.5 33.72 28.55 21.43 10.30 45.98 8.12 5.81 9.32 0.6 25.68 21.74 16.55 5.63 37.47 3.00 5.08 4.57 0.7 18.41 15.60 12.01 3.20 28.71 0.84 3.94 1.98 0.8 11.80 10.01 7.78 1.84 19.61 0.68 2.60 0.68 0.9 5.67 4.81 3.77 0.97 10.04 0.71 1.29 0.37

表5 ≥1，≥1時平均排隊時間的平均相對百分比誤差比較

表5 ≥1，≥1時平均排隊時間的平均相對百分比誤差比較

ρ 方法1/% 方法2/% 方法3/% 方法4/% 方法5/% 方法6/% 方法7/% 方法8/%0.1 83.00 62.71 111.30 17.02 67.64 34.70 9.21 39.08 0.2 45.86 47.10 62.17 38.43 53.49 19.51 10.89 20.70 0.3 29.92 36.33 40.46 43.60 43.20 12.98 7.98 11.65 0.4 20.66 28.11 27.80 38.56 34.88 9.62 5.23 6.81 0.5 14.51 21.44 19.41 30.48 27.71 7.50 3.27 4.02 0.6 10.13 15.85 13.44 22.30 21.30 5.88 2.03 2.33 0.7 6.74 11.07 8.91 15.06 15.45 4.44 1.25 1.28 0.8 4.09 6.91 5.32 8.99 10.02 3.02 0.78 0.63 0.9 1.83 3.26 2.37 4.01 4.90 1.56 0.66 0.52

5 結束語

本文提出將GI/G/1排隊系統(tǒng)通過近似方法構建為MAP/PH/1排隊系統(tǒng)，即具有馬爾可夫性的排隊系統(tǒng)，通過分析MAP/PH/1排隊系統(tǒng)，得到GI/G/1排隊系統(tǒng)的近似數(shù)量指標。數(shù)值試驗結果表明當?shù)竭_過程的平方變異系數(shù)小于1或ρ→1，本文提出的方法近似效果較優(yōu)。后續(xù)研究可以對到達過程的平方變異系數(shù)大于1的情況進行修正，以提高近似分析的精度，或者利用這一方法研究更復雜的排隊系統(tǒng)，例如GI/G/m排隊系統(tǒng)以及排隊網(wǎng)絡等。