第12章节排队论课件

《第12章节排队论课件》由会员分享，可在线阅读，更多相关《第12章节排队论课件（41页珍藏版）》请在金锄头文库上搜索。

1、第12章 排队论,第1节 基本概念,1.1 排队过程的一般表示,一般的排队过程为：顾客由顾客源出发，到达服务机构（服务台）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。排队过程的一般过程可用下图表示。,我们所说的排队系统就是指图中虚线所包括的部分。这里的“顾客”和“服务台”要作广泛的理解；队列可以是具体的，也可以是无形的。,1.2 排队系统的组成和特征,尽管排队系统是多种多样的，但从决定排队系统进程的因素来看，它有三个基本的组成部分，这就是输入过程、排队规则及服务机构。,顾客源中主体的数量是有限还是无限； 顾客到达的方式是单个到达还是成批到达； 顾客相继

2、到达的间隔时间分布是确定型的还是随机型的，是否相互独立，是否平稳，分布的类型和参数是什么。,2、排队规则 描述了顾客排队等待的队列和接受服务的次序。包括下列情况：,1、输入过程 描述了顾客来源以及顾客到达排队系统的规律。包括下列情况：,即时制还是等待制； 等待制下队列的情况（队列是有形还是无形的，单列还是多列，容量是否有限制；顾客在队列中能不能中途退出，在各列间能不能相互转移）； 等待制下顾客接受服务的次序（先到先服务，后到先服务，随机服务，有优先权的服务）。,服务台（员）的数目和排列情况； 服务台（员）的服务方式是对顾客单个进行的，还是成批进行的； 服务时间是确定型的还是随机型的，是否相互独

3、立，是否平稳 ，分布的类型和参数是什么 。,3、服务机构 描述了服务台（员）的机构形式和工作情况。包括下列情况：,1.3 排队模型的分类,在1971年关于排队论符号标准化的会议上决定，将Kendall符号扩充为： X/Y/Z/A/B/C 其中前三项意义不变，后三项意义分别为：A处填写系统容量限制；B处填写顾客源中的顾客数目；C处填写服务规则（如FCFS，LCFS）。 约定，如略去后三项，即指X/Y/Z/FCFS。,D.G.Kendall在1953年提出了一个分类方法，按照系统的三个最主要的、影响最大的特征要素进行分类，它们是：顾客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。 按照

4、这三个特征要素分类的排队系统，用符号（称为Kendall记号）表示为： X/Y/Z 其中，X处填写顾客相继到达间隔时间的分布，Y处填写服务时间的分布，Z处填写并列的服务台个数。,1.4 排队系统的求解,对于一个排队系统，运行状况的好坏既涉及到顾客的利益，又涉及到服务机构的利益，还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标，用以判断系统运行状况的优劣。 下面介绍几种常用的指标：,（1）队长，指在系统中的顾客数，它的期望值记作Ls。 排队长（队列长）， 指系统中排队等待服务的顾客数，它的期望值记作Lq。显然有 队长排队长正被服务的顾客数。

5、,（2）逗留时间，指一个顾客从到达排队系统到服务完毕离去的总停留时间，它的期望值记作Ws。等待时间，指一个顾客在系统中排队等待的时间，它的期望值记作Wq。显然有 逗留时间等待时间服务时间。,此外 ，还有忙期、损失率、服务强度等指标，都是常用的重要指标。,计算这些指标的基础是系统状态的概率分布。所谓状态，指系统中的顾客数，记为n，n=0,1, 2,（或n=0,1, 2, N，或n=0,1, 2,c）。,考虑在时刻t系统的状态为n的概率，用Pn(t)表示，它是随时刻t而变化的，称为系统的瞬态（或称过渡状态）。 求系统的瞬态是很不容易的，一般即使求出也很难利用，因此常用它的极限（如果存在的话）,称为

