biliili Link：https://www.bilibili.com/video/BV1eP4y1f7a1/?spm_id_from=333.337.search-card.all.click&vd_source=ab9cf5374617c2867aaea34af29b53c9

基本概念

排队系统的基本组成部分：

输入过程（顾客按照怎么样的规律到达）
排队规则（顾客按照一定的规则排队等待服务
服务机构（服务机构的设置、服务台的数量、服务的方式、服务时间分布等

输入过程

顾客源：即顾客的总体，可以是有限的，也可以是无限的
顾客的到达方式：顾客单个到达，或成批到达
顾客到达时间间隔分布：即相继顾客到达的时间间隔的分布，常见的概率分布：负指数分布 、k阶爱尔朗分布等

定理：在排队系统中，如果单位时间内顾客到达数服从以$\lambda$为参数的泊松分布，则顾客相继到达的时间间隔服从以$\lambda$为参数的负指数分布

排队规则

排队系统类型：顾客到达时，如所有服务台都正被占用，排队等候的称为等待制，随即离去的称为损失制
排队队列：队列可以是单列，也可以是多列
接受服务的顺序：
- 先到先服务（FCFS）
- 后到先服务（LCFS）
- 随机服务（SIRO）
- 优先服务（PR）

服务机构

服务台数量有单服务台，也有多服务台，其构成形式主要有以下五种：（前三个最重要）

单对——单服务台
单队——多服务台并联式
多队——多服务台并联式
单队——多服务台串联式
单队——多服务台串并联混合式

排队系统模型

标准格式：A/B/C/D/E/F，顾客到达时间间隔分布/服务时间分布/服务台（员）数目/系统中顾客容量限制/顾客源数目/服务规则

顾客到达时间间隔分布：M——负指数分布
服务时间分布：M——负指数分布
服务台数目：1——一个服务台，C——多个服务台
系统中顾客容量限制：$\infty$——系统中顾客容量无限制，N——系统中最多容纳N个顾客
顾客源数目：$\infty$——顾客源数目无限多，N——顾客源的总体有N个
服务规则：FCFS——先到先服务

常见的排队系统模型

M/M/1/$\infty$/$\infty$/FCFS
M/M/1/N/$\infty$/FCFS
M/M/1/N/N/FCFS
M/M/C/$\infty$/$\infty$/FCFS
M/M/C/N/$\infty$/FCFS
M/M/C/N/N/FCFS

排队系统指标

状态概率分布$P_{n}$：系统中有n个顾客的概率
队长$L$：系统的平均顾客数
排队长$L_{q}$：系统中排队等待的平均顾客数
顾客平均停留时间$W$
顾客平均等待时间$W_{q}$

Little公式

\[L = \lambda W \quad \quad L_{q} = \lambda W_{q} \quad \quad W = W_{q}+ \frac{1}{\mu} \quad \quad L = L_{q}+\frac{\lambda}{\mu}\]

$\lambda$ —— 单位时间内顾客的平均到达率
$\mu$ —— 单位时间内服务台的平均服务率
$\frac{1}{\mu}$——相邻两个顾客到达的平均间隔时间
$\frac{1}{\mu}$——对每个顾客的平均服务时间
$\rho = \frac{\lambda}{\mu}$——服务台的繁忙程度

马尔可夫（Markov）排队模型

生灭过程

马尔可夫排队模型

平衡状态方程

平衡状态：对于任一状态n，“流入”=“流出”

\[N(t)的分布P_{n}(t) = P \lbrace N(t)=n \rbrace ,n=0, 1, 2,... \implies P_{n}，平衡状态\]

We have:

状态0：$P_{1} \mu_{1} = P_{0} \lambda_{0} \implies P_{1} = \frac{\lambda_{0}}{\mu_{1}}P_{0}$

状态1：$P_{0} \lambda_{0} + P_{2} \mu_{2} = P_{1} \mu_{1} + P_{1}\lambda_{1} \implies P_{2} = \frac{\lambda_{1}\lambda_{0}}{\mu_{2}\mu_{1}}P_{0}$

$\cdot \cdot \cdot$

状态n：$P_{n-1} \lambda_{n-1} + P_{n+1} \mu_{n+1} = P_{n} \mu_{n} + P_{n}\lambda_{n} \implies P_{n} = \frac{\lambda_{n-1}\lambda_{n-2}…\lambda_{0}}{\mu_{n}\mu_{n-1}…\mu_{1}}P_{0}$

