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

一般的排队过程为：顾客由顾客源出发，到达服务机构一般的排队过程为：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接受服务，服务（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。排队机构按服务规则给顾客服务，顾客接受完服务后就离开。排队过程的一般过程的一般过程过程可用下图表示。我们所说的排队系统是指图中可用下图表示。我们所说的排队系统是指图中虚线所包括的部分虚线所包括的部分。在现实生活中的排队现象是多种多样的，对上面所在现实生活中的排队现象是多种多样的，对上面所说的说的“顾客顾客”和和“服务员服务员”要作广泛的理解。它们可以要作广泛的理解。它们可以是人，也可以是某种物质或设备。排队可以是有形的，是人，也可以是某种物质或设备。排队可以是有形的，也可以是无形的。也可以是无形的。基本概念基本概念 排队过程的一般表示排队过程的一般表示排队系统的组成和特征排队系统的组成和特征 尽管排队系统是多种多样的，但从决定排队系统进尽管排队系统是多种多样的，但从决定排队系统进程的因素来看，它有三个基本的组成部分，这就是程的因素来看，它有三个基本的组成部分，这就是输入输入过程、过程、排队规则排队规则及及服务机构服务机构。1)1)输入过程：描述顾客来源以及顾客到达排队系统的规输入过程：描述顾客来源以及顾客到达排队系统的规律。包括：律。包括：顾客源中顾客的数量是有限还是无限；顾客源中顾客的数量是有限还是无限；顾客到达的方式是单个到达还是成批到达；顾客到达的方式是单个到达还是成批到达；顾客相继到达的间隔时间分布是确定型的还是随机顾客相继到达的间隔时间分布是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。型的，分布参数是什么，是否独立，是否平稳。2)2)排队规则：排队规则：描述顾客排队等待的队列和接受服务的次描述顾客排队等待的队列和接受服务的次序。包括：序。包括：即时制还是等待制；即时制还是等待制；等待制下队列的等待制下队列的情况（情况（是单列还是多列，顾客能不是单列还是多列，顾客能不能中途退出，多列时各列间的顾客能不能相互转移）；能中途退出，多列时各列间的顾客能不能相互转移）；等待制下顾客接受服务的次序（先到先服务，后到等待制下顾客接受服务的次序（先到先服务，后到先服务，随机服务，有优先权的服务）。先服务，随机服务，有优先权的服务）。3)3)服务机构：描述服务台服务机构：描述服务台(员员)的机构形式和工作情况。的机构形式和工作情况。包括：包括：服务台（员）的数目和排列情况；服务台（员）的数目和排列情况；服务台（员）的服务方式；服务台（员）的服务方式；服务时间是确定型的还是随机型的，分布参数是什服务时间是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。么，是否独立，是否平稳。排队模型的分类排队模型的分类 D.G.KendallD.G.Kendall在在19531953年提出了一个分类方法，按照系年提出了一个分类方法，按照系统的三个最主要的、影响最大的三个特征要素进行分类，统的三个最主要的、影响最大的三个特征要素进行分类，它们是：顾客相继到达的间隔时间分布、服务时间的分它们是：顾客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。按照这三个特征要素分类的排布、并列的服务台个数。按照这三个特征要素分类的排队系统，用符号（称为队系统，用符号（称为KendallKendall记号）表示为记号）表示为 X/Y/ZX/Y/Z其中其中X X处填写顾客相继到达的间隔时间分布，处填写顾客相继到达的间隔时间分布，Y Y处填写服处填写服务时间的分布，务时间的分布，Z Z处填写并列的服务台个数。处填写并列的服务台个数。例如例如M/M/1M/M/1，表示顾客相继到达的间隔时间为负指表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、单服务台的模型。数分布、服务时间为负指数分布、单服务台的模型。后来，在后来，在19711971年关于排队论符号标准化的会议上年关于排队论符号标准化的会议上决定，将决定，将KendallKendall符号扩充为：符号扩充为：X/Y/Z/A/B/CX/Y/Z/A/B/C 其中前三项意义不变其中前三项意义不变。A A处填写系统容量限制处填写系统容量限制;B B处填写顾客源中的顾客数目处填写顾客源中的顾客数目;C C处填写服务规则（如先到先服务处填写服务规则（如先到先服务FCFSFCFS，后到先服后到先服务务LCFSLCFS）。）。约定，如略去后三项，即指约定，如略去后三项，即指X/Y/Z/FCFSX/Y/Z/FCFS的的情形。情形。后面我们只讨论先到先服务后面我们只讨论先到先服务FCFSFCFS的情形，所以略的情形，所以略去第六项去第六项。排队系统的求解排队系统的求解 对于一个排队系统，运行状况的好坏既涉及到顾客对于一个排队系统，运行状况的好坏既涉及到顾客的利益，又涉及到服务机构的利益，还有社会效果好的利益，又涉及到服务机构的利益，还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标，质量、研究设计改进措施，必须确定一些基本指标，用以判断系统运行状况的优劣。下面介绍几种常用的用以判断系统运行状况的优劣。下面介绍几种常用的指标。指标。1)1)队长：把系统中的顾客数称为队长：把系统中的顾客数称为队长队长，它的期望值记，它的期望值记作作LsLs。而把系统中排队等待服务的顾客数称为而把系统中排队等待服务的顾客数称为排队长排队长（队列长）（队列长），它的期望值记作，它的期望值记作LqLq。显然显然有有 队长排队长正被服务的顾客数。队长排队长正被服务的顾客数。2)2)逗留时间：逗留时间：一个一个顾客从到达排队系统到服务完顾客从到达排队系统到服务完毕离去的总停留时间称为毕离去的总停留时间称为逗留时间逗留时间，它的期望值记作，它的期望值记作WsWs。一个一个顾客在系统中排队等待的时间称为顾客在系统中排队等待的时间称为等待时等待时间间，它的期望值记作，它的期望值记作WqWq。显然显然有有 逗留时间等待时间服务时间。逗留时间等待时间服务时间。3)3)瞬态和稳态瞬态和稳态 把系统中的顾客数称为系统的把系统中的顾客数称为系统的状态状态。考虑在考虑在t t时刻时刻系统的状态为系统的状态为n n的概率，它是随时刻的概率，它是随时刻t t而变化的，用而变化的，用P Pn n(t)(t)表示，称为系统的表示，称为系统的瞬态瞬态。求瞬态解是很不容易的，。求瞬态解是很不容易的，一般即使求出也很难利用，因此我们常用它的极限一般即使求出也很难利用，因此我们常用它的极限 lim Plim Pn n(t)(t)P Pn n t t称为称为稳态或称统计平衡状态的解稳态或称统计平衡状态的解。统计平稳条件下的记号统计平稳条件下的记号 n =系统有系统有n个顾客时的平均到达率（单个顾客时的平均到达率（单位时间平均到达的顾客人数即是平均到达率）位时间平均到达的顾客人数即是平均到达率）n =系统有系统有n个顾客时的平均离开率个顾客时的平均离开率 =对任何对任何n都是常数的平均到达率都是常数的平均到达率.m =对任何对任何n都是常数的平均都是常数的平均离开率率.1/=期望到达间隔时间期望到达间隔时间1/=期望服务时间期望服务时间 =服务强度，服务强度，或称使用因子或称使用因子,/(s)统计平稳条件下的记号统计平稳条件下的记号平均队长平均队长平均等待队长平均等待队长平均等待时间平均等待时间平均逗留时间平均逗留时间Ls,Ws,Lq,Wq满足满足公式公式Little 所以，只需要求出所以，只需要求出Pn即可。即可。几个主要概率分布几个主要概率分布一、一、POISSON分布分布 设设N(t)N(t)表示在时间区间表示在时间区间 t t0,t,t0+t)+t)内到达的顾客数，是随机变内到达的顾客数，是随机变量。当量。当N(t)N(t)满足下列三个条件时，我们说顾客的到达符合满足下列三个条件时，我们说顾客的到达符合PoissonPoisson分布。这三个条件是：分布。这三个条件是：(1)(1)平稳性平稳性 在时间区间在时间区间 t t0,t,t0+t)+t)内到达的顾客数内到达的顾客数N(t)N(t)，只只与区间长度与区间长度t t有关而与时间起点有关而与时间起点t t0无关。无关。(2)(2)无后效性无后效性 在时间区间在时间区间 t t0,t,t0+t)+t)内到达的顾客数内到达的顾客数N(t)N(t)，与与t t0以前到达的顾客数独立。以前到达的顾客数独立。(3)(3)普通性普通性 在充分短的时间区间在充分短的时间区间t t内，到达两个或两个内，到达两个或两个以上顾客的概率极小，可以忽略不计，即以上顾客的概率极小，可以忽略不计，即 P Pn(t)t)o(o(t)t)n=2 在上述三个条件下可以推出在上述三个条件下可以推出 (t)t)n P Pn(t)(t)e e-t n=0,1,2,n=0,1,2,n!n!其中其中表示单位时间平均到达的顾客数，表示单位时间平均到达的顾客数，即即为到为到达率。达率。不难算出，不难算出，N(t)N(t)的数学期望和方差分别是：的数学期望和方差分别是：EN(t)EN(t)t t VarN(t)VarN(t)t t二、负指数分布二、负指数分布 随机变量随机变量T T的概率密度若是的概率密度若是 e e-t t0 t0 f fT(t)(t)0 t 0 t 0 0则称则称T T服从负指数分布，它的分布函数是服从负指数分布，它的分布函数是 1-1-e e-t t0 t0 F FT(t)(t)0 t 0 t 0 0 T T的数学期望和方差分别为：的数学期望和方差分别为：ETET1/1/，Var(T)Var(T)1/1/2 负指数分布具有下列性质：负指数分布具有下列性质：(1)(1)无记忆性或马尔柯夫性，即无记忆性或马尔柯夫性，即 PTt+s/TsPTt+s/TsPTtPTt (2)(2)当顾客到达符合当顾客到达符合PoissonPoisson分布时，分布时，顾客相继到达的顾客相继到达的间隔时间间隔时间T T必服从负指数分布。必服从负指数分布。对于对于PoissonPoisson分布，分布，表示单位时间平均到达的表示单位时间平均到达的顾客数，所以顾客数，所以1/1/表示顾客相继到达的平均间隔时表示顾客相继到达的平均间隔时间，而这正和间，而这正和ETET的意义相符。的意义相符。服务时间服务时间符合负指数分布时，设它的概率密度符合负指数分布时，设它的概率密度函数和分布函数分别为函数和分布函数分别为 f fv(t)(t)e e-t；F Fv(t)(t)1-e1-e-t (t0)(t0)其中其中表示单位时间能够服务完的顾客数，为服务表示单位时间能够服务完的顾客数，为服务率；而率；而1/1/表示一个顾客的平均服务时间，正是表示一个顾客的平均服务时间，正是v v的期望值。的期望值。指数分布性质指数分布性质密度函数密度函数均值均值方差方差设随机变量设随机变量 T分布函数分布函数 fT(t)t性质性质1 fT(t)t ttfT(t)是一个严格下降函数是一个严格下降函数性质性质2无后效性无后效性不管多长时间不管多长时间(t)已经过去，已经过去，逗留时间的概率分布与下逗留时间的概率分布与下一个事件的相同一个事件的相同.性质性质3几个独立的指数分布的随几个独立的指数分布的随机变量的最小有一个指数机变量的最小有一个指数分布分布几个独立的指数分布的随机几个独立的指数分布的随机变量的和还是一个指数分数变量的和还是一个指数分数的随机变量的随机变量T(1+2+3)T1(1)T1(2)T1(3)min性质性质4指数分布指数分布Poisson分布分布 服务时间的概率服务时间的概率在在t时间内已经服务时间内已经服务n个顾个顾客的概率客的概率1/:平均服务时平均服务时间间平均服务率平均服务率=排队系统的状态排队系统的状态n随时间变化的过程称为随时间变化的过程称为生灭过程生灭过程，设平均到达率为设平均到达率为n,平均服务率为平均服务率为n,负指数分布排队系统负指数分布排队系统（M/M/1/）的生灭过程可用下面的状态转移图表示：）的生灭过程可用下面的状态转移图表示：稳态概率方程如下：稳态概率方程如下：0P0=1P1 n-1Pn-1+n+1Pn+1=nPn+nPn01 n-1n n+1.0 1 n-2 n-1 n 1 2 n-1 n n+1 .生灭过程生灭过程由前面的推导，可以求出另外的那些量的值。由前面的推导，可以求出另外的那些量的值。最简单的排队系统的模型最简单的排队系统的模型最简单的排队系统：是指输入为最简单流，服务时间最简单的排队系统：是指输入为最简单流，服务时间为负指数分布的排队服务系统为负指数分布的排队服务系统并且，此处我们假设：服务规则为：先到先服务；在并且，此处我们假设：服务规则为：先到先服务；在多个服务站的情况，假设顾客排成一个单一的队伍。多个服务站的情况，假设顾客排成一个单一的队伍。假定：假定：1.平均到达率为常数平均到达率为常数（对所有的（对所有的n,有有n=）2.服务机构的平均服务率也是常数服务机构的平均服务率也是常数单个服务站时，有单个服务站时，有n=，多个服务站时，若设多个服务站时，若设S为并联的服务站个数，则有为并联的服务站个数，则有 3.即服务机构总的服务效率应高于顾客的平均到达率即服务机构总的服务效率应高于顾客的平均到达率 保证系统最终能进入稳定状态。保证系统最终能进入稳定状态。这样就可以把生灭过程的结论拿来用！这样就可以把生灭过程的结论拿来用！一、顾客源无限、队长不受限制的排队模型一、顾客源无限、队长不受限制的排队模型01 n-1n n+1.稳态概率方程如下：稳态概率方程如下：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个顾客个顾客时，新到顾客会自动离开，故时，新到顾客会自动离开，故当当nMn1时时01 S+1 N (N-1)(N-S+1)(N-S)2 S S S.N N-1.S S-1 由上图中知道，由上图中知道，S1时，有时，有 S1时，有时，有 由于当由于当n=N时，时，n=0,n=0,所以系统最终一定能达到稳定状所以系统最终一定能达到稳定状态，所以可用求解稳定状态的方法进行处理。态，所以可用求解稳定状态的方法进行处理。S1时时 由于顾客输入率由于顾客输入率n随系统状态而变化，因此平均随系统状态而变化，因此平均输入率可按照下式计算：输入率可按照下式计算：且有且有 S1时，时，例：设有一名工人负责照管例：设有一名工人负责照管6台自动机床。当机床需台自动机床。当机床需要加料、发生故障或刀具磨损时就自动停车，等待要加料、发生故障或刀具磨损时就自动停车，等待工人照管。设平均每台机床两次停车的时间间隔为工人照管。设平均每台机床两次停车的时间间隔为1小时，又设每台机床停车时，需要工人平均照管的小时，又设每台机床停车时，需要工人平均照管的时间为时间为0.1小时。以上两项时间均服从负指数分布，小时。以上两项时间均服从负指数分布，试计算该系统的各项指标。试计算该系统的各项指标。解：解：数据见下表数据见下表n等待照管的等待照管的机床数机床数n-1Pn/P0Pn(n-1)PnnPn0010.484500100.60.290700.2907210.30.14540.14540.2908320.120.05820.11640.1746430.0360.01750.05250.07540.00720.00350.01400.0175650.000720.00030.00150.0018所以，系统中平均等待照管的机床数为：所以，系统中平均等待照管的机床数为：系统中停车的机床数为：系统中停车的机床数为：例：上例中改为由三个工人联合看管例：上例中改为由三个工人联合看管20台自动机床，台自动机床，其他各项数据不变，试计算该系统的各项指标。其他各项数据不变，试计算该系统的各项指标。数据见下表（其中数据见下表（其中n12时，时，Pn较小可忽略不计）较小可忽略不计）解解n正照管正照管机床数机床数等待照管等待照管机床数机床数空闲的空闲的工人数工人数Pn/P0Pn(n-S)PnnPn000310.13626110220.272500.2725022011.90.258880.5177633001.140.155330.4659943100.6460.088020.088020.3520853200.34450.046940.093880.2347063300.17220.023470.070410.1408273400.08040.010950.043800.0766583500.03480.004750.023750.038893600.01390.00190.011400.0171103700.00510.00070.004900.007113800.00170.000230.001840.00253123900.00050.000070.000630.00084所以，系统中平均等待照管的机床数为：所以，系统中平均等待照管的机床数为：系统中停车的机床数为：系统中停车的机床数为：其他模型其他模型nM/M/c/K/Kn顾客来源是有限的服务系统顾客来源是有限的服务系统.例如：例如：一个饭店有一个饭店有 X 张桌子和张桌子和 Y个服务生服务来源有限的顾客个服务生服务来源有限的顾客.nM/D/1n服务时间不变的服务系统服务时间不变的服务系统.nD/M/1n确定性到达模式确定性到达模式,及指数分布服务时间及指数分布服务时间.例如：医生赴约治病的例如：医生赴约治病的时间表时间表.nM/E k/1n服务服从服务服从 Erlang 分布分布.例如：用相同平均时间去完成一些程例如：用相同平均时间去完成一些程序。序。