基本概念
排队系统的组成
- 输入过程：顾客按照怎样的规律到达
- 顾客的数量
- 单个到达还是批量到达
- 顾客到达间隔的分布（如泊松分布，负指数分布）
- 排队规则
- 损失制：到达后发现被占用，顾客离开（不允许排队）
- 等待制：排队等候
- 先到先服务（队列）
- 后到先服务（栈）
- 随机服务
- 按优先权服务
- 混合制：如当人数超过阈值，顾客不再排队
- 服务机构
- 服务台的数目
- 任意时刻的容量
- 每个顾客服务时间的分布
服务密度：$\rho = \dfrac{\lambda}{\mu}$，即到达数比服务数。越小效率越高。
符号描述
$n$：排队系统中顾客数目
$\lambda$：顾客到达的平均速率（到达顾客数/时间）
$\mu$：系统的平均服务速率（服务顾客数/时间）
$p_n(t)$：$t$ 时刻有 $n$ 个顾客的概率。
$C$：服务台个数
$\text{FCFS}$：FIFO
$\text{FCLS}$：FILO
PR:优先权服务的排队规则
$M$:负指数过程
$D$:定长型分布
$E_k$：k阶爱尔朗分布
a:顾客到达过程的概率分布(输入)
b:服务过程的概率分布(输出)
d:排队系统的最大容量
e:顾客总体的数量
f:排队规则
a/b/c/e 记号，如 $M/M/1/\infty$ 表示
- 顾客以泊松过程到达
- 服务时间服从指数分布
- 单服务台
- 顾客源无限
1971 标准：a/b/c/d/e/f
顾客到达的分布：泊松分布
p_{n}(t)=\frac{(\lambda t)^{n}}{n !} e^{-\lambda t}, t>0, n=0,1,2, \cdots
$$
表示长 $t$ 的时间区间到达 $n$ 个顾客的概率。期望和方差都是 $\lambda t$。
顾客到达的密集程度（间隔）：负指数分布
上面的泊松分布，当 $n=0$，即 $[0,t]$ 内 没有顾客到达的概率是 $p_0(t) = e^{-\lambda t}$。
则至少有一个顾客到达的概率是 $F_T(t) = 1 - e^{-\lambda t}$，期望是 $\dfrac{1}{\lambda}$，方差是 $\dfrac{1}{\lambda^2}$
服务时间的分布：负指数分布
设 $\mu$ 是单位时间内可以服务完的人数。则服务时间分布为 $f_v(t) = \mu e^{-\mu t}$。期望 $\dfrac{1}{\mu}$ 表示一个顾客的平均服务时间。
负指数分布具有无记忆性。所以研究过程不必考虑之前的情况，只需要研究当前的排队状况。
泊松过程的三个条件
- 无后效性：前面到达的顾客数，不影响后面到达的顾客数。
- 平稳性：顾客到达的多少只和时间间隔有关。
- 普通性：极短时间间隔到达多个顾客的概率极小。
单服务台模型（M/M/1）
-
输入过程: 顾客源是无限的,顾客单个到达,相互独立,到达数服从泊松分布,到达过程是平稳的;
-
排队规则: 单队,队长无限制,先到先服务;
-
服务机构: 单服务台,各顾客服务时间是相互独立的,服从相同的指数分布.
系统状态概率
$p_n$：系统中有 $n$ 个顾客的概率。
\left\{\begin{array}{ccc}
p_{0}=1-\rho \\
p_{n}=\rho^{n}(1-\rho) & p_{n}=\rho^{n} p_{0} \quad n\geq 1\\
\rho=\frac{\lambda}{\mu} & 0 \leq \rho<1 \end{array}\right. $$
排队系统的运行指标
$L$：排队顾客数期望。正在等候的和正在服务的之和。
$L_q$：排队中的顾客数期望。
$W$：进入系统时间的期望。包括排队时间和被服务时间之和。
$W_q$：顾客排队时间的期望。
系统运行指标的计算
$L$
L = \dfrac{\rho}{1-\rho} = \dfrac{\lambda}{\mu - \lambda}
$$
$L_q$
L_q = \dfrac{\rho^2}{1-\rho}
$$
$W$
顾客在系统中的时间 $T_s$ 是一个随机变量，服从参数为 $\mu - \lambda$ 的负指数分布。
\begin{array}{ll}
f(t)=(\mu-\lambda) e^{-(\mu-\lambda) t} & t \geq 0 \\
W=E\left(T_{S}\right)=\dfrac{1}{\mu-\lambda}
\end{array}
$$
$W_q$
W_{q}=W-\frac{1}{\mu}=\frac{1}{\mu-\lambda}-\frac{1}{\mu}=\frac{\rho}{\mu-\lambda}=\frac{\lambda}{\mu(\mu-\lambda)}
$$
系统内多于 $m$ 个顾客的概率
P\{N>1\}=1-p_{0}-p_{1}=1-(1-\rho)-\rho(1-\rho)=\rho^{2}\\
p\{N>m\} = \rho^{m+1}
$$
顾客停留时间大于 $t$ 的概率
P\{W>t\}=e^{-\mu(1-\rho) t}=e^{-(\mu-\lambda) t}
$$
顾客在系统中平均排队时间超过 t 的概率是
P\left\{W_{q}>t\right\}=\rho e^{-\mu(1-\rho) t}
$$
服务台忙期
当 $0<\rho<1$ 时，忙期随 $\rho$ 值得增加而增加，当 $\rho \rightarrow 1$ 时，系统趋于饱和状态，服务台忙碌的均值为
E(B)=\frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda}
$$
在一个忙期内完成服务的平均顾客数为
N_{B}=\frac{1}{\mu-\lambda} \cdot \mu=\frac{1}{1-\rho}(0<\rho<1) $$
Little 公式
设 $\lambda_{e}$ 为顾客到达系统中速率的平均值,则在很宽的条件下有：
$W=\dfrac{L}{\lambda_{e}}, W_{q}=\dfrac{L_{q}}{\lambda_{e}},$
在 $M / M / 1 / \infty / \infty / F C F S$ 系统中,顾客到达的速率是常数 $\lambda,$ 即 $\lambda_{e}=\lambda,$ 因此：
$W=\dfrac{L}{\lambda}, W_{q}=\dfrac{L_{q}}{\lambda},$ 称为利特尔公式.
例题
【例子】服务台全天服务，假设顾客到达的时间间隔服从均值为 1 的负指数分布。现在有一位顾客正好中午12:00 到达，试求:
(1）下一个顾客将在下午 1:00 前到达的概率;
(2）在下午 1:00 与 2:00 之间到达的概率:
(3）在下午 2:00 以后到达的概率。
【分析与解答】
（1）由已知，t 时间至少有一个顾客到达的概率是 $F_T(t) = 1 - e^{-t}$，当 $t = 1$ 时 $P = 1-e^{-1} = 0.6321$，所以概率是 $63.21\%$.
（2）在 2:00 内到达的概率是 $1-e^{-2} = 0.8646$，$0.8646 - 0.6321 = 0.2325$，即 $23.25\%$
（3）在 2:00 内到达的概率是 $0.8646$，则之后才到达的概率是 $1 - 0.8646 = 0.1354 = 13.54\%$.
【例子】小汽车过收费站，到达速率 100 $h^{-1}$，泊松流，检查一辆车 $15s$，为负指数分布，求稳态概率 $p_0, p_1, p_2$ 和系统的各项指标。