详谈排队论模型的始末

用户7506105

发布于 2021-08-09 15:45:54

1.3K0

发布于 2021-08-09 15:45:54

文章被收录于专栏：碎片学习录

一般而言，排队问题相当常见，比如等待银行柜台服务、加油站加油或者多个进程等待cpu处理都会出现排队，为叙述方便，将排队者称为顾客，提供服务的一方称为服务员。常识都知道我们不希望排队(为了享受排队的另说)，排队意味着是时间成本的消耗，如果是物资等待被处理的排队则说明物资出现积压，不管哪种都会对生产效率产生重要负面影响，但往往这个排队现象是无法完全消失的，这是一种随即现象，排队与很多因素相关，其中最重要的两部分是顾客到达时间间隔的随机时间和服务过程的服务随机时间两部分，而排队论的宗旨也是系统在不同场景下利用以上两种过程规律对实际的排队系统做出最优的决策以提高效益。

一般来说排队论是基于概率随机过程的理论建立起来的理论，最后才是系统的优化。

准备

排队系统

一般包含顾客输入、排队规则、服务过程三部分。顾客的输入过程指的是顾客到来的时间规律性。

顾客可以是无限的，也不一定是一个一个按照时间间隔到达，且顾客间相互独立，互不影响

排队规则主要是顾客会按照什么样的规则排队，分为损失制，等待制和前两者的混合，损失制顾名思义是顾客到达时没有服务员了就立马离去，而等待制则是说明顾客愿意等待直到接受完服务后才离去。

服务过程可以简单理解为柜台分配规则和对顾客的处理规则，有时是单个服务台，有时有多个服务台并行出现，当然也有多个服务台串联(即顾客需要按顺序走完流程)；而处理规则包括先到先服务(FIFO，最常见)，后到先服务(比如砌墙用的砖头，先拿来用的一定是最后放上去的)，随机服务，优先服务(比如重大患者优先)

符号约定

模型一般用六个符号表示，符号间用斜线隔开

X/Y/Z/A/B/C

其中X代表顾客流到达时间间隔的概率分布，Y表示服务员服务时间的概率分布(常见概率分布见后)，Z表示服务台个数，A表示系统容量限制，B表示顾客数目限制，C表示服务规则

表示顾客到达间隔时间和服务时间的分布的约定符号为：M为指数分布，D为确定型分布(即不依靠概率)，

E_k

为k阶爱尔朗分布，G为一般服务时间的分布，GI为一般相互独立的时间间隔的分布

常用概率分布和过程

排队系统指标

常见的排队模型

M/M/S排队模型

该模型所在的系统满足:

(1) 顾客到达服从泊松分布

(2) 服务时间服从指数分布

(3) 并列的服务台数为S个，系统容量、顾客数限制为无穷，排队规则为先来先服务

S=1时为单服务台等待模型，S>1时为并列多服务台排队模型

小trick：一般来说采用一个M/M/2排队模型要比两个M/M/1排队模型的效果更好(即排队效益最好，等待时间少，等待队长短)，这在经济学上是规模效益的说法

M/M/S/k排队模型

当k=S时为损失制系统，毫无疑问此时的容量为S个顾客，且等于服务台数，系统就已经达到系统限制了，若是新增顾客则一定这个顾客(无服务台服务他也不会让他排队)会损失，即为损失制系统，当k>S则为混合制排队系统

此时

P_j = \begin{cases} \frac{(S\rho)^j}{j!} P_0, 1<=j<=S \\ \frac{S^S \rho^j}{S!} P_0, j= S+1,S+2,...,k \end{cases}

此时ρ一定小于1，因为一定不会无限排队

此时

L_s = \sum_{j=0}^{k} jp_j , L_q = \sum_{j=0}^{k-S} jp_{S+j}

由于此时有损失顾客的行为，所以李特尔系数

\lambda

由损失概率决定，即

\lambda = \lambda_0 (1-P_k)

所以此时

W_s = \frac{1}{\lambda} L_s , W_q = \frac{1}{\lambda} L_q

M/M/S/m/m模型

即此时顾客源为有限的m个，即如果系统有m个客户就不会再有新的顾客到达

此时生灭过程的系数为

\lambda_j = (m - j) \lambda ,j=0,1,2,...,m-1

\mu_j = \begin{cases} j \mu, j = 1,2,3...,S \\ S\mu,j = S+1,S+2,...m \end{cases}

此时稳态概率为

p_j = \begin{cases} C_j^m (\frac{\lambda}{\mu})^j p_0 j=1,2,...,S\\ C_j^m \frac{j!}{S!S^{j-S}}(\frac{\lambda}{\mu})^jp_0,j=S+1,S+2,..,m \end{cases}

