# Queuing Theory (CH1)

###### tags: `NTHU CLASS`

## 1.1 Measures of System Performance

下圖(Figure 1.1)展示出了典型的排隊系統，顧客會抵達並等待被系統服務，等接收並完成服務後便離開系統。但有些顧客可能會在接收到服務之前在離開系統，也許是因為他們厭倦了排隊等候，或者因為沒有 waiting room 讓他們進入系統等待。


<br/>

## 1.2 Characteristics of Queueing Systems

以下六個基本特徵用來描述一個排隊系統

- **1. Arrival pattern of customers:** 顧客到達系統之間隔時間的機率分佈
- 顧客有可能"不排了(balking)"、"排到一半放棄(reneging)" 或 "換人少的隊伍排(jockeying)"
- **Stationary:** 顧客數不隨時間而變(time-invariant)
- **Non-stationary:** 顧客數隨時間而變(time-variant)

- **2. Service pattern:** 顧客的服務時間會遵循一些機率分佈
- Service 可以是 single 或 batch
- **State-dependent on service rate:** 排隊的人多的時候服務加快或變慢
- 是否 "Stationary" 是根據 operation time 來判斷而不是根據顧客的數量

- **3. Queue discipline:** 排隊的紀律與方式 (有以下幾種)
- **First come first service (FCFS)** 早進來排隊的人先服務
- **Last come first service (LCFS)** 晚近來排隊的人先服務
- **Random order (RSS):** 隨機選人服務，與排隊順序無關
- **Priority:** 根據優先層級
- **Preemptive:** 先服務優先層級高的顧客
- **Non-preemptive:** 先服務優先層級低的顧客

- **4. System capacity:** waiting room 的數量，通常假設 waiting room 的數量為 infinite 以方便計算

- **5. Number of server:** 增加 server 的數量會增加成本，但是為可以顧客降低延遲
- 在多伺服器系統中又有兩種 case (Figure 1.2)
- 一個 Queue 對到多個伺服器
- 一個 Queue 對一個伺服器


- **6. Stages of service:** 一個排隊系統可能只有一個服務階段，也可能有多個服務階段 (Figure 1.3)
- 以健康檢查為例，你必須經過很多個檢查環節像是視力、牙齒、聽力等，而每個環節都需要排隊


<br/>

## 1.2.7 Notation (符號)

符號只是在排隊理論中用來簡單描述一個排隊系統的標記，其欄位如下所示

- **A / B / X / Y / Z**
- **A:** Interarrival time distribution (相鄰兩位顧客的時間間隔之機率分佈)
- **B:** Service pattern (在 1.2 節中有解釋)
- **X:** Number of parallel servers (在 1.2 節中有解釋)
- **Y:** Waiting room 的大小 (在 1.2 節中有解釋)
- **Z:** Queue discipline (在 1.2 節中有解釋)

- **例如:** M / M / 1 / $\infty$ / FCFS = M / M / 1
- M 放在 A 欄中時是指 Poisson arrival process
- M 放在 B 欄中時是指 Exponential service pattern

- 下表 (Table 1.1) 為 A / B / X / Y / Z 的各種 Symbol


<br/>

## 1.3 Little's Law

Little's Law 敘述了三種基本量詞之間的關係

- $L=\lambda W$
- $L$ = mean number of customers in system (系統內平均人數)
- $\lambda$ = mean customer arrival rate (平均顧客到達數)
- $W$ = mean system time (系統平均時間 - 也包含顧客等待及被服務的時間)

> 只要滿足 customer 不會在排隊系統中排到消失不見，並且 customer 不會從系統中無中生有，就都可以使用 Little's Law

下圖的紅色斜線部分面積即為所有 customers 在 system 中所待的時間加總


<br/>

### EXAMPLE 1.1

- 一間小學有六個年級。每年都會有 30 名新生進入一年級。請問整個小學有多少學生?

**[SOL]**
每年來 30 位新生 $\to \lambda =30$
每位學生都要在學校待 6 年 $\to W=6$
根據 Little's Law，學校共有 $\to L=\lambda W=30\times 6=180$ 位學生

<br/>

### EXAMPLE 1.3

- 下圖 (Figure 1.6) 說明的一個排隊系統。其 Little's Law 為 $L_q=\lambda W_q$

其中 $L_q$ 是平均 Queue 中的顧客數量，$W_q$ 是平均顧客在 Queue 中所花費的時間，而 Queue 的 arrival rate $\lambda$ 則與整個系統相同。


<br/>

### EXAMPLE 1.4

- 下圖 (Figure 1.7) 中，$L$ 代表 service 的平均顧客數量，由於此系統只有一個 server，因此 $L=0\times p_0+1\times (1-p_0)$，其中 $p_0$ 是系統為空的時間比例，$W$ 代表顧客在 service 中花費的時間，而 $W=E[S]$ ($S$ 為隨機服務時間)，假設 arrival rate 為 $\lambda$，則

