# Queueing Theory - 3.4 Choosing the Number of Servers contributed by <[`kaeteyaruyo`](https://github.com/kaeteyaruyo)> ###### tags: `Queueing Theory` * 一個 M/M/c 系統如果要有 steady state,那他的 $\rho$ 值(顧客到來的速度跟系統服務的速度之間的比值)必須要小於 1,否則系統會來不及消耗掉人流,隊伍就會愈來愈長 * 根據這個事實,我們可以推論出 $$ \rho < 1 \Rightarrow \frac{\lambda}{c\mu} < 1 \Rightarrow c > \frac{\lambda}{\mu} = r $$ 意思就是說, M/M/c 系統**至少一定要有 $r$ 個 server** 才會有 steady state * 所以說,想要決定一個 M/M/c 系統的 server 數量 $c$,好讓他可以達到預期的效能指標,就等同於是在決定需要從 $r$ 開始再疊加多少 server 上去,也就是 $$ c = r + \Delta $$ * 一般來說我們在決定總共要放幾個 server 時,會有三種不同的考量方式,這些決策對於排隊系統的效能有不同的影響。以下我們通通都使用 $r = 9, c = 12 \Rightarrow \rho = 0.75$ 的 baseline 來進行說明,我們想要知道,如果系統的負載變大了,$r_{\text{new}} = 36$,那麼我們需要把 server 數增加到多少,也就是 $c_{\text{new}}$ 必須要變成多少,才可以維持排隊系統的效能不變 * Quality domain (QD): 要維持系統的服務品質,因此要維持系統的**繁忙時間比 $\rho$ 約是一個定值**(但不可以比原本差),也就是 $\rho_{\text{new}} \approx \rho$ $$ \rho_{\text{new}} = \rho \Rightarrow \frac{36}{c_{\text{new}}} = 0.75 \Rightarrow \frac{36}{36 + \Delta} = 0.75 \\ \therefore \Delta = 12, \; c_{\text{new}} = 48 $$ * Quality and efficiency domain (QED): 要兼顧系統的服務品質跟布建成本,因此要維持系統的**壅塞程度是一個定值**。但是「壅塞程度」是一個抽象的概念,學術界並沒有一個壅塞程度定義的共識,此處課本僅使用 $1-W_q(0)$,也就是**絕對需要排隊等待的機率**,來代表系統的壅塞程度,其定義式為 $$ C(c, r) \equiv 1 - W_q(0) = \frac{\frac{r^c}{c!(1-\rho)}}{\frac{r^c}{c!(1-\rho)} + \sum_{n=0}^{c-1}\frac{r^n}{n!}} $$ ~~真的是醜到爆炸。~~ 因為跟 $c$ 有關的項次實在太多了,直接解不好解,所以會需要其他的定理來幫助我們快速求得一個理想的 $c$ 值 * (定理待補充) * 新的 server 個數必須要使 $1 - W_q(0)$ 不超過原先的壅塞程度 $\alpha$,以我們考慮的情況來說 $$ C(c, r) = 1 - W_q(0) = 0.266 \\ \Rightarrow C(c_{\text{new}}, r_{\text{new}}) = C(c_{\text{new}}, 36) \approx 0.266 \\ c_{\text{new}} = 42, \; \Delta = 6, \; 1 - W_q(0) = 0.246 $$ * Efficiency domain (ED): 要維持系統的布建成本,因此要維持系統的**多補上的 server 數 $\Delta$ 是一個定值**。也就是說,先算出在原本的情況下,server 數比最低要求的 server 數 $r$ 還要多多少,之後不管環境怎麼變化,就是維持 server 數永遠比最低底線還要多這個麼多個,是一個相當~~偷懶~~沒有彈性的作法 $$ c = r + 3, \; \Delta = 3 \\ r_{\text{new}} = 36, \; c_{\text{new}} = r_{\text{new}} + \Delta = 36 + 3 = 39 $$ ![](https://i.imgur.com/lENvDMd.png) > Table 3.1 Example performance measures for various choices of $c$ * 在 Table 3.1 中,我們將三種不同考量方式對繁忙時間比 $\rho$、壅塞程度 $1 - W_q(0)$,和比 $r$ 多出來的 server 數 $\Delta$ 的影響放在一起比較 * Quality domain 的作法要維持繁忙時間比不可以改變,實際上的意思就是說,每一個員工休息的時間比不可以改變。當系統負載 $r$ 變大的情況下,依然要可以維持這樣的效能量度時,就需要多僱用非常多的員工,因此 $\Delta$ 會變大,布建成本就會上升。但相對的,壅塞程度大幅下降,因此整個系統會變得非常不擁擠,大部分的顧客到來都不會需要排隊,也就是 $$ r \to \infty \Rightarrow 1 - W_q(0) \to 0 $$ * Efficiency domain 的作法要維持布建成本不可以增加,因此會造成另一個極端。原本系統負載沒那麼大的時候,比最低限度多僱用 $\Delta$ 個 server,可能就比例來說會對系統有很大的幫助;但是當負載越來越大時,同樣數量的 $\Delta$ 對於系統的幫助就會愈來愈小,因此每個 server 到後來都會幾乎忙不過來,每個顧客來到隊伍時幾乎都會需要排隊(但隊伍不會愈來愈長,因為我們僱用的 server 數依然有超過最低限度 $r$),也就是 $$ r \to \infty \Rightarrow \rho \to 1, 1 - W_q(0) \to 1 $$ * Quality and efficiency domain 的作法是一個折衷的作法,選擇一個不會造成排隊機率改變的 server 數量。server 增加的數量可能會比 efficiency domain 中的還要多一些,所以成本會比較高一點,但不會多到像 quality ddomain 那樣不惜成本;而每一個 server 都會變得比 quality domain 中的還要更忙一點,但不會忙到像 efficiency domain 一樣無法接受的地步