$\because P_{0}+P_{1}+…+P_{n}=1$

$\therefore P_{0} = (1+\sum_{n=1}^\infty \frac{\lambda_{n-1} \lambda_{n-2}… \lambda_{0}}{\mu_{n} \mu_{n-1}…\mu_{1}})^{-1}$

M/M/1/$\infty$/$\infty$/FCFS排队模型

模型含义：

顾客到达过程遵循泊松流，服务时间服从负指数分布，单服务台，系统容量和顾客来源无限，先到先服务。设单位时间内顾客平均到达率为$\lambda$，单位时间内服务台平均服务率为$\mu$。

M/M/1模型可以理解为马尔可夫排队模型中的$\lambda$和$\mu$为统一值。

回忆一下各个指标：

状态概率分布$P_{n}$：系统中有n个顾客的概率

队长$L$：系统的平均顾客数

排队长$L_{q}$：系统中排队等待的平均顾客数

顾客平均停留时间$W$

顾客平均等待时间$W_{q}$

状态概率$P_n$

可以计算得，状态概率$P_{n} = \rho^nP_0$

$\because P_0+P_1+…+P_n = 1$

$\therefore P_0+\rho P_0+…+\rho^nP_0 = 1$

由等比数列可以求解得：

系统中没有顾客的概率：$P_0 = 1-\rho$，即可知系统中有n个顾客的概率为：$P_n = \rho^n(1-\rho)$

队长$L$

\[L = \sum_{n=0}^{\infty}nP_n = \sum_{n=0}^{\infty}n\rho^n(1-\rho) = \rho \sum_{n=0}^{\infty}(1+\rho+\rho^2+...+\rho^n+...)\]

通过级数公式求解得：$L = \frac{\rho}{1-\rho}$

排队长$L_q$

\[L_q = L - \frac{\lambda}{\mu} = \frac{\rho^2}{1-\rho}\]

顾客平均停留时间$W$

\[W = \frac{L}{\lambda} = \frac{1}{\mu-\lambda}\]

顾客平均等待时间$W_q$

\[W_q = \frac{L_q}{\lambda} = \frac{\lambda}{\mu(\mu-\lambda)}\]

顾客到达后必须等待k个以上顾客的概率P(n>k)

\[P(n>k) = \sum_{n=k+1}^{\infty}P_n = 1-\sum_{n=0}^{k}P_n = \rho^{k+1}\]

顾客停留时间超过给定时间t的概率

\[P(T>t) = e^{-(\mu-\lambda)t}\]

M/M/C/$\infty$/$\infty$/FCFS排队模型

模型含义：

顾客到达过程遵循泊松流，服务时间服从负指数分布，C个服务台，系统容量和顾客来源无限，先到先服务。设单位时间内顾客平均到达率为$\lambda$，单位时间内服务台平均服务率为$\mu$。

常见指标

假设到达n个顾客，那么系统的平均服务率为：$\mu_n = min(n, C)\mu$
服务台的繁忙程度：$\rho = \frac{\lambda}{C\mu}$
系统中没有顾客的概率$P_0$：$P_0=\left[ \sum_{i=0}^{C-1}\frac{1}{i!}(\frac{\lambda}{\mu})^i+\frac{1}{1-\rho}\frac{1}{C!}(\frac{\lambda}{\mu})^C \right]^{-1}$
系统中有n个顾客的概率$P_n$：$P_n = \begin{cases} \left[ \frac{1}{n!} (\frac{\lambda}{\mu}^i) + \frac{1}{1-\rho}\frac{1}{C!}(\frac{\lambda}{\mu})^C \right]^{-1} , & \text{n<=C} \\ \frac{1}{C!C^{n-C}}(\frac{\lambda}{\mu})^n P_0, & \text{n>C }\end{cases} $
排队长$L_q$：$L_q = \frac{1}{C!}(\frac{\lambda}{\mu})^C \frac{\rho}{(1-\rho)^2}P_0$
队长L：$L = L_q + \frac{\lambda}{\mu}$
顾客平均停留时间W：$W = \frac{L}{\lambda}$
顾客平均等待时间$W_q$：$W_q = \frac{L_q}{\lambda}$
顾客到达后必须等待k个以上顾客的概率$P(n>k)$：$P(n>k) = 1-\sum_{n=0}^{k}P_n$

Queuing Theory —— 排队论