--- # System prepended metadata title: Queueing Theory - Chapter 1 Introduction tags: [Queueing Theory] --- # Queueing Theory - Chapter 1 Introduction contributed by <[`kaeteyaruyo`](https://github.com/kaeteyaruyo)> ## 1.1 Measures of System Performance ![](https://i.imgur.com/ytw5qlr.png) > Figure 1.1 一個 queueing system * 一個排隊系統 (queueing system) 如 Figure 1.1 所示，使用者從**入口**進去，進入**隊伍 (queue)** 排隊，等到有**服務員 (server)** 空閒時就可以被服務，被服務完之後就會從**出口**離開隊伍 * 如果一個排隊系統有很多個 server，則可以根據他們的排列的方式分成**平行的 server**（每個 server 的功能都一樣）和**序列的 server**（要被一個 server 服務完才能進下一個）兩種。如果沒有特別講都是指平行的那種 * 使用者有時候會有不耐煩的排隊行為 (impatient behavior) * Balking: 沒有進入口就離開了（沒有進入系統） * Reneging: 從隊伍中離開（已經進入系統） * 我們常用以下幾個指標來評估一個排隊系統的效能 ![](https://i.imgur.com/eNdFExh.png =75%x75%) * 等待時間 * Waiting time (= $t_1 - t_0$) * System time (= $t_2 - t_0$) * 上面這兩者的平均和機率分佈 * 在系統 / 隊伍中的顧客人數 * 一樣可以算平均跟機率分佈 * 工作狀況 * Idle time: 沒有顧客在系統 / server 中的時間長 * Busy period: 有顧客在系統 / server 中的時間長 * 上面這兩者的平均和機率分佈 ## 1.2 Characteristics of Queueing Systems * 每次都要畫圖說明一個排隊系統很麻煩，我們只要可以清楚說明一個排隊系統的幾個關鍵特色，其實別人就可以理解我們腦中想的排隊系統長怎樣了。這些特色包含 * 顧客抵達的 pattern * server 服務顧客的 pattern * server 的數量 * 系統的容量 * 排隊的準則（誰排前面誰排後面） * 如果是序列型的 server 的話，要額外描述 number of service stage（server 有幾關） ### 1.2.1 Arrival Pattern of Customers * interarrival times 的機率分佈 * 有時候一次的 arrival 會帶來很多個顧客，這種狀況叫作 Bulk arrival 或是 Batch arrival * 此時我們會看到來顧客數量的機率分佈 * 也會看 batches 之間的 interarrival time 的機率分佈 * 是否允許不耐煩的排隊行為 * Balking, reneging and jockeying（有多個隊伍的時候換隊伍） * Arrival pattern 是否會隨時間而改變 * 如果不會,稱作 stationary arrival pattern * 如果會，則稱作 nonstationary arrival pattern ### 1.2.2 Service Patterns * service times 的機率分佈 * 如果一個 server 一次可以服務好多個顧客，那稱作 batch service * 服務速率是否會跟當下系統的狀態有關 * Service pattern 是否會隨時間而改變 * 同樣分做 stationary 和 nonstationary ### 1.2.3 Number of Services * 一個 server * 很多個 server * 整個系統只有一個隊伍 * 每個 server 前都有一個隊伍（只有這種狀況才會發生 jockeying） ### 1.2.4 Queue Discipline * 指的是 server 用什麼標準決定下一個要服務哪個顧客 * 常見的 queue discipline * First come first serve (FCFS)：先來先服務 * First come last serve (FCLS)：先來後服務 * Random selection for service (RSS)：隨機挑選 * Priority schemes：優先度高的先服務 * Preemptive: 服務可以被中斷，先切去優先度更高的 * Nonpreemptive: 服務不能被中斷 ### 1.2.5 System Capacity * 有些系統的隊伍只有有限的空間（等待區的位子有限），這種系統稱作 finite queueing * 當下一個顧客來到系統的時候，等待區已經滿了，那這個顧客就會被迫 balking （例如：路由器的 buffer 滿的時候會掉包） ### 1.2.6 Stages of Service * 有些系統會有很多個關卡 (stage of service)。例如：醫院的健康檢查。顧客必須先在某個 server 被服務，結束後再去下一個 server，直到所有關卡都完成後才能離開系統 * 有些有多個關卡的系統會有重新回到前面關卡的情況，如下圖所示。例如：工廠的產品在進入品管關卡時如果沒有過關，可能會被送回前面的流程重新製作 ![](https://i.imgur.com/CTm8iZ6.png) > Figure 1.3 Multistage queueing system with feedback. ### 1.2.7 Notation * 我們通常使用 $A / B / X / Y / Z$ 這樣的格式來簡單表達一個排隊系統的上述特色。這種表記法叫作 5 tuples notation * $A$: Interarrival-time distribution * $B$: Service-time distribution * A, B 共用可能出現的 symbol * 可能的 symbol * $M$: Exponential，指數分佈 * $D$: Deterministic，定值 * $E_k$: [Erlang type $k$](https://en.wikipedia.org/wiki/Erlang_distribution) ($k = 1,2,...$) * $H_k$: Mixture of k exponentials，也就是 [hyperexponential distribution](https://en.wikipedia.org/wiki/Hyperexponential_distribution) * $PH$: [Phase-type distribution](https://en.wikipedia.org/wiki/Phase-type_distribution)，見下方說明 * $G$: General，沒有特定的 distribution * $X$: Parallel servers （的個數） * 可能的值： $1,2,...,\infty$ * $Y$: System capacity，不一定要描述 * 可能的值： $1,2,...,\infty$ * 預設是 $\infty$ * $Z$: Queue discipline，不一定要描述 * 可能的值 * FCFS: 先到先服務，沒特別講就是這個 * LCFS: 後到先服務 * RSS: 隨機選擇下一個客戶 * PR: Priority * GD: 沒有特定的選擇規則 * $A$, $B$, $X$ 必須描述， $Y$, $Z$ 則有預設值。例如：$M/M/1$，就是 $A$ 是 $M$， $B$ 是 $M$， $X$ 是 $1$ 的意思 #### Phase type distribution * 基本上就是有 $1,...,k$ 個 state （又叫作 phase）的馬可夫鍊，然後有一個描述狀態間轉移機率的轉移矩陣 $P$ * $P$ 的長相如下，其中 $p_{i,j}$ 的意思是「轉移一次後從 state $i$ 跑到 state $j$ 的機率」 $$\begin{bmatrix} p_{1,1} & \dots & p_{1,k} \\ \vdots & \ddots & \vdots \\ p_{k,1} & \dots & p_{k,k} \end{bmatrix}$$ * 以 $P$ 描述的機率轉移 $n$ 次，就相當於轉移了 $P^n$ 次，矩陣的長相如下，其中 $p^n_{i,j}$ 的意思是「轉移 $n$ 次後從 state $i$ 跑到 state $j$ 的機率」$$\begin{bmatrix} p^{(n)}_{1,1} & \dots & p^{(n)}_{1,k} \\ \vdots & \ddots & \vdots \\ p^{(n)}_{k,1} & \dots & p^{(n)}_{k,k} \end{bmatrix}$$ * $P$ 必須是一個 transient，也就是當 $n \rightarrow \infty$ 時， $P^n \rightarrow 0$ * 在單一個 state $i$ 裏面待的時間必須要呈 exponential distribution with parameter $\frac{1}{\mu_i}$ * 舉例 * Coxian distribution ![](https://www.researchgate.net/profile/Mogens-Bladt/publication/241309412/figure/fig1/AS:669005044011020@1536514640931/A-flow-diagram-leading-to-a-Coxian-distribution.png) * Mixed Erlang distribution ![](https://i.imgur.com/HtlDrUU.png) ## 1.3 The Experience of Waiting * Unoccupied time 感覺上比 occupied time 還要久 * Unoccupied time：等的時候沒事情做 * Occupied time：等的時候有事情做 * Pre-process wait 感覺上比 in-process wait 還要久 * Pre-process wait：還沒被服務，在店門口外面等 * In-process wait：服務到一半，在等下一個服務步驟 * 焦慮會讓等待時間感覺更長 * 不確定要等多久感覺上比知道要等多久（有限等待時間）還要久 * 沒有人來說明要等多久，感覺上比有人來說明要等多久還要久 * 不公平的排隊感覺上比公平的排隊還要久 * 但如果服務品質更好/更有價值，那等更久就還可以忍受 * 一個人等感覺上比一群人一起等還要久 ## 1.4 Little's Law ![](https://i.imgur.com/52XoLgo.png) * **Little's Law** 提供以下三個排隊系統中常見的基本物理量之間的等式關係： $$ L = \lambda W $$ * $\lambda$: 顧客抵達系統的平均抵達率 * $W$: 每個顧客待在系統中的平均時間 * $L$: 長期來看系統當中的平均人數 * 有了 Little's Law， 我們只要知道這三個物理量中的其中兩個，就可以算出第三個 * 例如：我們可以站在一間店的門口數出來的人數，然後問問每個出來的人他們在裏面待了多久，有以上兩者對時間的平均，我們就可以大概推估出這間店當中的平均人數 * Example 1.1 * 有一間小學，每年都有 30 個人入學，每個學生讀滿六年後就會離開 * 在這個系統中， $\lambda = 30$ ， $W = 6$。 根據 Little's Law，這個學校平均每年會有 $30 \times 6 = 180$ 人就讀 * 這例子聽起來很顯而易見，用膝蓋想也知道每年有 30 人入學、總共有六個年級的學校當然是總共 180 個學生。但是如果今天系統的參數不是這麼穩定，那人數的估計就不是那麼簡單，例如： * 如果有學生在唸到一半時轉入 / 轉出呢？ * 如果有學生跳級或留級呢？ * 如果每年的入學人數其實是隨機變化的呢？ * 如果入學人數是逐年增加的呢？ * 我們需要更精確的用數學語言定義 Little's Law 當中的物理量，才可以清楚的描述這些問題 * 考慮一個會有顧客抵達和離開的系統，如上圖 Figure 1.4 ，令 * $A^{(k)}$：第 $k$ 個顧客進入系統的時間點，照大小順序排好，使得 $A^{(k+1)} \geq A^{(k)}$ * $A(t)$：**到時間點 $t$ 為止**累積的進入系統的人數 * $W^{(k)}$：第 $k$ 個顧客在系統中待的時長。顧客不可能在抵達前就離開，所以 $W^{(k)} \geq 0$ * $N(t)$：**在時間點 $t$ 的當下**系統中的人數。也就是符合 $A^{(k)} \leq t \; \land \; A^{(k)} + W^{(k)} \geq t$ 的 $k$ 的數量 * 則上述三個物理量可以用以下極限值來定義 $$ \lambda \equiv \lim\limits_{t \to \infty} \frac{A(t)}{t}, \quad W \equiv \lim\limits_{k \to \infty} \frac{1}{k} \sum_{i=1}^k W^{(k)}, \quad L \equiv \lim\limits_{T \to \infty} \frac{1}{T} \int_0^T N(t)dt. \tag{1.1} $$ * 在此定義下， $\lambda$ 是長期下來的 (long-run) 平均顧客抵達率、 $W$ 是長期下來的平均系統時間、 $L$ 是長期下來的平均系統人數 :::success **Theorem 1.1 [Little’s law]** If the limits $\lambda$ and $W$ in $(1.1)$ exist and are finite, then the limit $L$ exists and $$L = \lambda W.$$ ::: * Theorem 1.1 在討論的是一個**長期平均 (long-run averages)** 的關係。也就是說，在 $(1.1)$ 中這三個物理量都是以趨近無限大的極限值來定義的 * 因為這些物理量是以極限值來定義，所以他們的極限值必須要先存在，這條式子才會有意義，這樣的定義幫我們排除掉了那些等待時間會無限增長的系統。換句話說，我們討論的排隊系統必須是一個**有進有出的系統 (Conservative System)**，才能夠使用 Little's Law * 基於這樣的定義，其實 Theorem 1.1 技術上來說並不是只能用在一個「排隊」系統上，只要是一個「會有人進出」的系統就可以了。系統中間可以當作是一個黑盒子，不管 arrival pattern 和 service pattern 到底是什麼挖割分佈、是先進先服務還是隨便抽人來服務，Little's Law 通通都不在意。只要上述的極限值存在、顧客的抵達時間一定小於離開時間，就可以使用 Little's Law 了 --- * 基於不同的「系統」定義， Little’s Law 可能會導出稍微長得不太一樣的關係式。下列幾個範例會讓我們看到， Little’s Law 其實比較像是一個法則，而不是一條確定的式子。更準確的說，當我們關注的「系統」不一樣的時候， $\lambda$, $W$ 和 $L$ 可能會分別指稱到不同的對象 * Example 1.2 ![](https://i.imgur.com/fpu5BFg.png) * Figure 1.5 描述了一個完整的排隊系統。在這樣的觀點下，$L$ 指的是整個排隊系統中的人數（隊伍中的人數 + 正在被服務的人數）； $W$ 指的是顧客在整個系統當中所花的時間（排隊的時間 + 被服務的時間）。而這兩者之間的關係是 $L = \lambda W$ * 雖然上圖中只有畫出一個 server 跟一個 queue，但其實上述的等式關係在多個 server 或是多個 queue 的情況下也會成立 * Example 1.3 ![](https://i.imgur.com/bVyvM6n.png) * Figure 1.6 中描述的「系統」是整個排隊系統中的隊伍的部份。在這樣的觀點下，$L_q$ 指的是隊伍中的人數； $W_q$ 指的是顧客排隊所花的時間。此時隊伍的抵達率跟整個系統的抵達率是一樣的（都是 $\lambda$）。而這三者之間的關係是 $L_q = \lambda W_q$ * Example 1.4 ![](https://i.imgur.com/bLPU6hE.png) * Figure 1.7 中描述的「系統」是一個只有一個 server 的排隊系統中，那個 single server 的部份。在這樣的觀點下， * 這 server 中要嘛就有一個人，要嘛就沒有人。如果令 $p_0$ 為 server 停擺的時間比例，則長期平均下來隊伍中的人數 $L = 0 \cdot p_0 + 1 \cdot(1 - p_0) = 1 - p_0$ * 令 $S$ 代表顧客服務時間的隨機變數，則長期平均下來顧客待在 server 中的時間就會是 $S$ 的期望值，也就是 $W = E[S]$ * 假設離開這個 server 的離開率跟抵達率差不多，那 server 的抵達率就會是整個排隊系統的抵達率 $\lambda$ * 因此，整個 Little's Law 就可以改寫為 $$ L = \lambda W \\ \Rightarrow 1 - p_0 = \lambda \cdot E[S] \\ $$ * 用這條式子來計算一個排隊系統的效能是很方便的，因為他不依靠任何對於排隊系統的假設（像是服務模式是泊松分佈、先到先服務之類的），只要是 single server 就可以用了 * Example 1.5 ### 1.4.1 Geometric Illustration of Little’s Law ![](https://i.imgur.com/JBXxt86.png) * $A(t)$: 到時間點 $t$ 為止累積的抵達人數，上圖的粗實線 * $D(t)$: 到時間點 $t$ 為止累積的離開系統人數，上圖的點狀虛線 * 每一個圍出來的矩型分別代表每一個顧客的系統時間 * $\int_0^T (A(t) - D(t)) dt$ = 矩型面積總和 = $\sum_{k=1}^{N}W^{(k)}$ $$ \frac{1}{T} \int_0^T \big(A(t) - D(t)\big) dt = \frac{N}{T} \cdot \Bigg(\frac{1}{N} \sum_{k=1}^{N}W^{(k)}\Bigg) $$ * 等號左邊代表平均系統長度 $L$ * $\frac{N}{T} = \lambda$ * 等號右邊的大括號內部代表平均系統時間 $W$ ## 1.5 General Results * Summary of notation ![](https://i.imgur.com/Ep5g7aM.png) * 注意 $\rho$ 和 $r$ 的差異= ## 1.6 Simple Bookkeeping for Queues * 系統假設 * 是個先來先服務 (FCFS) 的系統 * 只有一個服務器 (single server) * 用到的變數 * $A^{(n)}$: 第 $n$ 個客戶的**抵達時間 (arrival time)** * $S^{(n)}$: 第 $n$ 個客戶**被服務的時長 (service time)** * $T^{(n)}$: 第 $n$ 個客戶和第 $n+1$ 個客戶**抵達的時間差 (interarrival time)** * $U^{(n)}$: 第 $n$ 個客戶**開始被服務的時間 (time starts service)** * $D^{(n)}$: 第 $n$ 個客戶的**離開時間 (departure time)** * $W^{(n)}_q$: 第 $n$ 個客戶**在隊伍裡的時間長 (time in queue / waiting time)** * $W^{(n)}$: 第 $n$ 個客戶**在系統裡的時間長 (time in system / system time)** * 這些變數的關係 * $T^{(n)} = A^{(n+1)} - A^{(n)}$ * $U^{(n+1)} = max\{D^{(n)}, A^{(n+1)}\}$（重要，第 $n+1$ 個客戶會在第 $n$ 個客戶離開時開始被服務，前題是當時第 $n+1$ 個客戶已經在系統中） * $D^{(n)} = U^{(n)} + S^{(n)}$ * $W^{(n)}_q = U^{(n)} - A^{(n)}$ * $W^{(n)} = W^{n}_q + S^{(n)}$ * 示意圖 * 第一種狀況 ![](https://i.imgur.com/bMxB18v.png) * $T^{(n)} + W^{(n+1)}_q = W^{(n)}_q + S^{(n)} \Rightarrow W^{(n+1)}_q = W^{(n)}_q + S^{(n)} - T^{(n)}$ * 下一個人要等多久，可以透過上一個人等多久以及被服務多久算出來 * 第二種狀況 ![](https://i.imgur.com/HDiR7Rj.png) * $W^{(n+1)}_q = 0$ * 有時候客戶抵達時系統是空的，那就不用等 * 綜合兩種狀況，等待時間長可以用以下算式 (Lindley’s equation) 計算 $$W^{(n+1)}_q = max\{W^{(n)}_q + S^{(n)} - T^{(n)}, 0\}$$