M/M/1

維基百科,自由的百科全書
前往: 導覽搜尋

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

M/M/1 schema

依據開恩特羅符號必須有下列的條件:

分析[編輯]

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

  • 有人加入隊列。如果模型在狀態k,它會以速率λ進入狀態k + 1
  • 有人離開隊列。如果模型在狀態kk不等於0),它會以速率μ進入狀態k − 1

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

此模型中有幾項數值常被測量,例如:

  • 一人在系統中的平均逗留時間
  • 一人在接受服務前的平均等候時間
  • 整個系統中的平均人數
  • 等候隊列的平均人數
  • 一單位時間內系統完成服務人數,即服務速度

穩定狀態下的公式[編輯]

緩衝效用 \scriptstyle \rho\,=\,\tfrac{\lambda}{\mu}. 表示服務被佔用的平均機率

平穩過程在狀態i(「i」個總人數,包括正在被服務的)的機率為

\mbox{Prob}(q=i)=\pi_i=(1-\rho)\rho^i.\,

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

  • 整個系統的平均人數N
\overline N=\frac{\rho}{1-\rho},且其方差為
\sigma^2_N = \frac{\rho}{(1 - \rho)^2}.
  • 一單位時間內系統完成服務的人數:
\overline N_S = \lambda \overline x = \rho
  • 在隊列中等候服務的人數:
\overline N_Q = \frac{\rho^2}{1 - \rho}
  • 一人在系統中的平均逗留(等候+接受服務)時間:
T=\frac{1}{\mu-\lambda}.
  • 一人的平均等候時間:
W = \frac{\overline N_Q}{\lambda} = T - \overline x = T - \frac{1}{\mu} = \frac{\rho}{\mu - \lambda}

[編輯]

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

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