当前位置：首页 > 编程资源 > 编程问答 >内容正文

编程问答

排队论模型

发布时间：2023/12/14 编程问答 29 豆豆

生活随笔收集整理的这篇文章主要介绍了排队论模型小编觉得挺不错的,现在分享给大家,帮大家做个参考.

排队论模型

现实中的问题

生活生产中有很多排队的场景

商店、超市等收款处排队付款
车站、民航等售票处依次购买车船票
各种生产系统、存储系统、运输系统等一系列等待现象比比皆是

合理安排排队，提高服务效率是一个值得研究的问题

排队论的基本组成

排队系统

现实中排队的情况有很多种

一起排队——分开服务——离开

分开排队——分开服务——离开

一起排队——服务——排队——再服务——离开

分开排队——分开服务——一起服务——分开服务——一起服务——离开

总结：

中间的服务系统是随机的，因此可以把它看成是一个随机系统

整个排队流程可以看成

输入——随机服务系统——输出

输入

顾客总体（顾客源）数量可分为：有限/无限
顾客到来方式可能是一个一个也可能是成批
顾客到达间隔时间：到下一个顾客到达的时间一般是服从某一概率分布（例如：指数分布）
顾客的行为假定为：在未服务之前不会离开；当看到队列很长的时候离开；从一个队列移到另一个队列。

排队规则

队列容量可分为有限/无限

排队规则

先来先服务（FCFS）；
后来先服务（LCFS）；
随机服务（RSS）；
有优先权的服务（PS）；
排队模型中也用到服务中的 “一般规则（GD）” 它包括前三种排队规则。

服务规则

服务机构可以有一个，也可以有多个；
对于多个服务台可以是并列、串列、混合排列；
服务方式可以是一个或成批；

排队模型的评价数量指标

平均队长：排队系统中顾客数的平均值， $L_s$ ，Line system

平均队列长：排队系统中等待服务的顾客数平均值， $L_q$ ，Line query

平均逗留时间：一个顾客在系统中停留的时间平均值， $W_s$ ，Wait System

平均等待时间：一个顾客在系统中排队等待的时间平均值, $W_q$ , Wait query

如何求数量指标

需要提前知道的数据

P_n(t)- 时刻t系统中顾客数为n的概率，若 $lim⁡t→∞Pn(t)=Pn−\lim _{t \rightarrow \infty} P_{n}(t)=P_{n}-$ 称为稳态解(统计平衡状态解)，此时系统稳定

$λ−\lambda-$ 平均到达率单位时间内到达顾客的平均数，常用分作为时间单位

$μ−\mu-$ 平均服务率，单位时间内被服务顾客的平均数

$ρ=λ/μ−\rho=\lambda/\mu-$ 服务强度：单位时间内的服务强度

其他数量指标(了解)

记号方案

X,Y的表示

X表示相继到达时间间隔的分布，Y表示服务时间的分布，

X，Y取值有以下几种情况：

M一表示泊松过程或负指数分布；
D-表示确定型分布；
$E_k-$ 表示k阶爱尔朗分布，
G-表示一般服务时间分布；
GI-表示一般相互独立的时间间隔分布

其他记号的表示方式

Z一表示服务台（员）个数-“1”则表示单个服务台，“c”（c>1）表示多个服务台。

A一表示系统中容量限额，或称等待空间容量,有限为N，无限为\infty

B一表示顾客源数目，分有限与无限两种， $∞\infty$ 一顾客源无限，此时一般 $∞\infty$ 也可省略不写。

C一表示服务规则，常用下列符号：

FCFS：表示先到先服务的排队规则（省略时代表的是FCFS（先到先服务））

LCFS 表示后到先服务的排队规则；

PR.表示优先权服务的排队规则

随机服务

排队论模型

模型有很多种，只学最标准的，然后递推

单服务台模型分为3种

设系统输入过程服从泊松流，服务时间服从负指数分布，单服务台：（1）标准型：M/M/1/ $∞\infty$ / $∞\infty$ /FCFS （M/M/1）（2）系统容量有限型：M/M/1/N/ $∞\infty$ （3）顾客源有限型：M/M/1/ $∞\infty$ /m

1.标准型：M/M/1型

此图叫状态转移图

稳态概率方程

根据0和n两个状态的流入/流出量建立稳态概率方程

流量=流速*面积

流速= $λ\lambda$ 或 $μ\mu$

