排队论

基本概念

输入过程：

顾客源：可以是无限的，也可以是有限的

顾客的到达方式：单个到达或者是成批到达

顾客到达时间间隔分布：负指数分布（单位时间顾客到达数服从 $\lambda$ 为参数的指数分布）

排队规则：

排队系统类型：如果所有服务台都正被占用，等候的称为等待制，随即离去的称为损失制

排队队列可以是单列，也可以是多列

接受服务的顺序：先到先服务（FCFS）、后到先服务（FCFS）、随机服务（SIRO）、优先服务（PR）

服务机构：一般有五种

单对单服务台：一条队对一个服务台

单队对多服务台并联式

多队对多服务台并联式

单队对多服务台串联式

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

排队系统模型表示：$A/B/C/D/E/F$

分别表示：顾客到达时间间隔分布/服务时间分布/服务台数目/系统中顾客容量限制/顾客源数目/服务规则

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

排队系统的指标：

• 状态概率分布 $P_n$：系统中有 $n$ 个顾客的概率
• 队长 $L$：系统的平均顾客数
• 排队长 $L_q$：系统中排队等待的平均顾客数
• 顾客平均停留时间 $W$
• 顾客平均等待时间 $W_q$

马尔可夫排队模型

将一个新顾客到来看作为生，将一个顾客服务完离开看作死，设置 $N(t)$ 为任意时刻 $t$ 排队系统的状态。满足下列生灭过程特征的排队模型称为马尔科夫排队模型：

• 给定 $N(t)=n$，到下一个顾客到达的间隔时间服从参数为 $\lambda_n(n=0,1,2,\dots)$ 的负指数分布；

• 给定 $N(t)=n$，到下一个顾客离开的间隔时间服从参数为 $\mu_n(n=0,1,2,…)$ 的负指数分布；

• 同一时刻只有一个顾客达到或离去。

状态平衡方程：

对于 $N(t)$ 的分布，在平稳状态下，就是状态平衡方程

平稳状态：对于任一状态 $n$，流入的等于流出。

那么可以得出：

$$\begin{align*} 状态 0: & P_1\mu_1 = P_0\lambda_0 & 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 & P_2=\frac{\lambda_1\lambda_0}{\mu_2\mu_1}P_0 \\ 状态 2: & P_1\lambda_1 + P_3\mu_3 = P_2\mu_2 + P_2\lambda_2 & P_3 = \frac{\lambda_2\lambda_1\lambda_0}{\mu_3\mu_2\mu_1}P_0 \\ &\vdots \\ 状态 n: & P_{n-1}\lambda_{n-1} + P_{n+1}\mu_{n+1} = P_{n}\mu_{n} + P_{n}\lambda_{n} & P_n = \frac{\lambda_{n-1}\lambda_{n-2}\cdots\lambda_0}{\mu_{n-1}\mu_{n-2}\cdots\mu_1} P_0 \\ \end{align*}$$

通过 $P_0 + P_1 + P_2 \cdots + P_n = 1$ 可以算出 $P_0$ 那么进一步可以算出其他的

M/M/1/∞/∞/FCFS 排队模型

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

状态平衡方程

$$\begin{align*} 状态 0: & P_1\mu = P_0\lambda & P_1=\frac{\lambda}{\mu} P_0 = \rho P_0\\ 状态 1: & P_0\lambda + P_2\mu = P_1\mu + P_1\lambda & P_2=\rho^2 P_0 \\ 状态 2: & P_1\lambda + P_3\mu = P_2\mu + P_2\lambda & P_3 = \rho^3 P_0 \\ &\vdots \\ 状态 n: & P_{n-1}\lambda + P_{n+1}\mu = P_{n}\mu + P_{n}\lambda & P_n = \rho^n P_0 \\ \end{align*}$$

通过 $P_0 + P_1 + P_2 \cdots + P_n = 1$ 可以算出 $P_0 = 1 - \rho$，$P_n = \rho^n(1-\rho)$

队长：$L = \Sigma_{n=0}^{\infty} nP_n = \frac{\rho}{1-\rho}$

排队长：$L_q = \frac{\rho^2}{1-\rho}$

顾客平均停留时间：$W = \frac{1}{\mu - \lambda}$

顾客平均等待时间：$W_q = \frac{\lambda}{\mu(\mu - \lambda)}$

M/M/C/∞/∞/FCFS排队模型

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

系统的平均服务率：$\mu_n = \begin{cases} n\mu &0\leq n\leq C \ C\mu & C\leq n \end{cases}$

服务台的繁忙度：$\rho = \frac{\lambda}{C\mu}$

系统中没有顾客的概率：

$$P_0 = [\Sigma_{i-0}^{C-1} \dfrac{1}{i!}(\dfrac{\lambda}{\mu})^i + \dfrac{1}{1-\rho} \dfrac{1}{C!}(\dfrac{\lambda}{\mu})^C]^{-1}$$

排队长：$L_q =\dfrac{1}{C!} (\dfrac{\lambda}{\mu})^C\dfrac{\rho}{(1-\rho)^2} P_0$

顾客平均停留时间：$W = \dfrac{L}{\lambda}$