本文主要是介绍运筹说 第112期 | M/M/s等待制排队模型,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
通过上期学习,大家已经了解了排队论中的一些基本概念,以及生灭过程和Poisson过程。
那么本期小编将基于这些基本原理,为大家介绍M/M/s混合制排队模型,包括单服务台模型和多服务台模型,介绍模型的概念以及推导过程等内容。M/M/s等待制排队模型有两种机制,分别为单服务台模型M/M/1/∞和多服务台模型M/M/s/∞。 单服务台模型是指顾客的相继到达时间服从参数为λ的负指数分布,服务台数为1,服务时间服从参数为μ的负指数分布,系统空间无限,允许无限排队。多服务台模型是指顾客的相继到达时间服从参数为λ的负指数分布,服务台数为s且服务时间相互独立,服务时间服从参数为μ的负指数分布,系统空间无限,允许无限排队。
单服务台模型
01 队长的分布
设pn=P{N=n}(n=0,1,2,…)为系统达到平衡状态后队长N的概率分布,此时λn=λ,μn=μ。记ρ=λ/μ,且ρ<1,则
因 ,故
其中, 是一个等比数列,所以根据等比数列求和公式S=首项/(1-公比),这里首项为1,公比为ρ,求出
ρ是系统中至少有一个顾客的概率,也就是服务台处于忙的状态的概率,因而也称ρ为服务强度,它反映了系统繁忙的程度。只有ρ<1,即要求顾客平均到达率小于系统平均服务率,才能使系统达到统计平衡,才有
02 几个重要的数量指标
对单服务台等待制排队系统,通过平稳状态下队长的分布(即当系统达到统计平衡时处于状态n的概率为pn)与队长n相乘后加总,可以得到平均队长L
平均排队长Lq为
顾客在系统中的逗留时间为T,由于到达过程和服务时间分别服从参数为λ和μ负指数分布,具有无记忆性;因此T服从参数为μ-λ负指数分布
因此,平均逗留时间W为
可发现平均队长L与平均逗留时间W具有如下关系
同样,可发现平均排队长Lq与平均等待时间Wq。有如下关系
上述两式通常称为Little公式,是排队论中一个非常重要的公式。
03 忙期和闲期
由于忙期和闲期出现的概率分别为ρ和1-ρ,所以可认为在一段时间内两者总长度之比为ρ:(1-ρ)。又因为忙期和闲期是交替出现的,所以在足够长的时间内,它们出现的平均次数应该是相同的。于是,忙期平均长度 和闲期平均长度 之比也为ρ:(1-ρ),即
在到达为Poisson流时,从系统空闲时刻起,到下一个顾客到达时刻止(闲期)的时间间隔仍服从参数为λ的负指数分布,且与到达时间间隔相互独立。故平均闲期为1/λ,可求得平均忙期为
可见,一个顾客在系统内的平均逗留时间=平均忙期。因此,一个顾客在系统内的平均逗留时间应等于服务员平均连续忙的时间。
例题展示
例1:修理店只有一个修理工,顾客到达为Poisson流,平均4人/h。修理时间服从负指数分布,平均需要6min。试求: (1)修理店空闲概率; (2)店内恰有3个顾客的概率; (3)店里至少有1个顾客的概率; (4)店内平均顾客数; (5)每位顾客在店内的平均逗留时间; (6)等待服务的平均顾客数; (7)每位顾客平均等待服务时间; (8)顾客在店内等待时间超过10min的概率。
解:本题为M/M/1/∞问题,λ=4,μ=1/0.1=10,ρ=λ/μ=2/5
(1)修理店空闲概率
(2)店内恰有3个顾客的概率
(3)店里至少有1个顾客的概率
(4)店内平均顾客数
(5)每位顾客在店内的平均逗留时间
(6)等待服务的平均顾客数
(7)每位顾客平均等待服务时间
(8)顾客在店内等待时间超过10min的概率
多服务台模型
01 基本概念
设顾客单个到达,相继到达时间间隔服从参数为的负指数分布,系统中共有s个服务台,服务台的服务时间相互独立,且服从参数为μ的负指数分布。系统空间无限,允许无限排队。 多服务台模型与单服务台模型的区别为:单服务台模型中服务率与系统状态无关,均为μ,服务强度ρ=λ/μ<1;而多服务台模型中服务率与系统状态有关。 02 过程推导
记pn=P{N=n}(n=0,1,2,…)为系统达到平稳状态后队长N的概率分布,对个数为s的多服务台系统,有
且
引入
列出平衡方程
可推导出
解得平衡条件下系统中顾客数为n的概率:
由 ,得
其中,
是一个等比数列(首项为 ,公比为 ),根据等比数列求和公式,求出
故
当n≥s时,再来的顾客就必须等待,则有
上式也被称为Erlang等待公式,它给出了顾客到达系统时需要等待的概率。对多服务台等待制排队系统,由已得到的平稳分布可得到平均排队长Lq
或
记系统中正在接受服务的顾客平均数为 ,显然也是正在忙的服务台平均数,故
平均在忙的服务台个数不依赖于服务台个数s,可得到平均队长L
对多服务台系统,Little公式依然成立,即有
例题展示
例2:急诊病人相继到达时间间隔服从负指数分布,平均每0.5h来一个;医生处理一个病人的时间也服从负指数分布,平均需要20min/人。现已有一个医生,考虑是否需要再增加一个医生?
解:本题可以看作为M/M/s/∞问题,λ=2,μ=3,ρ=λ/μ=2/3,s=1,2
由上表中的结果可知,从减少病人等待时间,提供及时处理来看,需要增加医生。以上就是M/M/s等待制排队模型的全部内容了,通过这一节的学习,大家可以尝试对现实生活中的一些实际问题进行练习了!
作者 | 林若唯 唐京茹
责编 | 王一静
审核 | 徐小峰
这篇关于运筹说 第112期 | M/M/s等待制排队模型的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!