趙 寧，黃小峰，劉文奇

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

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

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

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

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

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

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

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

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

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

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

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

本節(jié)將GI/G/1排隊(duì)系統(tǒng)的到達(dá)過程近似為MAP，服務(wù)時(shí)間近似為PH分布，將GI/G/1排隊(duì)系統(tǒng)近似為MAP/PH/1排隊(duì)系統(tǒng)。通過分析相應(yīng)的MAP/PH/1排隊(duì)系統(tǒng)，得到GI/G/1排隊(duì)系統(tǒng)性能指標(biāo)的近似解。

2.1 服務(wù)時(shí)間的近似

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

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

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

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

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

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

2.2 到達(dá)過程的近似

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

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

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

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

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

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

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

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

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

式中

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

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

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

R滿足

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

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

2.4 性能指標(biāo)

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

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

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

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

3 平均等待時(shí)間的近似方法

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

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

續(xù)表1

4 數(shù)值試驗(yàn)

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

4.1 實(shí)例分析

假設(shè)GI/G/1排隊(duì)系統(tǒng)的到達(dá)時(shí)間間隔分布和服務(wù)時(shí)間分布分別為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))，將到達(dá)時(shí)間間隔XG近似為超指數(shù)分布，從而得到到達(dá)過程MAP(D0，D1)，且

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

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

圖1 隊(duì)長的概率分布

對這個(gè)系統(tǒng)進(jìn)行仿真試驗(yàn)，統(tǒng)計(jì)6×107個(gè)顧客的平均等待時(shí)間，得到平均排隊(duì)時(shí)間模擬值ˉ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 平均排隊(duì)時(shí)間相對誤差比較

4.2 近似方法比較

本文采用平均排隊(duì)時(shí)間的平均相對百分比誤差R作為評(píng)價(jià)各種近似方法準(zhǔn)確性的指標(biāo)。

以上任意情形下，當(dāng)ρ取某確定值時(shí)，

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

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

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

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

(7)當(dāng)服務(wù)強(qiáng)度ρ較大(ρ→1)時(shí)，方法8誤差最小(見表2—表5)。

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

表2 0＜＜1，0＜＜1時(shí)平均排隊(duì)時(shí)間的平均相對百分比誤差比較

表2 0＜＜1，0＜＜1時(shí)平均排隊(duì)時(shí)間的平均相對百分比誤差比較

ρ 方法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時(shí)平均排隊(duì)時(shí)間的平均相對百分比誤差比較

表3 0＜＜1，≥1時(shí)平均排隊(duì)時(shí)間的平均相對百分比誤差比較

ρ 方法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時(shí)平均排隊(duì)時(shí)間的平均相對百分比誤差比較

表4 ≥1，0＜＜1時(shí)平均排隊(duì)時(shí)間的平均相對百分比誤差比較

ρ 方法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時(shí)平均排隊(duì)時(shí)間的平均相對百分比誤差比較

表5 ≥1，≥1時(shí)平均排隊(duì)時(shí)間的平均相對百分比誤差比較

ρ 方法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 結(jié)束語

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