面积=稳定状态 $P_n$

此图叫状态转移图

求评价指标

解此方程可得

$P1=λμ∗P0P_1=\frac{\lambda}{\mu}*P_0$

$P2=(λμ)2∗P0P_2=(\frac{\lambda}{\mu})^2*P_0$

······由递推关系

$Pn=(λμ)n∗P0令λμ=ρP_n=(\frac{\lambda}{\mu})^n*P_0 令\frac{\lambda}{\mu}=\rho$ ，即平均到达率与平均服务率之比

由概率性质： $P0∑ρn∞n=0=P01−ρ=1P_0\underset{n=0}{\overset{\infty}{\sum{\rho ^n}}}=\frac{P_0}{1-\rho}=1$

所以

$P0=1−ρP_0=1-\rho$ ，没有人来的概率

$Pn=(1−ρ)ρn,n>1P_n=(1-\rho)\rho^n,n>1$ , 来n个人的概率

这就是系统状态为n的概率

代入 $P_n$ 可得

平均队长（包含正在被服务的那个顾客）

$KaTeX parse error: {equation} can be used only in display mode.$

平均队列长（等待的平均顾客数）

$KaTeX parse error: {equation} can be used only in display mode.$

平均逗留时间（即顾客在系统中的时间期望）

$KaTeX parse error: {equation} can be used only in display mode.$

平均等待时间（即顾客等待时间的期望）

$Wq=Ws−1μ=ρμ−λ=λμ(μ−λ)W_{q}=W_{s}-\frac{1}{\mu}=\frac{\rho}{\mu-\lambda}=\frac{\lambda}{\mu(\mu-\lambda)}$

对应的lingo程序

model: lambda=4; mu=6;rho=lambda/mu; L_s=lambda/(mu-lambda); L_q=L_s-rho; W_s=L_s/lambda; W_q=L_q/lambda; end

评价指标间的关系

$Ls=λWsLq=λWq,Ls=Lq+λμWs=Wq+1μ\begin{aligned} &L_{s}=\lambda W_{s} \quad L_{q}=\lambda W_{q}, \\ &L_{s}=L_{q}+\frac{\lambda}{\mu} \\ &W_{s}=W_{q}+\frac{1}{\mu} \end{aligned}$

这些关系式称为Little公式.

只要求到两个指标，其他指标也可以求到

例题

此时Z=2需要用别的公式

2.系统容量有限制：M/M/1/N/ $∞\infty$ 型

服务人数的数量有限制，增加到一定数量后就不会增了

利用0，n，N，三点的流量关系（流入-流出）建立建立稳态概率方程

稳态概率方程