6、系统的稳态或称统计平衡状态。,稳态的物理意义是，当系统运行了无限长的时间以后，初始状态的影响将消失，系统的状态概率分布不再随时间变化。当然，实际应用中大多数系统会很快趋于稳态，无需等到无限长的时间以后。,第2节 几个主要概率分布,解决排队系统问题，先要把有关的原始资料进行统计，确定顾客到达间隔和服务时间的经验分布，然后按照统计学的方法确定符合哪种理论分布。 经验分布的主要指标如下：,2.1 经验分布,处理实际问题时，首先要记录每个顾客的到达时刻i和服务时间si；然后，计算出每个顾客的到达间隔ti 和排队等待时间i 再利用前面的公式计算出经验分布指标。例P308,2.2 泊松分布,（3）普通性：

7、在充分短的时间区间t内，到达两个或两个以上顾客的概率极小，可忽略不计，即,设N(t)表示在时间区间t0,t0+t)内到达的顾客数，是随机变量。当N(t)满足下面的三个条件时，我们说顾客的到达符合普阿松分布。这三个条件是：,（1）平稳性：在时间区间t0,t0+t)内到达的顾客数N(t)，只与区间长度t有关而与时间起点t0无关。,（2）无后效性：在时间区间t0,t0+t)内到达的顾客数N(t)，与t0以前到达的顾客数独立。,为了求出pn(t)，考虑0, t+t) 内来n个顾客的概率 pn(t+t )=pn(t)p0(t)+pn-1(t)p1(t)+p0(t)pn(t),N(t)的数学期望为t，可知

8、即平均到达率。,对于充分小的t， 则有 p0(t)=e-t=1-t+o(t) p1(t)=1-p0(t)+o(t) =t+o(t),p0(t)表示在时间长度为t的时间段中没有顾客到达的概率，它关于t单调下降，则存在0，使p0(t)=e-t,则 pn(t+t )=pn(t)(1-t)+pn-1(t) (t)+o(t) (n1),依次求解下去，可得,2.3 负指数分布,负指数分布具有下列性质： （1）无记忆性或马尔柯夫性，即 PTt+s / TsPTt （2）当顾客到达符合普阿松分布时，顾客相继到达的间隔时间T必服从负指数分布。,T的数学期望和方差分别为： ET1/， Var(T)1/2,用普阿松

9、分布描述顾客到达时，表示顾客的平均到达率，所以1/表示顾客相继到达的平均间隔时间。而用负指数分布描述顾客相继到达的间隔时间时，顾客相继到达的平均间隔时间为ET= 1/，所以同样表示顾客的平均到达率。,第3节 单服务台负指数分布排队系统分析,排队系统的状态n随时间变化的过程称为生灭过程。设平均到达率为,平均服务率为, 排队系统M/M/1/的生灭过程可用下面的状态转移图表示：,3.1 标准M/M/1模型(M/M/1/),这里的称为服务强度，也称话务强度，它刻画了服务机构的繁忙程度，所以又称服务机构的利用率。,系统的各项运行指标计算如下：,平均队长：,平均排队长：,逗留时间W的分布函数为:,平均逗留

10、时间:,平均等待时间:,解：,（2）排队等待平均病人数为 Lq= 5.25-0.84=4.41人,3.2 系统容量有限制的情形(M/M/1/N/),当系统的容量有限制(为N)时，设平均到达率为、平均服务率为，排队系统（M/M/1/N/）的生灭过程可用下面的状态转移图表示：,设=/1， 考虑到 p0+ p1+ + pN=1, 解得,系统的各项运行指标计算如下：,平均队长：,平均排队长：,有效到达率（平均单位时间实际进入排队系统的顾客数）：e=(1-pN)=(1-p0),平均逗留时间:,平均等待时间:,损失率:,例 单人理发馆有6个椅子接待人们排队等待理发，当6个椅子都坐满时，后来到的顾客不进店就

