平均負荷不足以描述排隊
即使平均到達率低於服務率,服務站仍可能排隊,因到達及服務完成並非完全定時。模型可以量化這種波動,但結論依賴明確假設。
定義 8.3.1
(M/M/1 排隊及其交通強度)
顧客按速率 的 Poisson 過程到達,服務時間是速率 的獨立指數隨機變量,到達與服務互相獨立。一個服務台在系統非空時持續工作,按先到先服務次序服務;等候空間無限,顧客不會中途離開。令 為等候及正在受服務的顧客數。它是一條連續時間 Markov 鏈,由 以速率 跳到 ,而由 以速率 跳到 。交通強度是 。
穩態平衡
定理 8.3.2
(M/M/1 排隊的穩態分布)
若 ,隊長鏈有唯一的穩態分布
若 ,則不存在穩態概率分布。
證明
(平衡方程強制幾何分布)
穩態分布 必須平衡總流量。在零狀態,;在 ,
零狀態方程給出 。若對某個 有 ,從第 個方程減去它,便剩下 。由歸納,對所有 有 ,因此任何穩態分布都須有 。
若 ,正規化給出 ,故 。反過來,這些概率之和為一並滿足平衡方程。對此不可約、無爆炸的生滅鏈,正規化不變分布是唯一穩態分布;這裏使用這個標準連續時間 Markov 鏈結果。
若 ,被強制的序列 之和發散,除非 ,而此時每個 。兩者都不能和為一,所以不存在穩態概率分布。這是穩態陳述,不是說每次有限觀察中隊伍每刻都必然增加。
證明透視
由每個狀態一條總方程到每條邊一條割方程
不顯然的一步是歸納:它把每條總流量方程化為更簡單的陳述,即由 上升到 的流量等於由 下降到 的流量。這之所以可行,是因為鏈只在相鄰狀態之間跳動: 與 之間的割恰好被一個向上轉移和一個向下轉移穿過。割方程一旦成立,幾何形式便隨即得出。
假設 只在一處使用,就是正規化。平衡方程本身對每個 都成立; 時失敗的是:被強制的序列不能成為概率分布。唯一性並未在此證明,它來自不可約性與無爆炸性,經引用的 Markov 鏈結果得到。把 代入公式會給出 ,這顯示假設被違反,而不是出現了負概率。
平均人數與服務能力比較
定理 8.3.3
(穩態平均數)
當 ,在穩態下
其中 只計等待者。
證明
(對幾何分布求和)
對 微分得 ,所以
服務台繁忙恰在 時,概率為 。由於 ,得 。
這些是穩態平均數,不是容量上限,也不是某一時刻的保證。
例題 8.3.4
(穩定的服務站)
若每小時 、,則 、。系統平均人數為 ,等候的平均人數為 。繁忙概率為 不代表系統每刻恰有兩人。
例題 8.3.5
(比較兩個服務率)
假設某個示範成本模型每小時按 收取服務能力成本,並按系統內每名平均顧客收取三個成本單位。固定 ,只比較 和 。當 ,、。總成本率分別是 和 ,故 在這兩個選項中較佳。能力成本公式是明確的建模假設,不是普遍的人手定律;此比較不能證明其他服務率之間的最優性。
例題 8.3.6
(接近臨界的負荷)
保持 ,把到達率提高到 。則 ,而
到達率由 增至 ,只增加百分之四十五,平均人數卻乘以 。當 趨近一,穩態平均數無界增長;到 時便不存在穩態分布。
常見錯誤
反例模式
有限平均數不能界定每次觀察
在到達率為 2、服務率為 3 的服務站中,每個穩態概率都是正數。穩態平均人數為二,但觀察到至少三人的概率是幾何尾概率 。不能把平均人數說成隊伍人數上限。
常見錯誤
(在 時使用穩定公式)
若 、,公式 給出 名顧客。這個數字沒有意義:定理的假設 不成立,根本沒有可供平均的穩態分布。
常見錯誤
(混淆系統內人數與等候人數)
包括正在受服務的顧客, 則不包括。在穩定服務站中兩者分別是 與 。差額是繁忙概率 ,而不是 ,因為服務台有 的概率閒置。
練習
快速檢查
(若 、,求 、 和 。)
解答 · 答案
、、。
快速檢查
(在 、 的穩定服務站,求穩態下的 。)
解答 · 答案
幾何尾和為 。
快速檢查
(解釋為何此模型中 沒有穩態概率分布。)
解答 · 答案
時,平衡強制每個 。常數非負序列之和為 或發散,永遠不會等於一。
快速檢查
(若 、,求穩態繁忙概率和平均等候人數。)
解答 · 答案
,故繁忙概率為 ,。