${μP1=λP0μPn+1+λPn−1=(λ+μ)Pn(1≤n≤N−1)μPN=λPN−1\left\{\begin{array}{l} \mu P_{1}=\lambda P_{0} \\ \mu P_{n+1}+\lambda P_{n-1}=(\lambda+\mu) P_{n}(1 \leq n \leq N-1) \\ \mu P_{N}=\lambda P_{N-1} \end{array}\right.$

注意至 $∑n=0NPn=1\sum_{n=0}^{N} P_{n}=1$ 由递推关系得

系统状态概率

$KaTeX parse error: {equation} can be used only in display mode.$

评价指标

（1）队长:

$Ls=∑n=0NnPn=11−ρ−(N+1)ρN+11−ρN+1,ρ≠1L_{s}=\sum_{n=0}^{N} n P_{n}=\frac{1}{1-\rho}-\frac{(N+1) \rho^{N+1}}{1-\rho^{N+1}}, \rho \neq 1$

（2）队列长: $Lq=∑n=1N(n−1)Pn=Ls−(1−P0)L_{q}=\sum_{n=1}^{N}(n-1) P_{n}=L_{s}-\left(1-P_{0}\right)$ ;

有效到达率 $λe\lambda_{e}$

$λ\lambda$ 表示系统的容量有空时的平均到达率，当系统满员时则到达率为 0 , 因此有效到达率 $λe\lambda_{e}$ 表示有空时平均到达率 $λ\lambda$ 减去满员后拒绝顾客的平均数 $λPN\lambda P_{N}$ , 即 $KaTeX parse error: {equation} can be used only in display mode.$

有效服务强度 :

$λeμ=λ1−ρN1−ρN+1ρλ=ρ−ρN+11−ρN+1=1−P0\frac{\lambda_{e}}{\mu}=\lambda \frac{1-\rho^{N}}{1-\rho^{N+1}} \frac{\rho}{\lambda}=\frac{\rho-\rho^{N+1}}{1-\rho^{N+1}}=1-P_{0}$

(3) 平均逗留时间:

$Ws=Lsλe=Lsλ(1−P0)=Lqλ(1−PN)+1μW_{s}=\frac{L_{s}}{\lambda_{e}}=\frac{L_{s}}{\lambda\left(1-P_{0}\right)}=\frac{L_{q}}{\lambda\left(1-P_{N}\right)}+\frac{1}{\mu}$

(4) 平均等待时间:

$Wq=Lqλe=Lqλ(1−PN)=Ws−1μW_{q}=\frac{L_{q}}{\lambda_{e}}=\frac{L_{q}}{\lambda\left(1-P_{N}\right)}=W_{s}-\frac{1}{\mu}$

3.顾客源为有限型： $M/M/1/∞/mM/M/1/\infty/m$ 型

相当于M/M/1/m/m型

概率稳态方程

$KaTeX parse error: {equation} can be used only in display mode.$

注意到 $∑n=0mPn=1\sum_{n=0}^{m} P_{n}=1$ , 由递推关系可得

系统状态概率

$KaTeX parse error: {equation} can be used only in display mode.$

系统运行指标

$Ls=∑n=0mnPn=m−uλ(1−P0),Lq=∑n=1∞(n−1)Pn=m−(λ+μ)(1−P0)λ=Ls−(1−P0).Ws=mμ(1−P0)−1λ.Wq=Ws−1μ\begin{aligned} &L_{s}=\sum_{n=0}^{m} n P_{n}=m-\frac{u}{\lambda}\left(1-P_{0}\right), \\ &L_{q}=\sum_{n=1}^{\infty}(n-1) P_{n}=m-\frac{(\lambda+\mu)\left(1-P_{0}\right)}{\lambda}=L_{s}-\left(1-P_{0}\right) . \\ &W_{s}=\frac{m}{\mu\left(1-P_{0}\right)}-\frac{1}{\lambda} . \\ &W_{q}=W_{s}-\frac{1}{\mu} \end{aligned}$

多服务台模型

4.多服务台标准型M/M/C型

顾客流为泊松流，平均到达率为A，各个服务台的平均服务率是\mu，

则整个服务机构的平均服务率是 $nμ(n<c)或cμ(n>c)n\mu(n<c)或c\mu(n>c)$ ，令 $ρ=λcμ\rho=\frac{\lambda}{c\mu}$ ，称为系统服务强度当 $ρ>1\rho>1$ 时，会出现排队现象。

状态转移图

稳态状态方程

分别对0，1<n<c的n，n>c的n，三个状态列方程

$KaTeX parse error: {equation} can be used only in display mode.$

解得

系统状态概率

$_{0}=\left[\sum_{k=0}^{c=1} \frac{1}{k !}\left(\frac{\lambda}{\mu}\right)^{k}+\frac{1}{c !} \frac{1}{1-\rho}\left(\frac{\lambda}{\mu}\right)^{c}\right]^{-1}$ ,

$KaTeX parse error: {equation} can be used only in display mode.$

系统运行指标

系统运行指标: $KaTeX parse error: {equation} can be used only in display mode.$

5.系统容量有限制： $M/M/c/N/∞M/M/c/N/\infty$

状态转移图

稳态状态方程

分别对0，1<n<c的n(类比状态4-1)，n>c的n(类比状态4-2)**，N，四个状态列方程

$ρ=λcμ≤1\begin{aligned} &\left\{\begin{array}{l} \mu P_{1}=\lambda P_{0} \\ (n+1) \mu P_{n+1}+\lambda P_{n-1}=(\lambda+n \mu) P_{n}(1 \leq n \leq c) \\ c \mu P_{n+1}+\lambda P_{n-1}=(\lambda+n \mu) P_{n}(c \leq n<N-1) \\ \lambda P_{N-1}=c \mu P_{N} \end{array}\right. \\ &\text { 其中 } \sum_{n=0}^{N} P_{n}=1, \text { 且 } \rho=\frac{\lambda}{c \mu} \leq 1 \end{aligned}$

系统状态概率

由递推关系可得系统状态概率为: $KaTeX parse error: {equation} can be used only in display mode.$

$KaTeX parse error: {equation} can be used only in display mode.$

系统运行指标

$Ls=Lq+λμLq=∑n=c+1N(n−c)PN=(cρ)cρc!(1−ρ)2P0[1−ρN−c(1−ρ)ρN−c]Ws=Wq+1μWq=Lqλ(1−PN),\begin{aligned} &L_{s}=L_{q}+c \rho\left(1-P_{N}\right),=\frac{\lambda_{e}}{\mu} \mid \text { Little公式: } L_{s}=L_{q}+\frac{\lambda}{\mu} \\ &L_{q}=\sum_{n=c+1}^{N}(n-c) P_{N}=\frac{(c \rho)^{c} \rho}{c !(1-\rho) 2} P_{0}\left[1-\rho^{N-c}(1-\rho) \rho^{N-c}\right] \\ &W_{s}=W_{q}+\frac{1}{\mu} \\ &W_{q}=\frac{L_{q}}{\lambda\left(1-P_{N}\right)}, \end{aligned}$

6.顾客源为有限型M/M/c/\infty/m$型（与上一种相比有效到达率不同）

状态转移图

到达率是 $(m−n)λ(m-n)\lambda$

稳态状态方程

分别对0，1<n<c的n(类比状态4-1)，n>c的c(类比状态4-2)**，m，四个状态列方程

$ρ=λcμ≤1\begin{aligned} &\left\{\begin{array}{l} \mu P_{1}=m\lambda P_{0} \\ (n+1) \mu P_{n+1}+[(m-n+1)\lambda P_{n-1}]=[(m-n)\lambda+n \mu)] P_{n}, (1 \leq n \leq c) \\ c \mu P_{n+1}+(m-c+1)\lambda P_{n-1}=[(m-c)\lambda+c \mu) P_{n}, (c \leq n<m-1) \\ \lambda P_{m-1}=c \mu P_{m} \end{array}\right. \\ &\text { 其中 } \sum_{n=0}^{N} P_{n}=1, \text { 且 } \rho=\frac{\lambda}{c \mu} \leq 1 \end{aligned}$

系统状态概率

由递推关系可得系统状态概率 $KaTeX parse error: {equation} can be used only in display mode.$

系统数量指标

系统运行指标为: $KaTeX parse error: {equation} can be used only in display mode.$

例题再分析

排成两队——到达率 $λ\lambda$ 变成一半

一个队两个服务台——C变成两倍

会发现两种情况的指标是不同的，排成一个队更快

总结

以上是生活随笔为你收集整理的排队论模型的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。

模型

上一篇： android调用相册和摄像头,Andr
下一篇：省市区sql语句之：（三）区1

编程问答

排队论模型

排队论模型

现实中的问题

排队论的基本组成

排队系统

总结：

输入

排队规则

服务规则

排队模型的评价数量指标

如何求数量指标

需要提前知道的数据

记号方案

X,Y的表示

其他记号的表示方式

排队论模型

单服务台模型分为3种

1.标准型：M/M/1型

稳态概率方程

求评价指标

对应的lingo程序

评价指标间的关系

例题

2.系统容量有限制：M/M/1/N/∞\infty∞型

稳态概率方程

系统状态概率

评价指标

3.顾客源为有限型：M/M/1/∞/mM/M/1/\infty/mM/M/1/∞/m型

概率稳态方程

系统状态概率

系统运行指标

多服务台模型

4.多服务台标准型M/M/C型

状态转移图

稳态状态方程

系统状态概率

系统运行指标

5.系统容量有限制：M/M/c/N/∞M/M/c/N/\inftyM/M/c/N/∞

状态转移图

稳态状态方程

系统状态概率

系统运行指标

6.顾客源为有限型M/M/c/\infty/m$型（与上一种相比有效到达率不同）

状态转移图

稳态状态方程

系统状态概率

系统数量指标

例题再分析

排成两队——到达率 λ\lambdaλ 变成一半

一个队两个服务台——C变成两倍

总结

2.系统容量有限制：M/M/1/N/ $∞\infty$ 型

3.顾客源为有限型： $M/M/1/∞/mM/M/1/\infty/m$ 型

5.系统容量有限制： $M/M/c/N/∞M/M/c/N/\infty$

排成两队——到达率 $λ\lambda$ 变成一半