**[SOL]**
$L=\lambda W\to 1-p_0=\lambda E[S]$

> 當系統中有多個 server 時，$L\neq 1-P_0$


<br/>

### EXAMPLE 1.5

- 下圖 (Figure 1.8) 為 blocking 的排隊系統，blocking 會發生在 capacity 有限的系統中，當一個顧客來到系統時發現已經排滿了，就會直接離開系統。假設 $p_b$ 是被 block 而沒有進入系統的比例。

**[SOL]**
因此可以進入系統的顧客數為 $(1-p_b)\lambda$
故根據 Little's Law 可以得到 $L=(1-p_b)\lambda W$


<br/>

## 1.5 General Results

- Table 1.2 總結了一些關鍵的 notation


- 上表中的 $L,\ L_q,\ W,\ W_q$ 又有下圖 (Figure 1.11) 關係


- 下表 (Table 1.3) 總結了 G/G/c 和 G/G/1 Queue 的結果


當 $\rho=1$ 時，arrival rate 會剛好等於最大的 service rate。因此，若要求最少的 parallel servers 數量 (c )，並令 $\rho=\frac{\lambda}{c\mu}<1$，最後再求出 c 即可

> 滿足此條件的 c 就可以讓系統達到 steady-state

<br/>

## 1.6 Simple Bookkeeping for Queues

- Table 1.5 為 notation 以及一些基本關係


<br/>

### Case 1


1. $T^{(n)}$ 為第 n 位與第 n+1 位顧客來到系統的時間差
2. $W_q^{(n)}$ 為第 n 位顧客在 Queue 中等待的時間
3. $S^{(n)}$ 為第 n 位顧客被服務的時間

可以發現他們之間有這樣的關係

$T^{(n)}+W_q^{(n+1)}=W_q^{(n)}+S^{(n)}$

$\to W_q^{(n+1)}=W_q^{(n)}+S^{(n)}-T^{(n)}>0$

<br/>

## 課後練習

> 3, 5, 10, 11, 12, 13, 14, 15, 16

### P1.3

- A fastfood Indian restaurant must decide on how many parallel service channels to provide. They estimate that, during the rush hours, the average number of arrivals per hour will be approximately 40. They also estimate that, on average, a server will take about 5.5 min to serve a typical customer. Using only this information, how many service channels will you recommend they install?

**[SOL]**
平均每小時的 arrival rate 為 40 人 $\to \lambda =40$

每個 server 平均要花費 5.5 分鐘來服務一位客人 $\to \frac{1}{\mu}=5.5(min)=\frac{5.5}{60}(hour)$
代表每小時每個 server 可以服務 $\mu =\frac{60}{5.5}=10.91$ 人

$\because\frac{\lambda}{c\mu}=\frac{40}{10.91c}<1\to c>\frac{40}{10.91}=3.67$
$\therefore$ 至少需要 4 個 service channel 才能達到 steady-state

<br/>

### P1.5

- The Outfront BBQ Rib Haven does carry out only. During peak periods, two servers are on duty. The owner notices that during these periods, the servers are almost never idle. She estimates the percent idle time of each server to be 1 percent. Ideally, the percent idle time would be 10 percent to allow time for important breaks.
- **(a)** If the owner decides to add a third server during these times, how much idle time would each server have then?
- **(b)** Suppose that by adding the third server, the pressure on the servers is reduced, so they can work more carefully, but their service output rate is reduced by 20 percent. What now is the percent time each would be idle?
- **(c\)** Suppose, instead, that the owner decides to hire an aid (at a much lower salary) who servers as a gofer for the two servers, rather than hiring another full server. This allows the two servers to decrease their average service time by 20 percent (relative to the original service times). What now is the percent idle time of each of the two servers?

**[SOL]**
**(a)**
每個 server 都為 idle 的機率為 0.01 $\to P_{busy}=1-0.01=0.99$
$\because c=2\to c\cdot P_{busy}=2\times 0.99=1.98=\frac{\lambda}{\mu}$
如果 $c=3$ 則 $P_{busy}=\frac{1.98}{3}=0.66\to P_{idle}=1-0.66=0.34$
$\therefore$ 每個 server 都是 idle 的機率為 $34\%$

