# Queueing Theory - Chapter 1 Introduction

contributed by <[`kaeteyaruyo`](https://github.com/kaeteyaruyo)>

## 1.1 Measures of System Performance

> Figure 1.1 一個 queueing system

* 一個排隊系統 (queueing system) 如 Figure 1.1 所示，使用者從**入口**進去，進入**隊伍 (queue)** 排隊，等到有**服務員 (server)** 空閒時就可以被服務，被服務完之後就會從**出口**離開隊伍
* 如果一個排隊系統有很多個 server，則可以根據他們的排列的方式分成**平行的 server**（每個 server 的功能都一樣）和**序列的 server**（要被一個 server 服務完才能進下一個）兩種。如果沒有特別講都是指平行的那種
* 使用者有時候會有不耐煩的排隊行為 (impatient behavior)
* Balking: 沒有進入口就離開了（沒有進入系統）
* Reneging: 從隊伍中離開（已經進入系統）
* 我們常用以下幾個指標來評估一個排隊系統的效能
* 等待時間
* 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，直到所有關卡都完成後才能離開系統
* 有些有多個關卡的系統會有重新回到前面關卡的情況，如下圖所示。例如：工廠的產品在進入品管關卡時如果沒有過關，可能會被送回前面的流程重新製作
> 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
* Mixed Erlang distribution

## 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


* **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
* Figure 1.5 描述了一個完整的排隊系統。在這樣的觀點下，$L$ 指的是整個排隊系統中的人數（隊伍中的人數 + 正在被服務的人數）； $W$ 指的是顧客在整個系統當中所花的時間（排隊的時間 + 被服務的時間）。而這兩者之間的關係是 $L = \lambda W$
* 雖然上圖中只有畫出一個 server 跟一個 queue，但其實上述的等式關係在多個 server 或是多個 queue 的情況下也會成立
* Example 1.3
* Figure 1.6 中描述的「系統」是整個排隊系統中的隊伍的部份。在這樣的觀點下，$L_q$ 指的是隊伍中的人數； $W_q$ 指的是顧客排隊所花的時間。此時隊伍的抵達率跟整個系統的抵達率是一樣的（都是 $\lambda$）。而這三者之間的關係是 $L_q = \lambda W_q$
* Example 1.4
* 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


* $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
* 注意 $\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)}$
* 示意圖
* 第一種狀況
* $T^{(n)} + W^{(n+1)}_q = W^{(n)}_q + S^{(n)} \Rightarrow W^{(n+1)}_q = W^{(n)}_q + S^{(n)} - T^{(n)}$
* 下一個人要等多久，可以透過上一個人等多久以及被服務多久算出來
* 第二種狀況
* $W^{(n+1)}_q = 0$
* 有時候客戶抵達時系統是空的，那就不用等
* 綜合兩種狀況，等待時間長可以用以下算式 (Lindley’s equation) 計算 $$W^{(n+1)}_q = max\{W^{(n)}_q + S^{(n)} - T^{(n)}, 0\}$$