数模日记3
排队论模型
PS：此处的排队论，真的就是单纯的排队。
排队论研究随机服务系统的确定性规律。
等待时间、服务时间、到达时间具有随机性。
[TOC]
基本组成
输入
- 顾客总体的数量：有限/无限
- 顾客到来的方式：个体/批
- 到达的间隔时间：不确定（随机变量，遵从概率分布）
顾客的行为假定为：
- 在未服务之前不会离开（等待制）
- 当看到队列很长的时候离开（有损失）
- 从一个队列移到另一个队列（上两种结合）
排队规则
队列容量：有限/无限
—– 此处的队列是排队队列。
排队规则：FCFS、LCFS、RSS（random）、PS（priority）、GD（一般规则）
服务规则
- 服务机构（1 / 多）个
- 服务台：并行、串行、混合排列
- 服务方式：单个/批处理
数量指标
每天的排队人数是随机的，所以取长期的平均值。
$L_s$：(line system)平均队长。既在排队、又在接受服务的人。
$L_q$：(line query)平均队列长。只包括排队的人，不包括正在接受服务的人。
$W_s$：(wait system)平均逗留时间。顾客在这个系统中（排队+服务）停留的时间平均值。
$W_q$：(wait query)平均等待时间。顾客在排队的时间的平均值。
为求解以上4个指标，引入：
记号方案
Kendall 记号
X：顾客到达的时间分布，输入过程的特征。Y：服务时间分布。Z：服务台的个数。取值 1/c（$c \gt 1$，表示多个服务台）A：排队系统允许的最大顾客容量。取值有限/无限。B：顾客总体数量，指不在排队的、外部的顾客数量。（多分 ）取值有限/无限。C：排队队则，如FCFS。
常见：$X/Y/Z/A/B/C = M/M/1/\infty/ \infty /FCFS$
X/Y：
- M：表示泊松过程 or 负指数分布
- D：表示确定型分布
- $E_k$：表示 k 阶埃尔朗分布（综合到一起的分布）
- G：表示一般服务时间分布
- GI：表示一般相互独立的时间间隔分布
排队论模型
单服务台模型(FCFS)
$M/M/1$（标准型）
$ M/M/1/\infty/ \infty /FCFS$
求解要建立稳态概率方程：
$$
\begin{cases}
\lambda P_0=\mu P_1 \
\lambda P_{n-1}+\mu P_{n+1}-(\lambda +\mu)P_n=0& ,n\ge 1 \
\end{cases}
$$
由递推公式得：
$$
P_n = (\frac{\lambda}{\mu})^n P_0
$$
令$\rho = \frac{\lambda}{\mu}$：
$$
\sum^{\infty}{n=0}P_n=1\
P_0\sum^{\infty}{n=0}P_n= \frac{P_0}{1-\rho}=1
$$
故：
$$
P_0=1-\rho\
P_n=(1-\rho)\rho^n
$$
这是系统状态为 $n$ 的概率，然后接下来计算上述的4个指标。
平均队长$L_s$：(serve+queue)
$$
L_s=\sum_{n=1}^\infty nP_n=\sum_{n=1}^\infty n (1-\rho)\rho^n = \frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda}
$$
平均队列长$L_q$：(queue)
$$
L_q=\sum_{n=1}^\infty(n-1)P_n=\frac{\rho\lambda}{\mu-\lambda}
$$
平均逗留时间$W_s$：(serve+queue)
$$
W_S=\frac 1{\mu-\lambda}=\frac{\rho}{\lambda(1-\rho)}
$$
平均等待时间$W_q$：(queue)
$$
W_q=W_s-\frac 1{\mu}=\frac{\rho}{\mu-\lambda}=\rho\times W_S
$$
$ M/M/1/N/ \infty$
其稳态概率方程：
$$
\left{
\begin{aligned}
\lambda P_1&=\mu P_1 \
\lambda P_{n-1}+\mu P_{n+1}&=(\lambda +\mu)P_n& ,1\le n\le N-1 \
\mu P_N&=\lambda P_{N-1}
\end{aligned}
\right.
$$
它的计算结果已知，自己去Google。
$ M/M/1/\infty/m$
顾客的总体数量是有限的，该模型等价于$M/M/1/m/m$
假设每个顾客到达率相同且为 $\lambda$，在系统外的平均顾客数为 $m-L_S$。
系统的有效到达率$\lambda _e=\lambda(m-L_s)$
(有效到达率与顾客总容量以及当前剩余的容量有关)
其稳态方程：
$$
\left{
\begin{aligned}
m\lambda_e P_1&=\mu P_1 \
(m-n+1)\lambda_e P_{n-1}+\mu P_{n+1}&=[(m-n)\lambda_e +\mu]P_n& ,1\le n\le m-1 \
\mu P_m&=\lambda_e P_{m-1}
\end{aligned}
\right.
$$
多服务台模型（FCFS）
$M/M/c$（标准型）
顾客流为泊松流，平均到达率为 $\lambda$，各个服务台的平均服务率是 $\mu$，则：
整个服务机构的平均服务率是：$n\mu\ (n \lt c)$ or $c\mu\ (n\ge c)$，令$\rho = \frac{\lambda}{c\mu}$(系统服务强度)
当 $\rho >1$ 时，会出现排队现象。
稳态方程如下。
$$
\begin{cases}
\lambda P_0=\mu P_1 \
\lambda P_{n-1}+(n-1)\mu P_{n+1}=(\lambda +n\mu)P_n& ,1\le n\le c \
c\mu P_{n+1}+\lambda P_{n-1}=(\lambda+c\mu)P_n&,n\gt c
\end{cases}
$$
$M/M/c/N/\infty$（系统容量有限型）
$M/M/c/\infty/m$（顾客源有限型）
略，Google。