排队论

排队论也叫做随机服务系统理论，主要用于解决生活中排队问题(排队中的阻塞疏导等问题)而发展的学科。主要研究下面三个部分

性态问题：队长分布，等待时间分布，忙期分布。包括瞬态和稳态两种情形。
最优化问题：最优设计或排队系统的最优运营
排队系统的统计推断：判断排队系统符合哪一种模型。

基本概念

服务的对象统称顾客,为顾客服务的人或者物统称为服务台

排队系统的组成

一般的排队过程都由输入过程、排队规则、服务过程三部分组成

输入过程

顾客可能是有限的，也可能是无限的
顾客可能一个一个到达，也可能成批到达
顾客到达可以是独立的，也可能是相关的
输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等
数字特征都与时间无关

排队规则

损失制: 顾客到达时所有服务台都被占用，顾客随即离去
等待制：顾客到达时所有服务台都被占用，顾客排队等待，直到接受完服务再离去
混合制：在上一种的前提上增加排队限度，超过限度就离去

服务机构

单服务台；多服务台并联(同时为不同顾客服务)；多服务台串联(依次为同一顾客服务)；混合型

服务规则

先到先服务
后到先服务
随机服务
优先服务

符号表示

排队模型用六个符号表示，在符号之间用斜线隔开，即$X/Y/Z/A/B/C$

$X$ 表示顾客到达流或者是顾客到达间隔时间的分布
$Y$ 表示服务时间的分布
$Z$ 表示服务台数
$A$ 表示系统容量限制
$B$ 表示顾客源输密
$C$ 表示访问规则，比如FCFS(先到先服务) LCFS(后到先服务)等

表示顾客到达间隔时间和服务时间的分布的记号为

$M$ —— 指数分布
$D$ —— 确定性分布 https://zh.wikipedia.org/wiki/%E9%80%80%E5%8C%96%E5%88%86%E5%B8%83
$E_{k}$ —— $k$阶爱尔朗分布，当爱尔朗分布的阶数k=1时，退化为指数分布
$G$ — 一般（general）服务时间的分布；
$GI$ — 一般相互独立（General Independent）的时间间隔的分布

排队系统的运行指标

平均队长：系统内的顾客数(包括被服务的和等待的)，记作$L_{s}$
平均排队长：等待服务顾客的数学期望，记作$L_{q}$
平均逗留时间：顾客在系统内的逗留时间(包括排队和等待)，记作$W_{s}$
平均等待时间：在排队系统中排队等待时间的数学期望，记作$W_{q}$
平均忙期：指顾客到达空闲服务机构起，到服务机构再次空闲的长度的数学期望，记为$T_{b}$

还有顾客被拒绝造成的损失率和后面的服务强度

计算指标的基础是系统的状态，所谓系统的状态即指系统中顾客数。

如果系统中有n 个顾客就说系统的状态是n ，它的可能值是

队长没有限制时，$n = 0,1,2,\cdots,$
队长有限制，最大数为$N$ 时，$n = 0,1,\cdots,N$ ，
损失制，服务台个数是$c$时，$n = 0,1,\cdots,c$。

这些状态的概率一般是随时刻$t$ 而变化，所以在时刻$t$ 、系统状态为$n$的概率用$P_{n}(t)$表示。

稳态时系统状态为$n$ 的概率用$P_{n}$ 表示。

输入过程和服务时间的分布

泊松流和指数分布

设$N(t)$为时间区间$[0,t)$内到达的顾客数， $P_{n}(t_{1},t_{2})$ 表示在时间区间 $[t_{1},t_{2})$ 内有$n$个顾客到达的概率，即

$P_{n}(t_{1},t_{2}) = P\{N(t_{2} - N(t_{1}) = n\} \qquad (t_{2}>t_{1},n\ge0)$

当 $P_{n}(t_{1},t_{2})$ 满足三个条件时，顾客到达形成泊松流

在不相重叠的时间区间内顾客到达数是相互独立的，我们称这性质为无后效性。
对于充分小的$\Delta t$，在时间区间$[t,t+\Delta t)$内有一个顾客到达的概率与$t$无关，但与$\Delta t$成正比，即
$P_{1}(t,t+\Delta t) = \lambda \Delta t + o(\Delta t)$
$\lambda > 0$是常数，表示单位时间有一个顾客到达的概率

当$\Delta t \to 0$时，$o(\Delta t)$是关于$\Delta t$的高阶无穷小
对于充分小的$\Delta t$，在时间区间$[t,t+\Delta t)$内有两个或两个以上顾客到达的概率极小，以至于可以忽略

简记 $P_{n}(0,t)=P_{n}(t)$ ，取初值 $P_{0}(0)=1,P_{n}(0)=0 \quad(n=1,2,\cdots)$ ，可以解得

$P_{n}(t) = \frac{(\lambda t)^{n}}{n!} e^{- \lambda t}, \quad n = 1,2,\cdots$

当输入过程是泊松流时，顾客相继到达的时间间隔$T$服从指数分布

$P\{ T \le t\} = F(t) = \left\{ \matrix{ 1 - {e^{ - \lambda t}},\quad t \ge 0 \hfill \cr 0,\qquad \quad t < 0 \hfill \cr} \right.$

分布密度函数为

$f(t) = \lambda e^{-\lambda t},\; t>0$

对一顾客的服务时间也就是在忙期相继离开系统的两顾客的间隔时间，有时也服从指数分布

在任何小的时间间隔$[t,t+\Delta t)$内一个顾客被服务完了（离去）的概率是$\mu \Delta t+ o(\Delta t)$。$\mu$表示单位时间能被服务完成的顾客数，称为平均服务率.

单服务台模型

单服务台等待制模型$M/M/1/\infty$是指：顾客的相继到达时间服从参数为λ 的负指
数分布，服务台个数为1，服务时间V 服从参数为μ 的负指数分布，系统空间无限，
允许无限排队，这是一类最简单的排队系统。

队长的分布

直接给结论吧。。。反正这个东西的推导什么的资料很多

服务强度

记$\rho = \frac{\lambda}{\mu}$

$p_{n} = (1-\rho)\rho^{n}\qquad n = 1,2,\dots$

其中$\rho$是系统中至少有一个顾客的概率，也就是服务台处于忙状态的概率，也称$\rho$为服务强度，反映系统繁忙程度

平均队长

$L_{s} = \frac{\rho}{1-\rho} = \frac{\lambda}{\mu - \lambda}$

平均排队长

$L_{q} = L- \rho = \frac{\lambda^{2}}{\mu(\mu - \lambda)}$

顾客在系统中的逗留超过某个时间t的概率

$P\{ T >t\} = e ^{\mu - \lambda}t \qquad t \ge 0$

平均逗留时间

$W_{s} = \frac{1}{\mu - \lambda}$

平均等待时间

$W_{q} = W_{s} - \frac{1}{\mu} = \frac{\lambda}{\mu(\mu - \lambda)}$

平均忙期

$\overline{B} = \frac{1}{\mu - \lambda}$