**(b)**
$\because$ service output rate 降低 20% $\to \mu^{'}=0.8\mu\ and\ c=3$
$\therefore P_{busy}=\frac{\lambda}{c\mu^{'}}=\frac{\lambda}{2.4\mu}=\frac{1.98}{2.4}=0.825\to P_{idle}=1-0.825=0.175$
$\to$ 每個 server 都是 idle 的機率為 $17.5\%$

**(c\)**
令 $\mu_n$ 為新的 service rate
降低 service time 20% $\to \frac{1}{\mu_n}=0.8\cdot \frac{1}{\mu}\to \mu_n=1.25\mu$
$\therefore P_{busy}=\frac{\lambda}{2\mu_n}=\frac{\lambda}{2\times1.25\mu}=\frac{\lambda}{2.5\mu}=\frac{1.98}{2.5}=0.792\to P_{idle}=1-0.792=0.208$
$\to$ 每個 server 都是 idle 的機率為 $20.8\%$

<br/>

### P1.10

- Suppose that an M/G/1/K queue has a blocking probability of $p_k = 0.1$ with $\lambda=\mu=1$ and $L=5$. Find $W$, $W_q$, and $p_0$.

**[SOL]**
**(1)**
$L=\lambda W$
$\Rightarrow L=(1-p_k)\lambda W$
$\Rightarrow 5=(1-0.1)W$
$\Rightarrow W=\frac{50}{9}$

**(2)**
$W=W_q+\frac{1}{\mu}$
$\Rightarrow \frac{50}{9}=W_q+1\Rightarrow W_q=\frac{41}{9}$

**(3)**
$\rho=\frac{\lambda}{c\mu}$
$\Rightarrow \rho=\frac{0.9\lambda}{1}=0.9$
$\Rightarrow p_0=1-\rho=0.1$

<br/>

### P1.11

- Suppose that it costs $3 to make one dose of the small pox vaccine. Once a dose is made, its shelf life is 90 days, after which it can no longer be used. It is desired to have, on average, 300 million doses available at any given time.
- **(a)** What is the yearly cost to implement this plan?
- **(b)** Suppose now that the shelf life of a vaccine is randomly distributed according to an Erlang distribution with a mean of 90 days and a standard deviation of 30 days. What is the yearly cost to implement this plan?
- **(c\)** Suppose that a vaccine with a longer shelf life can be made, but at a greater cost. It is found that the cost to produce a vaccine with a shelf life of x days is equal to $a+bx^2$, where $a=$\$$2.50$ and $b=$\$$0.00005$. What is the shelf life that minimizes the yearly cost?

**[SOL]**
**(a)**
$\lambda=300(million)\times3=900(million)$
$W=\frac{365}{90}$
$L=\lambda W=900\times\frac{365}{90}=3650(million)$

**(b)**
$L=900\times\frac{365}{X}$
$E[L]=900\times\frac{365}{E[X]}=900\times\frac{365}{90}=3650(million)$

**(c\)**
$\lambda=300\times(2.5+0.00005x^2)=750+0.015x^2(million)$
$W=\frac{365}{x}$
$L=\frac{273750}{x}+5.475x$
$\Rightarrow\frac{dL}{dx}=\frac{-273750}{x^2}+5.475=0\Rightarrow x=223.61 (days)$

<br/>

### P1.12

- Customers who have purchased a Delta laptop may call a customer support center to get technical help. Initially, a call is handled by a regular service representative. If the problem cannot be handled by a regular service representative, the call is transferred to a specialist. 20% of all calls are transferred to a specialist. On average, there are 40 customers being served or waiting to be served by a regular representative. On average, there are 10 customers being served or waiting to be served by a specialist. The average rate of incoming calls is 100 per hour. There are 30 regular representatives and 10 specialists.
- **(a)** What is the average time spent in the system for an arbitrary customer? State any assumptions you make to answer this question.
- **(b)** What is the average time spent in the system for a customer who needs to talk to a specialist?


**[SOL]**
**(a)**

**(b)**

<br/>

### P1.13

- Consider the following (very) simplified model of Social Security. Every year, 3 million people turn 65. A person begins to receive Social Security benefits when s/he reaches an age of 65 years. An individual (over the age of 65) has a 5% chance of dying each year, independent of all else. Social Security benefits are $40,000 per person per year.
- **(a)** On average, how long does a person receive Social Security benefits?
- **(b)** What is the average total yearly payout in Social Security benefits?

<br/>

### P1.14

- Planes arrive at a circular sector of airspace according to a Poisson process with rate 20 arrivals per hour. The radius of the sector is 40 miles. Each plane travels at a speed of 400 miles per hour. There are 4 possible entrance / exit points in the sector, as shown. An aircraft is equally like to arrive and depart from any of points A, B, C, and D (but an aircraft cannot enter and exit from the same point). For example, the probability that an aircraft arrives at point A is 1/4. Given that an aircraft arrives at A, the probability that it exits at B, C, or D is 1/3 each. Assume that aircraft flights are straight paths and there are no collisions or conflict avoidance maneuvers in the sector.
- **(a)** What is the average path length across the sector?
- **(b)** What is the average number of aircraft in the sector?
- **(c\)** If we suppose that aircraft sometimes execute avoidance maneuvers to prevent conflicts/collisions, would the answer in (b) go up or down?


<br/>

### P1.15

<br/>

### P1.16