為何要有多個服務台
「穩態單服務台排隊」一課推導了 M/M/1 系統的人數分布。實際的服務系統常有多個相同的服務台,而一個核心的設計問題是延遲如何隨服務台數目而變。本單元把 M/M/1 一課的生滅平衡論證推廣到 個服務台,並加入 Little 定律,用它在平均顧客數與平均逗留時間之間換算。假設與前相同:到達間隔與服務時間均為指數分布,沒有顧客中途離開,等候空間無限。
模型與定義
定義 8.8.1
(M/M/c 排隊)
顧客按速率 的 Poisson 過程到達。共有 個相同的服務台;每個服務時間是速率 的指數隨機變量,所有隨機變量相互獨立。顧客按先到先服務次序受理,若所有服務台都忙,到達的顧客須等候。令 為系統內的顧客數(包括等候及正在受服務者)。則 是連續時間生滅鏈,每個狀態的出生率均為 ,狀態 的死亡率為 ,因為只有 個服務台在工作。
定義 8.8.2
(提供負荷、使用率與表現指標)
提供負荷是 ,即若服務台不受限制時平均會有多少個在忙;使用率是 。以 表示系統內有 位顧客的穩態概率, 為系統內平均人數, 為平均等候人數,、 則為到達顧客在系統內及在隊列中的平均時間。
主要結果
定理 8.8.3
(M/M/c 排隊的穩態分布)
穩態分布存在,當且僅當 。此時
證明
(割方程與規範化)
穩態的生滅鏈在 與 之間的割上,兩個方向的概率流相等:。因此 。當 時乘積為 。當 時,每多一項因子為 ,得 。
這些權重可求和,當且僅當 收斂,即 ;此時 是它們之和的倒數,即所述公式,而割方程蘊含平衡方程。若 ,權重不可求和,不存在穩態分布。
定理 8.8.4
(Erlang C 等候概率與平均隊長)
若 ,到達顧客須等候的概率是 Erlang C 量
平均隊長為
證明
(尾部求和與看見時間平均的到達者)
第一式是對穩態分布的幾何尾部求和:。Poisson 到達流所見的系統處於穩態分布(PASTA 性質),故到達者恰在 時須等候,概率為 。至於 ,令 :
其中用到 。
證明透視
Erlang C 公式背後的兩種平均
證明中有兩個看似相同、平均方式卻不同的量。 時 之和是時間平均:所有服務台都忙的時間比例。等候概率則是顧客平均:到達時發現所有服務台都忙的顧客比例。把兩者等同的唯一一步是 PASTA 性質,這也是除了生滅結構之外唯一用到 Poisson 到達的地方。相比之下,隊長公式自始至終都是時間平均,不需要這一步;它只是對幾何尾部的代數運算,而幾何尾部之所以存在,是因為 。
定理 8.8.5
(Little 定律)
設系統處於穩態,顧客以長期速率 進入,且各長期平均存在。若 為系統內顧客數的時間平均, 為顧客在系統內逗留的平均時間,則 。對單獨的等候隊列同樣有 。
證明
(面積論證(概要))
在長時段 內,積分 等於各顧客在系統內逗留時間之和,只差相對於 可忽略的邊界項。若約有 位顧客進入,則總和約為 。除以 即得 。此論證適用於任何顧客集合及任何子系統,特別是隊列。邊界項的嚴格控制留待以後處理。
由於每位顧客的平均服務時間為 ,有 ;對服務台應用 Little 定律,得 。當 ,公式化為 M/M/1 的結果:,,。
例題
例題 8.8.6
(兩個服務台)
設 ,,(每小時)。則 ,。規範化常數為 ,故 。於是 ,而 時 ;驗算:。等候概率為 。於是
驗算:。
例題 8.8.7
(合併服務台與分開排隊)
把上面的兩服務台系統與兩個各自獨立的單服務台隊列比較,各接收一半的到達:,,。每個隊列 ,由 Little 定律 小時;合併系統(總服務能力相同)則為 小時。分開排隊時,顧客可能在另一個服務台閒置時仍在等候;合併排隊消除了這種情況。
例題 8.8.8
(增設第三個服務台)
取 ,,:,,。則 ,故 。因此 ,, 小時, 小時,。驗算 成立。第三個服務台使平均等候由 小時降至 小時。
常見錯誤與細微之處
常見錯誤
(以 而非 判斷穩定性)
當 、,提供負荷 ,但兩服務台系統仍然穩定,因為 。事實上 正是穩定條件;當 , 是充分而非必要的。
常見錯誤
(混淆 與 )
也包括正在受服務者,M/M/c 中 。在兩服務台例子中 ,但 ;用錯其中一個除以 ,便會把 當成 。
常見錯誤
(有顧客被拒時仍用原到達率套用 Little 定律)
Little 定律使用的是實際進入系統的顧客速率。若有部分到達者被拒, 必須換成進入速率;沿用原到達率會低估 。
反例模式
沒有 Poisson 輸入時,到達者未必看見時間平均
聲稱:在任何穩定的單服務台隊列中,到達者須等候的概率等於服務台忙碌的時間比例。取在時刻 0、1、2 等定時到達的顧客,每次服務都歷時半小時。服務台有一半時間在忙,但每位顧客都在下一位到達前半小時離開,所以從沒有到達者需要等候。等候概率是 ,而不是 。Erlang C 的等同需要 Poisson 到達,因為 Poisson 到達者看見的是穩態分布。
穩態分布及 Erlang C 公式依賴指數服務時間;Little 定律則不依賴。與分開排隊的比較只在總到達率相同、服務台相同的條件下成立,而且只比較平均值。
練習
練習 8.8.9
(當 ,,(每小時),計算 、、 與 。)
基礎
解答(3)
- 1
計算負荷與
,。則 ,故 。
- 2
套用 Erlang C 公式
,。
- 3
以 Little 定律換算
小時, 小時,。驗算:。
練習 8.8.10
(當 ,(每小時),求使穩態分布存在的最少服務台數目,以及此時的使用率。)
基礎
解答(2)
- 1
寫出穩定條件
穩定性要求 ,即 。
- 2
取最小整數
故 ,此時 。若 ,則 ,不存在穩態分布。
練習 8.8.11
(某穩定系統平均有 位顧客,每小時有 位顧客到達。求 。若平均服務時間為 小時,求 與 。)
核心
解答(2)
- 1
對整個系統用 Little 定律
小時。
- 2
減去服務時間,再對隊列用 Little 定律
小時,。
練習 8.8.12
(對 、 的系統,列出 並計算 。)
核心
解答(2)
- 1
列出穩態概率
由於 ,,,而 時 。總和為 。
- 2
對幾何尾部求和
,所以 。