理论背景

排队理论又称大众服务理论#xff0c;顾名思义指的是在有限的服务条…

排队理论简介

排队理论又称大众服务理论顾名思义指的是在有限的服务条件下服务大量人员的一种理论情景。

日常生活中常见的场景如排队的电话亭、等待理发的顾客、售票窗口、商店结账处等等。

每个排队情景必然包括若干“服务人员”称之为服务通道。

一个排队情景中可以有一个或多个服务通道。

每个排队情景中必然也包括若干申请流或称请求流这些请求在某个随机时刻进入该排队系统。

当前正在处理的申请会占据一定的时间在这段时间之后处理该申请的通道会“放空”并等待处理下一个申请。

当有多余的申请等待处理时该申请有2种情况要么等待被处理形成“队列”即排队要么离开该服务通道。

除4中的情况外一个服务通道还可能处于非满载状态或停工状态。

一个服务通道能够成功处理的申请数称为通过性。

而排队理论研究的正是申请流、服务通道数量、服务通道的工作能力、排队系统的工作规则、工作效率等问题。

单位时间内可以处理的申请平均数量无法被满足、使排队系统无法服务的申请所占的百分比提交的申请能及时被处理的概率排队等候的平均用时等候用时的时长的分布律申请队列中的申请平均数量队列中申请数量的分布律单位时间内排队系统带来的平均收入。

如果排队系统中的随机过程是马尔科夫过程那么对排队系统的数学建模将会很简单。

而如果排队系统中的过程确实是马尔科夫过程那么逐个发生的事件流必须是泊松过程即每个单独的事件都没有相应的后果或后续动作。

对于排队过程来说即需要申请流和服务流都满足泊松过程。

然而业已证明排队系统越复杂服务通道越多则越可以近似于马尔科夫过程。

因此采用马尔科夫过程研究排队理论并无大碍。

\lambda

每个服务通道的处理能力工作产能即每个服务通道单位时间内可处理的申请的平均数量

设排队系统中的申请流和服务流都是泊松过程且为定常的参数不随时间变化。

而每2个事件之间的时间间隔

f(t)

拒绝型。

当所有服务通道都被占用时新的申请会被拒绝离开排队系统并之后不再参与进来。

等候型。

当所有服务通道都被占用时新的申请加入等候队列。

当某个通道处理完上一个申请变为空时就从等候队列中转移一个申请至该通道并处理。

拒绝型排队系统

对于拒绝型排队系统来说衡量其效率的指标称为绝对通过性指的是单位时间内系统可以处理的申请的平均数量。

与之对应的概念是相对通过性指单位时间内被系统处理的申请的平均数与该时间段内新增的申请数之比值。

设系统中有

n个通道均被占用。

从低占用向高占用转化的过程中每个状态转化的强度都是

\lambda

μ个申请。

值得注意的是从高占用向低占用转化的过程的强度并非全是

\mu

利用柯尔莫哥洛夫方程对图中每个状态的“入量”和“出量”进行描述可以得到每个状态的柯尔莫哥洛夫方程。

如对于某个状态

S_k

dtdpk​​−(λkμ)pk​λpk−1​(k1)μpk1​上式的含义是

所有方块

dtdp0​​dtdp1​​⋮dtdpk​​⋮dtdpn​​​−λp0​μp1​−(λμ)p1​λp0​2μp1​−(λkμ)pk​λpk−1​(k1)μpk1​−nμpn​λpn−1​​(1)上述方程称为艾拉姆咖方程。

初始条件为

p_0

p0​(0)1,p1​(0)p2​(0)⋯pn​(0)0艾拉姆咖方程往往无法手解需要通过计算机辅助求解得到结果

p_i(t)

另外在实际运用中往往还感兴趣状态的边界概率指系统的稳态模式下的概率。

这里不加推导地给出公式

p_k

pk​μ⋅2μ⋯kμλk​p0​k!(λ/μ)k​p0​p0​11!λ/μ​2!(λ/μ)2​⋯n!(λ/μ)n​1​记

\lambda

λ/μρ称为换算强度其物理意义是在处理一个请求的平均时长内到来新增的请求的平均数量。

p_k

p0​11!ρ​2!ρ2​⋯n!ρn​1​(2)式(2)同样称为艾拉姆咖方程。

p_n

另一方面由于绝对通过性表示单位时间内处理的申请的平均数量而一个被占用的服务通道在单位时间内可以处理

\mu