李特尔系数为

(m-L)\lambda

M/G/1排队模型

前三个的服务时间都是服从指数分布的排列系统，本系统模型是不作限制，服从任何一个分布(不一定要能写出分布函数表达式)，且期望为

E(\tau_n)

方差为

D(\tau_n)

则根据之前推导，有

p_0 = 1 - \rho = 1 - \frac{\lambda}{\mu}

此时的

\mu

为服务时间期望的倒数

则

L_s = \rho + \frac{\rho^2 + \lambda^2 D(\tau_n)}{2(1-\rho)}

L_q = \frac{\rho^2 + \lambda^2 D(\tau_n)}{2(1-\rho)}

李特尔系数为

\lambda

排队系统的优化

一般分为系统设计的优化和系统控制的优化

系统设计的优化为静态优化，即为在系统设置以前根据一定的质量指标，找出控制参数的最优值，比如λ、μ等
系统控制的优化为动态优化，对已有的排队系统寻求使其某一目标函数达到最优的运行机制(需要根据具体的业务场景定，每个场景确定的目标函数不尽相同，且计算复杂)

以下都为静态优化的策略

M/M/1排队模型的μ此时取定目标函数为单位时间服务成本率与顾客在系统逗留的费用总和，即

z = c_s \mu + c_wL_s

= c_s \mu + c_w \frac{\lambda}{\mu - \lambda}

其中

c_s

为服务一个顾客时单位时间内的服务费用,

c_w

为每个顾客在系统中逗留单位时间的费用，显然需要让z最小，所以根据z对

\mu

求导得

\frac{dz}{du} = c_s - c_w \frac{lambda}{(\mu - \lambda)^2} = 0

解得最优的

\mu^*

为

\mu^* = \lambda + \sqrt{\frac{c_w}{c_s} \lambda}

M/M/1/k模型的利润最大化

这里系统只有一个服务台，且有损失概率

p_k

此时系统的平均顾客数为

\lambda = \lambda_0 (1-p_k)

,且设服务一个客户的收入为G元，则利润z为

z = \lambda_0 (1-p_k)G - c_s \mu = \lambda G \frac{1-\rho^k}{1-\rho_{k+1}} - c_s \mu

= \lambda \mu G \frac{\mu^k - \lambda^k}{\mu^{k+1} - \lambda^{k+1}} - c_s \mu

令

\frac{dz}{d\mu} = 0

即可

M/M/S 模型中的最优服务台数S 显然系统稳定时的总费用为

z = c'_s S + s_w L_s

其中

c'_s

为每个服务台单位时间内的费用，z里面唯一可变的就是服务台个数S，且S只能是整数，采用整数优化方式的边际分析，即

z(S^*) <= z(S^* - 1)

z(S^*) <= z(S^* + 1)

则

L_s(S^*) - L_s(S^* +1) <= \frac{c'_s}{c_w} <= L_s(S^* - 1) - L_s(S^*)

不断带入s=1,2,3,...(s从小到大轮询)因为上述不等式中间的比例式已知，则只需计算两个相邻的L的差值并判断落在哪个不等式即可，

这个方法在整数规划中非常常用！！！

小技巧

当排队系统的到达间隔时间和服务时间的概率分布很复杂时，或不能用公式给出时，那么就不能用解析法求解，这就需用随机模拟法求解，其实核心要义就是如何生成F(X)为指定分布的随机变量X

1、反变换法

必须要求F(X)严格递增(这样才有反函数)

X = F^{-1}(U)

其中U为已知的分布

2、卷积法若

X = Y_1 + Y_2 + ... + Y_n

因为X很难直接求出，而

Y_i

相对容易，所以就是对他们做求和的卷积操作(概率论里面求Z = X+Y的分布函数的求法)

个人总结

这一篇是我酝酿较久的一个知识点，删稿次数太多，，惭愧

排队论是随机服务系统的理论，对研究排队的稳态和瞬态有比较严格的要求，它的最关键的步骤是求生灭过程的稳态概率推导式，而这个推导式在很大程度上是基于数学归纳法得出的结论，造成了这个理论具有非常通用有规律的特点，所以列出的几种模型也只是一些条件发生变化时的迭代性针对性修改，其次是它定义了较多的变量，很容易搞混，但其实仔细理解是想得通为什么这么定义的，写完本文说实话对我之前对它的一些固有了解层面做了很大的改变，因为它可能是我之前一直没搞懂的，惭愧惭愧。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-07-04，如有侵权请联系 cloudcommunity@tencent.com 删除

cpu

fifo

本文分享自碎片学习录微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

cpu

fifo

登录后参与评论

0 条评论

热度