11、离开。顾客平均到达率为3人/小时，理发需时平均15分钟。求： （1）某顾客一到达就理发的概率； （2）需要等待的顾客数的期望值； （3）有效到达率； （4）一顾客在理发馆内逗留的期望时间； （5）到来的顾客不等待就离开的概率。,解：,（1）顾客一到达就理发的概率为,N=7， =3(人/小时)，=60/15=4 (人/小时),（2）需要等待的顾客数的期望值为,（3）有效到达率为 e = (1-p0) = 4(1-0.2778) = 2.89(人/小时),（4）顾客逗留的期望时间为 Ws=2.112.89=0.73小时,（5）顾客不等待就离开的概率为 p7 = 1-e/= 1-2.89/3 3.7

12、%,现以本例比较系统容量为有限和无限两种情况：,Lq = 2.11-(1-0.2778) = 1.39(人),3.3 顾客源为有限的情形(M/M/1/m),当系统的顾客源为有限(m)时，设各个顾客的平均到达率都为、服务台的平均服务率为， 排队系统的生灭过程可用下面的状态转移图表示：,考虑到 p0+ p1+ + pm=1， 解得,平均队长：Ls=m(1-p0)/ 平均排队长：Lq=Ls(1-p0) 顾客源中的顾客平均数：m-Ls 有效到达率（排队系统总的平均到达率）： e=(m-Ls)=(1-p0) 平均逗留时间: Ws= Ls /e 平均等待时间：Wq=Ws1/=Lq /e,系统的各项运行指标

13、计算如下：,例：某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间15分钟。有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求： （1）修理工空闲的概率； （2）5台机器都出故障的概率； （3）出故障机器的平均台数； （4）等待修理机器的平均台数； （5）平均停工时间； （6）平均等待修理时间； （7）评价这些结果。,解：,m=5， =50/15=4，=60/12=5，/=0.8,（1）修理工空闲的概率为 p0 = (5!/5!)0.80+ (5!/0!)0.85 -1 = 0.0073,（3）出故障机器的平均台数为 Ls = 5-(1-0.0073)/0.8

14、=3.76(台),（5）平均停工时间为 e = (1-p0) = 5(1-0.0073) = 4.9635 Ws= 3.76/4.9635=0.758(小时) 46(分钟),（6）平均等待修理时间为 Wq=46-12=34(分钟),（2） 5台机器都出故障的概率为 p5 = (5!/0!)0.85p0 = 0.287,（4）等待修理机器的平均台数为 Lq = 3.76-(1-0.0073) = 2.77(台),（7）评价这些结果:,第4节 多服务台负指数分布排队系统分析,4.1 标准M/M/c模型(M/M/c/),对于排队系统M/M/c/，规定c个服务台相互独立且平均服务率都为。设 ，其生灭过

15、程可用下面的状态转移图表示：,稳态概率方程如下：,解得稳态概率分布为：,系统的运行指标如下：,例 某售票窗处有三个窗口，顾客的到达服从泊松过程，平均到达率为=0.9（人/分），服务时间服从负指数分布，平均服务率为=0.4（人/分）。现设顾客到达后排成一队，依次向空闲的窗口购票，求： （1）整个售票处空闲的概率； （2）平均队长； （3）平均逗留时间； （4）平均排队等待时间； （5）顾客到达后必须等待的概率。,解：,c=3，/=2.25，=2.25/3=0.751,（3）平均逗留时间为 Ws= 3.95/0.9=4.39（分钟）,（4）平均排队等待时间为 Wq= 4.39-1/0.4=1.89

16、（分钟）,（1）整个售票处空闲的概率,（2）平均队长,（5）顾客到达后必须等待的概率,就前面的例子，如果顾客到达后在每个窗口前各排一队，且不准换队，整个系统就变成了3个M/M/1子系统，每个子系统的平均到达率均为0.9/3=0.3（人/分钟）。计算各项指标并与前面的计算结果比较如下：,4.2 M/M/c系统和c个M/M/1系统的比较,通过对比可以看出，单队比多队有显著的优越性，在安排排队方式时应该注意。,多服务台时，由于计算p0和各项指标的公式很复杂，可使用专门的Wq数值表计算各项指标。,上例中，c=3， /c=0.75。查表无此数，用线性插值法得,因=0.4，所以Wq=0.8129/0.4=2.03（分钟）,Ws=2.03+1/0.4=4.53（分钟）,因