南充网站建设有哪些,企业网页设计价格,建设部网站首页格式合同,wordpress学校管理系统排队理论简介 1. 理论背景2. 研究的数学方法3. 拒绝型排队系统与等候型排队系统4. 拒绝型排队系统 本文参考文献为Вентцель Е. С.的《Исследование операций》。 1. 理论背景
排队理论又称大众服务理论#xff0c;顾名思义指的是在有限的服务条… 排队理论简介 1. 理论背景2. 研究的数学方法3. 拒绝型排队系统与等候型排队系统4. 拒绝型排队系统 本文参考文献为Вентцель Е. С.的《Исследование операций》。 1. 理论背景
排队理论又称大众服务理论顾名思义指的是在有限的服务条件下服务大量人员的一种理论情景。日常生活中常见的场景如排队的电话亭、等待理发的顾客、售票窗口、商店结账处等等。
显然这些排队情景中都有一些共性。如
每个排队情景必然包括若干“服务人员”称之为服务通道。一个排队情景中可以有一个或多个服务通道。每个排队情景中必然也包括若干申请流或称请求流这些请求在某个随机时刻进入该排队系统。当前正在处理的申请会占据一定的时间在这段时间之后处理该申请的通道会“放空”并等待处理下一个申请。当有多余的申请等待处理时该申请有2种情况要么等待被处理形成“队列”即排队要么离开该服务通道。除4中的情况外一个服务通道还可能处于非满载状态或停工状态。
一个服务通道能够成功处理的申请数称为通过性。而排队理论研究的正是申请流、服务通道数量、服务通道的工作能力、排队系统的工作规则、工作效率等问题。
一般地衡量一个排队系统的效率特征可以用以下的方式
单位时间内可以处理的申请平均数量无法被满足、使排队系统无法服务的申请所占的百分比提交的申请能及时被处理的概率排队等候的平均用时等候用时的时长的分布律申请队列中的申请平均数量队列中申请数量的分布律单位时间内排队系统带来的平均收入。
2. 研究的数学方法
如果排队系统中的随机过程是马尔科夫过程那么对排队系统的数学建模将会很简单。而如果排队系统中的过程确实是马尔科夫过程那么逐个发生的事件流必须是泊松过程即每个单独的事件都没有相应的后果或后续动作。对于排队过程来说即需要申请流和服务流都满足泊松过程。然而业已证明排队系统越复杂服务通道越多则越可以近似于马尔科夫过程。因此采用马尔科夫过程研究排队理论并无大碍。
在研究排队过程之前需要知道系统中的几个基本参数。 n n n – 服务通道数量 λ \lambda λ – 申请流的强度 μ \mu μ – 每个服务通道的处理能力工作产能即每个服务通道单位时间内可处理的申请的平均数量 形成排队的条件若存在。
设排队系统中的申请流和服务流都是泊松过程且为定常的参数不随时间变化。而每2个事件之间的时间间隔 T T T是随机变量其分布满足如下概率分布密度函数 f ( t ) λ e − λ t ( t 0 ) f(t) \lambda {\rm e}^{-\lambda t} \quad (t 0) f(t)λe−λt(t0)
3. 拒绝型排队系统与等候型排队系统
排队系统分为2类
拒绝型。当所有服务通道都被占用时新的申请会被拒绝离开排队系统并之后不再参与进来。等候型。当所有服务通道都被占用时新的申请加入等候队列。当某个通道处理完上一个申请变为空时就从等候队列中转移一个申请至该通道并处理。
接下来将着重讲解拒绝型排队系统的数学模型。
4. 拒绝型排队系统
对于拒绝型排队系统来说衡量其效率的指标称为绝对通过性指的是单位时间内系统可以处理的申请的平均数量。与之对应的概念是相对通过性指单位时间内被系统处理的申请的平均数与该时间段内新增的申请数之比值。
设系统中有 n n n个服务通道。根据被占用的通道的个数将系统的状态分为如下几类 S 0 S_0 S0 – 所有服务通道都空 S 1 S_1 S1 – 只有一个服务通道被占用其他通道都空 ⋯ \cdots ⋯ S k S_k Sk – 有 k k k个通道被占用其他通道都空 ⋯ \cdots ⋯ S n S_n Sn – 所有 n n n个通道都被占用。
如下图所示是拒绝型排队系统的示意图。 一开始系统中没有申请所有服务通道为空系统状态为 S 0 S_0 S0。当有一个申请加入时占用一个服务通道系统状态从 S 0 S_0 S0变为 S 1 S_1 S1即 S 0 → S 1 S_0 \rightarrow S_1 S0→S1此过程的强度或密度为 λ \lambda λ可以理解为单位时间内新增了 λ \lambda λ个申请。以此类推直到所有 n n n个通道均被占用。从低占用向高占用转化的过程中每个状态转化的强度都是 λ \lambda λ。
当系统处于 S 1 S_1 S1状态而该申请被完成时系统将变成 S 0 S_0 S0状态即 S 1 → S 0 S_1 \rightarrow S_0 S1→S0。此过程的强度或密度为 μ \mu μ可以理解为一个被占用的服务通道单位时间内可以服务 μ \mu μ个申请。值得注意的是从高占用向低占用转化的过程的强度并非全是 μ \mu μ如图所示 S k 1 → S k S_{k1} \rightarrow S_k Sk1→Sk过程的强度为 ( k 1 ) μ \left( k1 \right) \mu (k1)μ。
利用柯尔莫哥洛夫方程对图中每个状态的“入量”和“出量”进行描述可以得到每个状态的柯尔莫哥洛夫方程。如对于某个状态 S k S_k Sk来说其“出量”即图中从方块 S k S_k Sk发出的箭头有两个分别是方块 S k S_k Sk右上的 λ \lambda λ和左下的 k μ k \mu kμ而“入量”即图中进入方块 S k S_k Sk的箭头也有2个分别是方块 S k S_k Sk左上的 λ \lambda λ和右下的 ( k 1 ) μ (k1) \mu (k1)μ。那么状态 S k S_k Sk的概率可以描述为 d p k d t − ( λ k μ ) p k λ p k − 1 ( k 1 ) μ p k 1 \frac{ {\rm d} p_k }{ {\rm d} t } -\left( \lambda k \mu \right) p_k \lambda p_{k-1} (k1) \mu p_{k1} dtdpk−(λkμ)pkλpk−1(k1)μpk1上式的含义是
所有方块 S k S_k Sk的出量均为负项而入量为正项出量有2个1) 右上的 λ \lambda λ从 S k S_k Sk出发其概率为 p k p_k pk故该项是 − λ p k -\lambda p_k −λpk2) 左下的 k μ k \mu kμ也从 S k S_k Sk出发其概率也是 p k p_k pk故该项是 − k μ p k -k \mu p_k −kμpk。入量有2个1) 右下的 ( k 1 ) μ (k1) \mu (k1)μ从上一个状态 S k 1 S_{k1} Sk1出发其概率对应是 p k 1 p_{k1} pk1故该项是 ( k 1 ) μ p k 1 (k1) \mu p_{k1} (k1)μpk12) 左上的 λ \lambda λ从上一个状态 S k − 1 S_{k-1} Sk−1出发其概率对应是 p k − 1 p_{k-1} pk−1故该项是 λ p k − 1 \lambda p_{k-1} λpk−1。注意从哪个方块 S i S_i Si出发概率 p i p_i pi的下标就要和方块的下标对应概率 p i p_i pi取决于箭头的出发地而不是指向地
由此可以写出图中的微分方程关系 d p 0 d t − λ p 0 μ p 1 d p 1 d t − ( λ μ ) p 1 λ p 0 2 μ p 1 ⋮ d p k d t − ( λ k μ ) p k λ p k − 1 ( k 1 ) μ p k 1 ⋮ d p n d t − n μ p n λ p n − 1 (1) \begin{aligned} \frac{ {\rm d} p_0 }{ {\rm d} t } - \lambda p_0 \mu p_1 \\ \frac{ {\rm d} p_1 }{ {\rm d} t } - \left( \lambda \mu \right) p_1 \lambda p_0 2\mu p_1 \\ \vdots \\ \frac{ {\rm d} p_k }{ {\rm d} t } - \left( \lambda k\mu \right) p_k \lambda p_{k-1} (k1) \mu p_{k1} \\ \vdots \\ \frac{ {\rm d} p_n }{ {\rm d} t } - n\mu p_n \lambda p_{n-1} \\ \tag{1} \end{aligned} dtdp0dtdp1⋮dtdpk⋮dtdpn−λp0μp1−(λμ)p1λp02μp1−(λkμ)pkλpk−1(k1)μpk1−nμpnλpn−1(1)上述方程称为艾拉姆咖方程。初始条件为 p 0 ( 0 ) 1 , p 1 ( 0 ) p 2 ( 0 ) ⋯ p n ( 0 ) 0 p_0 (0) 1, \qquad p_1(0) p_2(0) \cdots p_n(0) 0 p0(0)1,p1(0)p2(0)⋯pn(0)0艾拉姆咖方程往往无法手解需要通过计算机辅助求解得到结果 p i ( t ) p_i(t) pi(t)为每种状态出现的概率。
另外在实际运用中往往还感兴趣状态的边界概率指系统的稳态模式下的概率。这里不加推导地给出公式 p k λ k μ ⋅ 2 μ ⋯ k μ p 0 ( λ / μ ) k k ! p 0 p 0 1 1 λ / μ 1 ! ( λ / μ ) 2 2 ! ⋯ ( λ / μ ) n n ! p_k \frac{\lambda^k}{\mu \cdot 2\mu \cdots k\mu} p_0 \frac{ \left( \lambda / \mu \right)^k}{k!} p_0 \\ p_0 \frac{1}{ 1 \frac{\lambda / \mu}{1!} \frac{ \left( \lambda / \mu \right)^2}{2!} \cdots \frac{ \left( \lambda / \mu \right)^n}{n!} } pkμ⋅2μ⋯kμλkp0k!(λ/μ)kp0p011!λ/μ2!(λ/μ)2⋯n!(λ/μ)n1记 λ / μ ρ \lambda / \mu \rho λ/μρ称为换算强度其物理意义是在处理一个请求的平均时长内到来新增的请求的平均数量。
则上述边界概率公式可改写为 p k ρ k k ! p 0 p_k \frac{\rho^k}{k!} p_0 pkk!ρkp0 p 0 1 1 ρ 1 ! ρ 2 2 ! ⋯ ρ n n ! (2) p_0 \frac{1}{ 1 \frac{\rho}{1!} \frac{ \rho^2}{2!} \cdots \frac{ \rho^n}{n!} } \tag{2} p011!ρ2!ρ2⋯n!ρn1(2)式(2)同样称为艾拉姆咖方程。
显然所有通道都被占用的概率是 p n p_n pn那么“新增申请能够被处理”的概率为 q 1 − p n q 1 - p_n q1−pn进而绝对通过性为 A λ q λ ( 1 − p n ) A \lambda q \lambda \left(1 - p_n \right) Aλqλ(1−pn)则繁忙通道的平均个数 k ˉ \bar k kˉ可以表示为加权和 k ˉ 0 ⋅ p 0 1 ⋅ p 1 ⋯ n ⋅ p n \bar k 0 \cdot p_0 1 \cdot p_1 \cdots n \cdot p_n kˉ0⋅p01⋅p1⋯n⋅pn即为数学期望。 另一方面由于绝对通过性表示单位时间内处理的申请的平均数量而一个被占用的服务通道在单位时间内可以处理 μ \mu μ个申请故繁忙通道的平均个数亦可表示为 k ˉ A μ λ ( 1 − p n ) μ ρ ( 1 − p n ) \bar k \frac{A}{\mu} \frac{ \lambda \left(1 - p_n \right) }{\mu} \rho \left( 1 - p_n\right) kˉμAμλ(1−pn)ρ(1−pn)
