m/m/1

m/m/1

M/M/1排隊模型(M/M/1 model)是一種單一伺服器(single-server)的(排隊模型),可用作模擬不少系統的運作。

分析

這種模型是一種出生-死亡過程,此隨機過程中的每一個狀態代表模型中人數的數目。因為模型的佇列長度無限且參與人數亦無限,故此狀態數目亦為無限。例如狀態0表示模型閒置、狀態1表示模型有一人在接受服務、狀態2表示模型有二人(一人正接受服務、一人在等候),如此類推。 此模型中,出生率(即加入佇列的速率)λ在各狀態中均相同,死亡率(即完成服務離開佇列的速率)μ亦在各狀態中相同(除了狀態0,因其不可能有人離開佇列)。故此,在任何狀態下,只有兩種事情可能發生:

有人加入佇列。如果模型在狀態k,它會以速率λ進入狀態k + 1

有人離開佇列。如果模型在狀態k(k不等於0),它會以速率μ進入狀態k − 1

由此可見,模型的隱定條件為λ < μ。如果死亡率小於出生率,則佇列中的平均人數為無限大,故此這種系統沒有平衡點。

佇列參數表示

λ:平均到達的顧客數(單位時間平均到達率,個/秒)

μ:平均服務的顧客數(服務率、離開率,個/秒),每客平均服務時間 T= 1/μ,

Lq:平均等待佇列長度(在佇列中排隊等待的顧客數)

Wq:每個顧客的平均等待時間,包括沒有排隊的顧客

L:系統中平均顧客數=正在被服務的顧客數+正在等待的顧客數

W:平均等待時間=平均等待時間+平均服務時間

ρ:平均利用率,一段相當長的時間內可測得 = λ/μ≤1

穩定狀態下的公式

定義

m/m/1m/m/1

則模型在狀態

的機率為

m/m/1m/m/1

由此,可給出各測量數值的公式:

整個系統的平均人數

m/m/1m/m/1

,且其變異(variance)為:(方差)

m/m/1m/m/1

一單位時間內系統完成服務的人數:

m/m/1m/m/1

在佇列中等候服務的人數:

m/m/1m/m/1

一人在系統中的平均逗留(等候+接受服務)時間:

m/m/1m/m/1

一人的平均等候時間:

m/m/1m/m/1

問題-求系統在任意時刻t的狀態n

系統中有n個顧客的機率Pn(t),它決定了系統運行的特徵。 穩定情況下,Pn(t)與t無關,Pn(t)=Pn; 狀態轉移平衡方程:轉入率=轉出率; 狀態i轉移到狀態i+1的轉移率λiPi; 狀態i+1轉移到狀態i的轉移率μi+1Pi+1; 狀態平衡方程:Rate In = Rate Out

0 u1P1= λ0P0

1 λ0P0+ u2P2= (λ1+ u1) P1

2 λ1P1+ u3P3= (λ2+ u2) P2

.... ....................... ................... N -1 λN -2PN -2+ uNPN= (λN -1+ uN -1) PN -1 N λN -1PN -1+ uN+1PN+1= (λN+ uN) PN .... ...................

求穩態狀態解

狀態:0: P1= (λ0 / u1) P0

狀態:1: P2= (λ1 / u2) P1+ (u1P1- λ0P0) / u2 = (λ1 / u2) P1+ (u1P1- u1P1) / u2 = (λ1 / u2) P1 =(λ1λ0/u2u1)P0

狀態:n-1: Pn= (λn -1 / un) Pn -1+ (un -1Pn -1- λn -2Pn -2) / un = (λn -1 / un) Pn -1+ (un -1Pn -1- un -1Pn -1) / un = (λn -1 / un) Pn -1 =(λn-1λn-2λn-3....λn0/un-1un-2un-3...u1)P0

狀態:n : Pn+1= (λn / un+1) Pn+ (unPn - λn -1Pn -1) / un+1 = (λn / un+1) Pn =(λnλn-1λn-2λn-3....λn0/unun-1un-2un-3...u1)P0

簡化過程

Let C = (λn-1λn-2λn-3....λn0/un-1un-2un-3...u1) then Pn = CnP0,Cn = (λ/u)^n = P^n 又∑Pi = 1,則 P0 = 1-ρ Pn = CnP0 = (1-ρ)ρ^n

M/M/1的系統對長

L = ∑n(1-ρ)ρ^n = ∑(nρ^n-ρ^n+1) 為變隊長極其機率的積之和 =ρ/(1-ρ) 或者 = λ/(u-λ)

排隊佇列長度期望值

Lq = ∑(n-1)Pn (第n個顧客到來時的對長為n-1,發生機率) =ρ^2/(1-ρ) 或者 = λ^2/u(u-λ)

舉例

可用M/M/1模型的例子眾多,例如只有一位員工的郵局,只有一佇列。客人進來,排隊、接受服務、離開。如果客人進來的數目符合 泊松過程,且服務時間是 指數分布,則可用M/M/1模擬,並算出平均佇列長度、不同等候時間的機率等。

M/M/1可一般化成為M/M/n模型,使可用時接受服務的人數為大於一。歷史上,M/M/n模型首先被用來模擬電話系統,因為荷蘭工程師Erlang發現客人打電話的速率符合 泊松過程,且通話時間是 指數分布,所以占用通訊線路的數目和等待接線的人數符合M/M/n模型。

相關搜尋

熱門詞條

聯絡我們