目录 第3章爱尔郎排队系统 3.1爱尔郎分布 3.2爱尔朗排队系统的相位分析法 3.3M/E./1排队模型 34E/M/排队模型 3.5批到达排队系统 3.6批服务排队系统
目 录 第 3 章 爱尔郎排队系统 3.1 爱尔郎分布 3.2 爱尔朗排队系统的相位分析法 3.3 M / E / 1 r 排队模型 3.4 E / M / 1 r 排队模型 3.5 批到达排队系统 3.6 批服务排队系统
第3章爱尔朗排队系统 第2章我们研究了生灭排队系统,它的基本特点是:状态转移只能在相邻状态之间 进行。现在放宽这种限制,允许状态的转移可以在不相邻状态之间进行,各种基本分布 仍然是负指数型的。我们可以把它想象为更一般的生灭系统。 我们仍然只考虑在排队系统达到稳态后的状态变化情况,即只求系统的平衡解。第 2章所讲的平衡状态下的信息流速率守恒的原理在这里仍然适用,即流入某状态的信息 速率与流出该状态的信息流速率是相等的。同样,我们采用状态转移率图来描述状态的 转移。 3.1爱尔郎分布概率密度函数的推导 在第1章我们曾经复习过r阶爱尔郎分布的定义,亦即,设v,v2, 是r个 相互独立的、服从相同参数rμ的负指数分布的连续型随机变量,则称T=v1+v2+…+v 服从r阶爱尔郎分布 为了叙述方便起见,下面以服务时间(连续型随机变量)为例,推导爱尔郎分布的 概率密度函数。我们已经知道,负指数分布的服务时间(以及到达间隔时间为负指数分 布)在分析排队系统中是非常简单和非常有用的。但是在实际生活中,有些排队系统的 特性并不符合负指数分布,若仍然用负指数分布来描述系统就会产生较大的误差。为了 解决这个问题,在这一节中,我们研究多个负指数分布的组合,以导出一种新的服务时 间分布。 服务时间为负指数分布的服务装置如图3.1所示。 图3.1单级负指数分布服务 圆圈代表一个系统的服务装置,它的服务时间分布为负指数分布。圆圈中的代表 服务率。 该负指数分布的概率密度函数为 b( )sJke-t≥0 e-"u(t),u()是单位阶跃函数 0t<0 这个系统的数学期望和方差值分别为:
486 第 3 章 爱尔朗排队系统 第 2 章我们研究了生灭排队系统，它的基本特点是：状态转移只能在相邻状态之间 进行。现在放宽这种限制，允许状态的转移可以在不相邻状态之间进行，各种基本分布 仍然是负指数型的。我们可以把它想象为更一般的生灭系统。 我们仍然只考虑在排队系统达到稳态后的状态变化情况，即只求系统的平衡解。第 2 章所讲的平衡状态下的信息流速率守恒的原理在这里仍然适用，即流入某状态的信息 速率与流出该状态的信息流速率是相等的。同样，我们采用状态转移率图来描述状态的 转移。 3.1 爱尔郎分布概率密度函数的推导 在第 1 章我们曾经复习过r 阶爱尔郎分布的定义，亦即，设 1 v ， 2 v ，， r v 是r 个 相互独立的、服从相同参数r 的负指数分布的连续型随机变量，则称 r T v v v 1 2 服从r 阶爱尔郎分布。 为了叙述方便起见，下面以服务时间（连续型随机变量）为例，推导爱尔郎分布的 概率密度函数。我们已经知道，负指数分布的服务时间（以及到达间隔时间为负指数分 布）在分析排队系统中是非常简单和非常有用的。但是在实际生活中，有些排队系统的 特性并不符合负指数分布，若仍然用负指数分布来描述系统就会产生较大的误差。为了 解决这个问题，在这一节中，我们研究多个负指数分布的组合，以导出一种新的服务时 间分布。 服务时间为负指数分布的服务装置如图 3.1 所示。 图 3.1 单级负指数分布服务 圆圈代表一个系统的服务装置，它的服务时间分布为负指数分布。圆圈中的 代表 服务率。 该负指数分布的概率密度函数为： e u t t e t b t t t 0 0 0 ，ut是单位阶跃函数。 这个系统的数学期望和方差值分别为：
ET] 现在考虑如图32所示的系统,它由两个服务时间为负指数分布的服务装置串联构 成,单个服务装置的服务率为2H。 2 图32两级负指数分布服务 单个服务装置的概率分布密度函数为: h()=2/e2"ult) 相应的数学期望和方差为 E[T,]=e, D[, I 这样一个两级服务装置的工作方式是:一个顾客进入前一级接受服务,服务完毕后 再进入下一级,两级服务完成后,该顾客离开系统。此时,才允许下一个顾客进入前一 级装置接受服务。 在任意一个时刻,这两级服务装置的忙闲状态只有以下三种情况之一: 第一级忙,第二级闲。 第一级闲,第二级忙 ③两级均空闲。 个顾客在系统中接受服务的时间等于各级服务时间的和,而这两个服务时间是相 互独立具有同分布的。在概率论中我们已经学过,两个独立随机变量的和的概率密度函 数等于它们概率密度函数的卷积。由此可以推得 b2()=b()*b()=」h()(-)dr =2e2.2er=2(2u)2m t≥0 又根据:随机变量和的数学期望等于它们的数学期望的和,随机变量和的方差等于 它们方差的和。我们有 E]=2E]=,D[]=D[]+D[]= 对于这样一个系统,仅说明系统中的顾客数是不够的。为了能总和系统在任意时刻 487
487 1 E T ， 2 1 D T 现在考虑如图 3.2 所示的系统，它由两个服务时间为负指数分布的服务装置串联构 成，单个服务装置的服务率为2 。 2 2 图 3.2 两级负指数分布服务 单个服务装置的概率分布密度函数为： h t e u t t 2 2 相应的数学期望和方差为： 2 1 E Th ， 2 2 1 D Th 这样一个两级服务装置的工作方式是：一个顾客进入前一级接受服务，服务完毕后 再进入下一级，两级服务完成后，该顾客离开系统。此时，才允许下一个顾客进入前一 级装置接受服务。 在任意一个时刻，这两级服务装置的忙闲状态只有以下三种情况之一： ① 第一级忙，第二级闲。 ② 第一级闲，第二级忙。 ③ 两级均空闲。 一个顾客在系统中接受服务的时间等于各级服务时间的和，而这两个服务时间是相 互独立具有同分布的。在概率论中我们已经学过，两个独立随机变量的和的概率密度函 数等于它们概率密度函数的卷积。由此可以推得： b t ht ht 2 h ht d e e d t t 2 0 2 2 2 t t e 2 2 2 t 0 又根据：随机变量和的数学期望等于它们的数学期望的和，随机变量和的方差等于 它们方差的和。我们有： 1 E T 2E Th ， 2 1 2 DT DT DT h h 对于这样一个系统，仅说明系统中的顾客数是不够的。为了能总和系统在任意时刻
以前的全部历史,还必须说明此刻在服务装置中的顾客正处于哪一级装置上。为此,我 们用一个两维的随机变量E.,来表示系统的状态。它说明系统中共有k个顾客,其中正在 接受服务的那个顾客现在正处于第j级,这样一个随机变量实际上是满足马尔柯夫特性 的。状态的下一次变化(EH,E4M,…)只与E.,有关,而与Ek,以前的状态无关。 推广以上的两级装置,我们可以有一个r级服务装置,如图3.3所示。 图3.3r级负指数分布服务 其中单级的概率密度函数为: h(t)=rue u(o) 相应的数学期望和方差为:E[ 万] 我们可以直接求出系统服务时间的数学期望和方差 E[T]=rE(T=rru/u D[门]=rD[] 系统的服务时间分布的密度函数等于r个负指数分布的卷积,采用求卷积积分的方 法来求解这个分布是很困难的。为了简化求解过程,可以釆用拉普拉斯变换法来求解。 取负指数分布的拉普拉斯变换 h()<→H(s) 令b,()的拉普拉斯变换为B,(s)。 根据卷积定理,时域中的卷积等于变换域中的乘积,故有 B()=H'(s) s+r 求拉普拉斯逆变换,得 t≥0 (3.1) 这就是著名的r阶爱尔郎分布 如果在(31)式中令r=1,就得到了负指数分布,由此可知,负指数分布是爱尔 郎分布的一种特殊形式。爱尔郎分布具有广泛的用途,许多实际系统都可以用爱尔郎分 488
488 以前的全部历史，还必须说明此刻在服务装置中的顾客正处于哪一级装置上。为此，我 们用一个两维的随机变量 Ek , j 来表示系统的状态。它说明系统中共有k 个顾客，其中正在 接受服务的那个顾客现在正处于第 j 级，这样一个随机变量实际上是满足马尔柯夫特性 的。状态的下一次变化（ Ek , j1 ，Ek1, j ，）只与 Ek , j 有关，而与 Ek , j 以前的状态无关。 推广以上的两级装置，我们可以有一个r 级服务装置，如图 3.3 所示。 r r r r 1 2 r1 r 图 3.3 r 级负指数分布服务 其中单级的概率密度函数为： h t r e u t rt 相应的数学期望和方差为： 1 E Th r ， 2 1 D Th r 我们可以直接求出系统服务时间的数学期望和方差： 1 1 E T rE T r h r ， 2 1 D T rD Th r 系统的服务时间分布的密度函数等于r 个负指数分布的卷积，采用求卷积积分的方 法来求解这个分布是很困难的。为了简化求解过程，可以采用拉普拉斯变换法来求解。 取负指数分布的拉普拉斯变换： s r r h t H s 令b t r 的拉普拉斯变换为 B s r 。 根据卷积定理，时域中的卷积等于变换域中的乘积，故有 r r r s r r B s H s 求拉普拉斯逆变换，得 1 ! 1 r r r t e b t r r t r t 0 （3.1） 这就是著名的 r 阶爱尔郎分布。 如果在（3.1）式中令r 1，就得到了负指数分布，由此可知，负指数分布是爱尔 郎分布的一种特殊形式。爱尔郎分布具有广泛的用途，许多实际系统都可以用爱尔郎分
布来描述,下面我们将要研究具有爱尔郎分布的排队系统。 3.2爱尔朗排队系统的相位分析法 根据爱尔郎分布的定义,一个r阶爱尔朗分布的随机变量(参数为r)为r个相互 独立、服从相同参数为r的负指数分布的随机变量之和。因此,若某个服务者的服务 时间的概率分布服从分布密度为b()=gcm(20)的r阶爱尔朗分布,则可 认为某顾客在其整个服务过程中通过了r级参数为r的相互独立的负指数分布服务装 置(在服务装置之间无等待)。若将每一级服务装置看作一个相位,一个顾客服务完成 则相当于该顾客经历完这r个相位,每个相位的服务时间均值为1。仅当一个顾客经 历完最后一个相位的服务后,下一顾客才能开始接受服务。 我们将服务时间分布服从r阶爱尔朗分布的服务机构按相位分解如图34所示。 到达 )>(m)…→(m)→… 离去 服务装置 图34r阶爱尔朗服务时间的服务机构相位分解 同样,若把到达间隔时间服从r阶爱尔朗分布(参数为r)的随机变量,看作是r 个参数为r的负指数分布的随机变量之和。则可以把每一顾客到达排队系统看作首先 须通过r级串联的到达装置才能进入排队系统等待或接受服务。通过每一个到达装置的 时间服从参数为r的负指数分布,每个到达装置为一个相位。一个顾客须通过r级到达 装置完毕才能进入排队系统,此时下一个顾客才能进入到达装置。这种相位分解法,使 得我们再次可利用负指数分布的无后效性。 将到达间隔时间分布为E的相位分解如图35描述。 服务机构/离去 到达装置
489 布来描述，下面我们将要研究具有爱尔郎分布的排队系统。 3.2 爱尔朗排队系统的相位分析法 根据爱尔郎分布的定义，一个r 阶爱尔朗分布的随机变量（参数为r ）为r 个相互 独立、服从相同参数为r 的负指数分布的随机变量之和。因此，若某个服务者的服务 时间的概率分布服从分布密度为 1 ! 1 r r r t e b t r r t r （t 0 ）的r 阶爱尔朗分布，则可 认为某顾客在其整个服务过程中通过了 r 级参数为 r 的相互独立的负指数分布服务装 置（在服务装置之间无等待）。若将每一级服务装置看作一个相位，一个顾客服务完成 则相当于该顾客经历完这r 个相位，每个相位的服务时间均值为 r 1 。仅当一个顾客经 历完最后一个相位的服务后，下一顾客才能开始接受服务。 我们将服务时间分布服从r 阶爱尔朗分布的服务机构按相位分解如图 3.4 所示。 r r r r 1 2 i r 图 3.4 r 阶爱尔朗服务时间的服务机构相位分解 同样，若把到达间隔时间服从r 阶爱尔朗分布（参数为r ）的随机变量，看作是r 个参数为r 的负指数分布的随机变量之和。则可以把每一顾客到达排队系统看作首先 须通过r 级串联的到达装置才能进入排队系统等待或接受服务。通过每一个到达装置的 时间服从参数为r 的负指数分布，每个到达装置为一个相位。一个顾客须通过r 级到达 装置完毕才能进入排队系统，此时下一个顾客才能进入到达装置。这种相位分解法，使 得我们再次可利用负指数分布的无后效性。 将到达间隔时间分布为 Er 的相位分解如图 3.5 描述。 r r r r 1 2 i r