[研究生入学考试]上海交大运筹学期末考试考研复习珍贵PPT资料适合全国高校考研和期末考试9排队论.ppt

运 筹 学 课 件,Queueing Theory,一般的排队过程为：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。排队过程的一般过程可用下图表示。我们所说的排队系统是指图中虚线所包括的部分。,在现实生活中的排队现象是多种多样的，对上面所说的“顾客”和“服务员”要作广泛的理解。它们可以是人，也可以是某种物质或设备。排队可以是有形的，也可以是无形的。,基本概念 排队过程的一般表示,排队系统的组成和特征,尽管排队系统是多种多样的，但从决定排队系统进程的因素来看，它有三个基本的组成部分，这就是输入过程、排队规则及服务机构。,1)输入过程：描述顾客来源以及顾客到达排队系统的规律。包括： 顾客源中顾客的数量是有限还是无限； 顾客到达的方式是单个到达还是成批到达； 顾客相继到达的间隔时间分布是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。,2)排队规则：描述顾客排队等待的队列和接受服务的次序。包括： 即时制还是等待制； 等待制下队列的情况（是单列还是多列，顾客能不能中途退出，多列时各列间的顾客能不能相互转移）； 等待制下顾客接受服务的次序（先到先服务，后到先服务，随机服务，有优先权的服务）。,3)服务机构：描述服务台(员)的机构形式和工作情况。包括： 服务台（员）的数目和排列情况； 服务台（员）的服务方式； 服务时间是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。,排队模型的分类,D.G.Kendall在1953年提出了一个分类方法，按照系统的三个最主要的、影响最大的三个特征要素进行分类，它们是：顾客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。按照这三个特征要素分类的排队系统，用符号（称为Kendall记号）表示为 X/Y/Z 其中X处填写顾客相继到达的间隔时间分布，Y处填写服务时间的分布，Z处填写并列的服务台个数。 例如M/M/1，表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、单服务台的模型。,后来，在1971年关于排队论符号标准化的会议上决定，将Kendall符号扩充为： X/Y/Z/A/B/C 其中前三项意义不变。 A处填写系统容量限制; B处填写顾客源中的顾客数目; C处填写服务规则（如先到先服务FCFS，后到先服务LCFS）。 约定，如略去后三项，即指X/Y/Z/FCFS的情形。 后面我们只讨论先到先服务FCFS的情形，所以略去第六项。,排队系统的求解,对于一个排队系统，运行状况的好坏既涉及到顾客的利益，又涉及到服务机构的利益，还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标，用以判断系统运行状况的优劣。下面介绍几种常用的指标。,1)队长：把系统中的顾客数称为队长，它的期望值记作Ls。而把系统中排队等待服务的顾客数称为排队长（队列长），它的期望值记作Lq。显然有 队长排队长正被服务的顾客数。,2)逗留时间：一个顾客从到达排队系统到服务完毕离去的总停留时间称为逗留时间，它的期望值记作Ws。 一个顾客在系统中排队等待的时间称为等待时间，它的期望值记作Wq。显然有 逗留时间等待时间服务时间。,3)瞬态和稳态 把系统中的顾客数称为系统的状态。考虑在t时刻系统的状态为n的概率，它是随时刻t而变化的，用Pn(t)表示，称为系统的瞬态。求瞬态解是很不容易的，一般即使求出也很难利用，因此我们常用它的极限 lim Pn(t)Pn t 称为稳态或称统计平衡状态的解。,统计平稳条件下的记号,n = 系统有n个顾客时的平均到达率（单位时间平均到达的顾客人数即是平均到达率） n = 系统有n个顾客时的平均离开率 = 对任何n都是常数的平均到达率. = 对任何n都是常数的平均离开率. 1/ = 期望到达间隔时间 1/ = 期望服务时间 = 服务强度， 或称使用因子, /(s),统计平稳条件下的记号,平均队长,平均等待队长,平均等待时间,平均逗留时间,Ls, Ws, Lq, Wq满足,所以，只需要求出Pn即可。,几个主要概率分布 一、POISSON分布,设N(t)表示在时间区间t0,t0+t)内到达的顾客数，是随机变量。当N(t)满足下列三个条件时，我们说顾客的到达符合Poisson分布。这三个条件是： (1)平稳性 在时间区间t0,t0+t)内到达的顾客数N(t)，只与区间长度t有关而与时间起点t0无关。 (2)无后效性 在时间区间t0,t0+t)内到达的顾客数N(t)，与t0以前到达的顾客数独立。 (3)普通性 在充分短的时间区间t内，到达两个或两个以上顾客的概率极小，可以忽略不计，即 Pn(t)o(t) n=2,在上述三个条件下可以推出 (t)n Pn(t) e-t n=0,1,2, n! 其中表示单位时间平均到达的顾客数，即为到达率。 不难算出，N(t)的数学期望和方差分别是： EN(t)t VarN(t)t,二、负指数分布,随机变量T的概率密度若是 e-t t0 fT(t) 0 t0 则称T服从负指数分布，它的分布函数是 1-e-t t0 FT(t) 0 t0 T的数学期望和方差分别为： ET1/， Var(T)1/2 负指数分布具有下列性质： (1)无记忆性或马尔柯夫性，即 PTt+s / TsPTt (2)当顾客到达符合Poisson分布时，顾客相继到达的间隔时间T必服从负指数分布。,对于Poisson分布，表示单位时间平均到达的顾客数，所以1/表示顾客相继到达的平均间隔时间，而这正和ET的意义相符。 服务时间符合负指数分布时，设它的概率密度函数和分布函数分别为 fv(t)e-t； Fv(t)1-e-t (t0) 其中表示单位时间能够服务完的顾客数，为服务率；而1/表示一个顾客的平均服务时间，正是v的期望值。,指数分布性质,密度函数,均值,方差,设随机变量 T,分布函数,性质1,fT(t) 是一个严格下降函数,性质2,无后效性,不管多长时间(t)已经过去， 逗留时间的概率分布与下一个事件的相同.,性质3,几个独立的指数分布的随机变量的最小有一个指数分布,几个独立的指数分布的随机变量的和还是一个指数分数的随机变量,性质4,指数分布,Poisson分布,服务时间的概率,在t时间内已经服务n个顾客的概率,排队系统的状态n随时间变化的过程称为生灭过程，设平均到达率为n,平均服务率为n,负指数分布排队系统（M/M/1/）的生灭过程可用下面的状态转移图表示：,稳态概率方程如下： 0P0=1P1 n-1Pn-1+n+1Pn+1=nPn+nPn,生灭过程,由前面的推导，可以求出另外的那些量的值。,最简单的排队系统的模型,最简单的排队系统：是指输入为最简单流，服务时间为负指数分布的排队服务系统,并且，此处我们假设：服务规则为：先到先服务；在多个服务站的情况，假设顾客排成一个单一的队伍。,假定： 1. 平均到达率为常数（对所有的n,有n = ） 2. 服务机构的平均服务率也是常数 单个服务站时，有n = ， 多个服务站时，若设S为并联的服务站个数，则有,3.,即服务机构总的服务效率应高于顾客的平均到达率,保证系统最终能进入稳定状态。,这样就可以把生灭过程的结论拿来用！,一、顾客源无限、队长不受限制的排队模型,稳态概率方程如下： P0=P1 Pn-1+Pn+1=Pn+Pn 设=/1，考虑到Pn=1，解得 P0=1- Pn=(1-) n , n1 这里的称为服务强度，也称话务强度，它刻划了服务机构的繁忙程度，所以又称服务机构的利用率。,此时的排队系统(M/M/1/）的生灭过程可用下面的状态转移图表示：,1、S1时，即M/M/1模型,服务系统的其他各项运行指标计算如下： 平均队长：,平均排队长：,平均逗留时间:,平均等待时间:,再计算（1）顾客在系统中停留时间超过t的概率？ 假定一个顾客来到系统时，系统中已有n个人，则该顾客在系统中的停留时间应该是系统对前n个顾客的服务时间加上对他的服务时间。 设T1，T2，Tn表示前n个顾客的服务时间，Tn+1表示对该顾客的服务时间。 令Sn+1=T1+T2+Tn+Tn+1,则,此时是爱尔朗分布,顾客在系统中停留时间小于t的概率（Ws平均逗留时间）,顾客在系统中停留时间超过t的概率,（2）已经有人等待的情况下还要等待多久？,M/M/1 举例,2、有S个并联服务站时，,因为此时有,所以,因为在多个服务站的情况下，,并令n-S=j,则有,平均排队长：,其他参数如：平均队长Ls，平均逗留时间Ws，平均等待时间Wq，都可以通过Little公式求出。,例：某厂有大量同一型号的车床，当该种车床损坏后或送机修车间或由机修车间派人来修理。已知该种车床损坏率服从泊松分布，平均每天2台。又机修车间对每台损坏车床的修理时间为负指数分布的随机变量，平均每台的修理时间为 天。但 是一个与机修人员编制及维修设备配备好坏（即与机修车间每年开支费用K）有关的函数。已知,又已知机器损坏后，每台每天的生产损失为400元，试决定使该厂生产最经济的K及,解：问题包含两个费用：机器损坏造成的生产损失S1机修车间的开支S2，要使整个系统最经济就是SS1S2最小。以下以一个月为期计算,S1正在修理和待修机器数每台每天的生产损失 每个月的工作日数,例：病人到达只有一个医生的医院门诊部的时间平均每20分钟一个，设对每个病人的诊治时间平均为15分钟，又知道以上两种时间均为负指数的概率分布。若该门诊部希望到达的病人90%以上能在候诊室找到座位，则该医院最少应该设置多少座位？,解：设候诊室有座位C个，再加上诊治中的病人的座位共有C1个。按照题目要求，该医院门诊部内病人总数不多于C1个的概率为0.90,即,二、顾客源无限、队长受限制的排队模型,当系统的容量有限制(为M)时，设顾客的平均到达率仍为常数，但由于系统中已有M个顾客时，新到的顾客将自动离去，所以有,1、 S1时,所以有,其他指标的计算： 先计算有效输入率,由于在队长受限的情况下，当达到顾客数n大于或等于M时，新来顾客会自动离去。因此虽然顾客以平均为的速度来到服务系统，但由于一部分的顾客离去，真正进入系统的的顾客的输入率是小于的。,由于系统中的平均排队的顾客数总是等于系统中的平均顾客数平均正在接受服务的顾客数，即：,对于队长受限制的排队模型，当系统中有M个顾客时，新到顾客会自动离开，故不一定要求,2、 S个并联服务站时,对于队长受限制的排队模型，当系统中有M个顾客时，新到顾客会自动离开，故当nM时， 和队长不受限时一样，但当 所以有,平均排队长：,由前面方法易求出其他结果。,当MS时，是一种特殊情况。因为这是一种带损失制的服务系统，此时，使用前面给出的公式，且令M=S，即可得到如下结果：,例：某单位电话交换台有一台200门内线的总机。已知在上班的8小时内。有20%的内线分机平均每40分钟要一次外线电话，80%的分机平均每2小时要一次外线电话，又知从外单位打来的电话呼叫率平均每分钟一次，设外线通话时间平均为3分钟，以上两个时间均属于负指数分布。如果要求电话接通率95%,问该交换台应设置多少外线？,解：来到电话交换台的的呼唤有2类：1，各分机往外打的电话；2，从外单位打进来的电话。,第1类：,第2类：,由possion分布性质，到交换台的总呼唤流仍是possion分布：,这是一个具有多个服务站带损失制的服务系统，要使电话接通率为95%，即损失低于5%，所以,将已知数值带入后，得出应不少于15条。,注：计算中没有考虑全面的因素：如外单位打来时内线是否占用，打不通时会不停拨打等，会使得实际的电话接通率达不到95%。,M/M/1/N/ 举例,三、顾客源有限的排队模型,设系统的顾客总数为有限(为N)，当有n个顾客在服务系统内时，在服务系统外的潜在顾客数就减少为（N-n）。若设每个顾客来到服务系统的时间间隔为参数的负指数分布的话，则根据负指数分布的性质有n=(N-n) ，因此此排队模型可用生灭过程的发生率图表示如下：,S1时,S1时,由上图中知道，S1时，有,S1时，有,由于当n=N时， n=0,所以系统最终一定能达到稳定状态，所以可用求解稳定状态的方法进行处理。,S1时,由于顾客输入率n随系统状态而变化，因此平均输入率可按照下式计算：,且有,S1时，,例：设有一名工人负责照管6台自动机床。当机床需要加料、发生故障或刀具磨损时就自动停车，等待工人照管。设平均每台机床两次停车的时间间隔为1小时，又设每台机床停车时，需要工人平均照管的时间为0.1小时。以上两项时间均服从负指数分布，试计算该系统的各项指标。 解：,数据见下表,所以，系统中平均等待照管的机床数为：,系统中