排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。排队论又叫随机服务系统理论或公用事业管理中的数学方法，它是研究各种各样的排队现象的。它所要解决的主要问题是：在排队现象中设法寻求能够达到服务标准的最少设备，使得在满足服务对象条件下，服务机构的花费最为经济，使服务系统效率最高。
一、随机服务系统实例
现实生活中存在大量有形和无形的排队或拥挤现象，如旅客购票排队，市内电话占线等现象，上述问题都可以抽象为排队系统进行分析。排队系统是由服务机构和服务对象（顾客）构成。顾客到来的时刻和服务时间（即占用服务系统的时间）都是随机的。上图为一最简单的排队系统模型。排队系统包括三个组成部分：输入过程、排队规则和服务机构。
| 到达顾客 | 服务内容 | 服务机构 |
|---|---|---|
| 病人 | 诊断/手术 | 医生/手术台 |
| 进港的货船 | 装货/卸货 | 码头泊位 |
| 到港的飞机 | 降落 | 机场跑道 |
| 电话拨号 | 通话 | 交换台 |
| 故障机器 | 修理 | 修理技工 |
| 修理技工 | 领取修配零件 | 仓库管理员 |
| 上游河水 | 入库 | 水闸管理员 |
智能仓库中配置多个搬运机器人，中心控制系统接收到订单后，经过分析拆解为相应的拣选任务，然后根据任务优先级，通过一定的分配算法，将任务分配给当前处于空闲状态的搬运机器人。这里，我们将订单看作顾客，搬运机器人看作服务台，不考虑系统对订单的处理及任务分配过程。那么，整个系统可以抽象为一个多服务台排队系统（M/M/C）。
二、排队系统运行指标
2.1 服务时间是负指数分布的排队系统
| 顾客有效到达率 | 系统空闲的概率\(P_0\) | 系统\(n\)个顾客概率\(P_n\) | 负荷强度 | 队长\(L_s\) | 队列长\(L_q\) | 逗留时间 \(W_s\) | 等待时间\(W_q\) | |
|---|---|---|---|---|---|---|---|---|
| M/M/1/∞/∞（标准模型） | \(\lambda\) | \(P_0=1-\rho\) | \(P_{n=} \rho^n P_0=(1-\rho) \rho^n\) | \(\rho\) | \(L_S=\frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda}\) | \(L_q=L_{s^{-}} \rho=\frac{\rho^2}{1-\rho}\) | \(W_s=\frac{L_s}{\lambda}\) | \(W_q=W_s-\frac{1}{\mu}\) |
| M/M/1/N/∞ （系统容量有限） | \(\lambda_e=\lambda\left(1-P_N\right)\) | \(P_0=\frac{1-\rho}{1-\rho^{N+1}}\) | \(P_{n=} \rho^n P_0\) | \(\frac{\lambda_e}{\mu}\) | \(L_S=\frac{\rho}{1-\rho}-\frac{(N+1) \rho^{N+1}}{1-\rho^{N+1}}\) | \(L_q=L_S-(1-P_0)\) | $ W_s =\frac{L_s}{\lambda_e} $ | $W_q =\frac{L_q}{\lambda_e} $ |
| M/M/1/∞/m（顾客源有限） | \(\lambda_e=\lambda\left(m-L_s\right)\) | \(P_0=\frac{1}{\sum_{i=0}^{m} \frac{m!}{(m-i)!} \quad \rho^i}\) | \(P_n=\frac{m!}{(m-n) !} \rho^n P_0\) | \(\frac{\lambda_e}{\mu}\) | \(L_S=m-\frac{\mu}{\lambda}(1-P_0)\) | \(L_q=L_s-(1-P_0)\) | \(W_s=\frac{L_s}{\lambda_e}\) | $W_q=\frac{L_q}{\lambda_e} $ |
| M/M/C/∞/∞（多服务台） | \(\lambda\) | \(P_0=\frac{1}{\sum_{k=0}^{c-1} \frac{1}{k!}(\frac{\lambda}{\mu})^k+\frac{1}{C!} \frac{1}{1-\rho} (\frac{\lambda}{\mu})^c}\) | \(\frac{\lambda}{c\mu}\) （！该系统公式中\(\rho\)） | \(L_S=L_q+\frac{\lambda}{\mu}\) | $ L_q=\frac{(C \rho)^C \rho}{C!(1-\rho)^2} \quad P_0 $ | $ W_s=\frac{L_s}{\lambda} $ | $ W_q=\frac{L_q}{\lambda} $ | |
| M/M/C/N/∞ | \(\lambda_e=\lambda\left(1-P_N\right)\) | \(P_0=\left\{\begin{array}{l}{\left[\sum_{k=0}^{c} \frac{1}{k !}\left(c \rho^k\right)+\frac{c^c}{c !} \frac{\rho\left(\rho^c-\rho^N\right)}{1-\rho}\right]^{-1}, \rho \neq 1} \\ \sum_{k=0}^{c} \frac{1}{k !}\left(c^k\right)+\frac{c^c}{c !}(N-c+1), \rho=1\end{array}\right.\) | \(\frac{\lambda_e}{c\mu}\) | \(L_s=L_q+c\rho(1-P_N)\) | $L_{q}=\frac{(c \rho)^{c} \rho}{c !(1-\rho) 2} P_{0}\left[1-\rho^{N-c}-（N-c）(1-\rho) \rho^{N-c}\right] $ | \(Ws=\frac{L_s}{\lambda_e}\) | $ W_q=\frac{L_q}{\lambda_e} $ | |
| 顾客到达率 | \(\lambda\) | 顾客服务率 | \(\mu\) |
2.2 服务时间其他分布的排队系统
| M/G/1/∞/∞ | M/D/1/N/∞ | M/\(E_k\)/1/∞/m) | |
|---|---|---|---|
| 系统 (每小时) 顾客平均数 | \(L_s=\rho+\frac{\rho^2+\lambda^2D(v))}{2(1-\rho)}\) | \(L_s=\rho+\frac{\rho^2}{2(1-\rho))}\) | \(L_s=\rho+\frac{(k+1)\rho^2}{2k(1-\rho)}\) |
| (每小时) 等待服务的平均顾客数 | \(L_q=\lambda W_q=L_s-\rho\) | \(L_q=L_s-\rho=\frac{\rho^2}{2(1-\rho)}\) | $ L_q = L_s \rho = \frac{(k+1) \rho ^2}{2k(1-\rho)}$ |
| (每位) 顾客在店内的平均逗留时间 | \(W_s=\frac{L_s}{\lambda}\) | \(W_s=\frac{L_s}{\lambda}\) | \(W_s=\frac{L_s}{\lambda}\) |
| （每位）顾客平均修理时间 | \(W_q=W_s-E(v)\) | \(W_q=\frac{L_q}{\lambda}\) | \(W_(q)=\frac{L_q}{\lambda}\) |
| \(\lambda\):每小时到达店内人数 | \(\lambda\):每小时到达店内人数 | ||
| \(\mu\):每小时可以服务的人数 | \(\mu\):每小时可以服务的人数 | ||
| \(E(v)\): 服务时间 \(v\) 的期望 | \(E(v)=\frac{1}{\mu}\) | ||
| \(D(v)\): 方差 | \(D(v)=\frac{1}{k\mu^2}\) | ||
| \(\rho\):系统忙着的概率 \(\rho=\lambda E(v)<1\) | \(\rho=\frac{\lambda}{\mu}\):系统忙着的概率 |
三、R语言计算
案例1：您在一家银行工作，您需要与呼叫中心联系并告诉他们您需要的服务器数量。您正在为客户的特定功能查询设置此呼叫中心，客户在一小时内有大约20个查询，每个查询大约需要15分钟才能解决。试找出所需的服务器数量，使得平均等待时间缩短至不到1分钟。
给定问题可参考多服务台M/M/C等待时间的计算。
3.1 R计算程序
options(digits=4)
rm(list = ls())
a =data.frame() #系统M/M/C运行指标计算结果
Lambda = 20
Mue = 4 #基于到达率和服务率可以预估服务器数量大约为6-20
Rho <- Lambda / Mue
for (c in 6:20){
P0inv=0
for (i in 0:(c-1)) {P0inv = P0inv+(Rho^i)/factorial(i)}
P0inv <- P0inv+ (Rho^c / (factorial(c)*(1-Rho/c)))
P0 = 1 / P0inv
Lq= P0*(Rho^c)*(Rho/c)/(factorial(c)*(1-(Rho/c))^2)
Wq =60* Lq / Lambda
Ls <- Lq + Rho
Ws <- 60*Ls/Lambda
a <- rbind(a,cbind(P0,Ls,Lq,Ws,Wq))
}
3.2 R计算结果
P0 Ls Lq Ws Wq
[1,] 0.004512 7.938 2.938e+00 23.81 8.813e+00
[2,] 0.005975 5.810 8.104e-01 17.43 2.431e+00
[3,] 0.006474 5.279 2.788e-01 15.84 8.363e-01
[4,] 0.006648 5.101 1.006e-01 15.30 3.019e-01
[5,] 0.006708 5.036 3.611e-02 15.11 1.083e-01
[6,] 0.006728 5.013 1.257e-02 15.04 3.772e-02
[7,] 0.006735 5.004 4.203e-03 15.01 1.261e-02
[8,] 0.006737 5.001 1.341e-03 15.00 4.024e-03
[9,] 0.006738 5.000 4.077e-04 15.00 1.223e-03
[10,] 0.006738 5.000 1.179e-04 15.00 3.538e-04
[11,] 0.006738 5.000 3.249e-05 15.00 9.747e-05
[12,] 0.006738 5.000 8.531e-06 15.00 2.559e-05
[13,] 0.006738 5.000 2.138e-06 15.00 6.414e-06
[14,] 0.006738 5.000 5.121e-07 15.00 1.536e-06
[15,] 0.006738 5.000 1.174e-07 15.00 3.522e-07
从上面结果可知，设置呼叫中心服务台数量为8，其等待时间为Wq=2.431e+00分钟；设置服务台数量为9，其等待时间Wq=8.363e-01分钟，满足问题要求。
3.3 案例应用
案例2：您是银行分行的运营官，您的分支机构最多可容纳50名客户。如果客户以100客户/小时的速度进入并且出纳员在3分钟内解决查询，为确保客户等待时间少于30秒，需要多少柜员？
系统模型M/M/C/N/∞ ，其中\(\lambda=100\)，\(\mu=20\)，\(N=50\).
总结
排队现象作为一种随机现象，所采用的主要工具是研究随机现象规律的概率论。它把所需研究的问题 形象地描述成顾客（如电话用户、发生故障的机床等）来到服务台前（如电话线路维修工人 等)要求接待，如果“服务台”已被其他顾客占用，那么就得排队等待;另一方面服务台”也 时而清闲，时而忙碌。排队论就是人们通过数学方法求出顾客等待时间、排队长度等的概率分布，以便作出决策。目前排队论在社会生活的各方面已有广泛而深入的应用，如在水库用水量的调度、存储 问题、生产流水线的安排、电力网的设计、铁路分车场的调度等方面都可运用排队论的基本理论来进行计算，从而获得合理的解决方案。
参考文献
单服务台排队模型R实现
怎么利用Python进行数学建模与分析？
【数学建模算法】(19)排队论：多服务台模型（M/M/s/∞)
R语言中如何使用排队论预测等待时间？
