第九章 排队论1

排队论课件1•1909年•丹麦电话工程师A.K.埃尔朗：话务理论，导出著名的埃尔朗电话损失率公式。自20世纪初以来，电话系统的设计一直在应用这个公式。•20世纪30年代•苏联数学家А.Я.欣钦把处于统计平衡的电话呼叫流称为最简单流。•瑞典数学家巴尔姆又引入有限后效流等概念和定义。•20世纪50年代初•美国数学家关于生灭过程的研究•英国数学家D.G.肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法。•L.塔卡奇等人又将组合方法引进排队论，使它更能适应各种类型的排队问题。20世纪70年代以来人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势排队论课件2第九章排队论第一节排队系统的基本概念第二节M/M/1排队模型第三节M/M/C排队模型第四节其它类型的排队模型第五节排队系统的优化应用排队论课件3•1、需求——顾客•2、服务——服务机构第一节基本概念一、排队系统组成排队可以是有形的，也可以是无形的。顾客源排队服务机构顾客到来排队规则服务规则顾客离去排队系统排队论课件4如果服务设施过少或服务效率太低，便会加剧拥挤，排队成龙。但增加服务设施便会增加服务成本或造成系统空闲，而有些服务设施如机场、港口泊位等一旦建成就不易改动。因此，有必要对排队系统的结构和运行规律加以研究，为排队系统的设计和调控提供依据。现实世界中形形色色的排队系统排队论课件5排队系统的三个基本组成部分.•输入过程arrivalprocess(顾客按照怎样的规律到达);•排队规则queuingdiscipline(顾客按照一定规则排队等待服务);•服务机构Serviceagencies(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)顾客源排队服务机构顾客到来排队规则服务规则顾客离去3.顾客是怎样接受服务2.顾客是怎样排队的1.顾客是怎样到达的排队论课件61、输入过程•顾客来源的总体数或顾客源数–有限m(如车间里待修理的机器)–无限∞(如电话呼唤)•顾客到达的类型–单个–成批•顾客相继到达的时间间隔分布.–顾客到达间隔时间:顾客相继到达的间隔时间分布是确定型的、还是随机型的，分布参数是什么，是否独立，是否平稳服从某一概率分布(定长分布D，负指数分布)输入过程：描述顾客来源以及顾客到达排队系统的规律。包括：排队论课件72、排队规则（顾客接受服务的先后次序）（1）损失制：指顾客到达时若所有服务设施均被占用，则顾客自动离去。（损失很多顾客）（2）等待制：顾客到达后，加入排队系统接受服务•先来先服务（FCFS，firstcome，firstservice）；•后来先服务（LCFS，lastcome，firstservice）；•随机服务（SIRO，serviceinrandomorder）；•有优先权的服务（PS，priorityservice）。（3）混合制:排队规则既允许排队又不允许队列无限长系统容量有限制等待时间有限制排队论课件8服务机构：描述服务台(员)的机构形式和工作情况。包括：服务台个数C=服务时间分布：服务时间是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。（指数,常数,k级Erlang)3、服务机构（服务台）11并行多台排队论课件9D.G.Kendall在1953年提出按照排队系统的三个最主要的、影响最大的特征要素进行分类：顾客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。用符号（称为Kendall记号）表示为X/Y/Z/A/B/CX：顾客相继到达的间隔时间分布，Y：服务时间的分布，Z：并列的服务台个数。A：系统容量限制，B：顾客源中的顾客数目;C：服务规则（如先到先服务FCFS，后到先服务LCFS）。如略去后三项，即指X/Y/Z/∞/∞/FCFS的情形。例如M/M/1，表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、单服务台的模型。二、排队系统的符号表示排队论课件10二、排队系统的符号表示ServerQueueArrivalX/Y/Z/A/B/C顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则(Kendall记号)M/M/1///FCFS（简记为M/M/1）M/M/C/N//FCFS，GI/M/1/M:负指数分布(兼指泊松输入)D:定长分布(常数时间)Er:Erlang分布GI:一般相互独立的时间间隔的分布（generalindependent）G:一般服务时间的概率分布(任意概率分布)排队论课件11思考题指出下面符号表示的含义•M/M/1/∞/m•G/D/C/N•GI/Er/1/1•M/M/C/N/mM:负指数分布(兼指泊松输入)D:定长分布(常数时间)Er:Erlang分布GI:一般相互独立的时间间隔的分布（generalindependent）G:一般服务时间的概率分布(任意概率分布)排队论课件12三、排队系统的主要数量指标及参数一）主要指标对于一个排队系统，运行状况的好坏既涉及到顾客的利益，又涉及到服务机构的利益，还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标，用以判断系统运行状况的优劣，常用的指标：1)队长：把系统中的顾客数称为队长，它的期望值记作L。而把系统中排队等待服务的顾客数称为排队长（队列长），它的期望值记作Lq。队长＝排队长＋正被服务的顾客数。排队论课件132)逗留时间：一个顾客从到达排队系统到服务完毕离去的总停留时间称为逗留时间，它的期望值记作W。一个顾客在系统中排队等待的时间称为等待时间，它的期望值记作Wq。显然有逗留时间＝等待时间＋服务时间。3)瞬态和稳态把系统中的顾客数称为系统的状态。考虑在t时刻系统的状态为n的概率，它是随时刻t而变化的，用Pn(t)表示，称为系统的瞬态。求瞬态解是很不容易的，一般即使求出也很难利用，因此我们常用它的极限limPn(t)＝Pnt→∞称为稳态或称统计平衡状态的解。排队论课件14（二）主要参数在处理实际排队系统时，需要把有关的原始资料进行统计，确定顾客到达间隔和服务时间的经验分布，然后按照统计学的方法确定符合哪种理论分布。经验分布的主要指标如下：总时间平均间隔时间=到达顾客总数服务时间总和平均服务时间=顾客总数到达顾客总数平均到达率=总时间顾客总数平均服务率=服务时间总和排队论课件15（二）主要参数顾客到达系统的平均速度，1/顾客到达系统间隔时间的平均值.系统中服务台的平均服务速度，1/服务台对每一顾客的平均服务时间排队论课件16例1：单人理发馆排队问题有6个椅子接待人们排队，超过6人顾客就离开，平均每小时到达3人，理发需时平均15分钟。求系统中的最大顾客数、平均到达率、平均服务率。解：Ｎ＝7为系统中的最大顾客数。平均到达率＝3人/小时，平均服务率＝4人/小时。例2：某服务机构是单服务台，先到先服务，有41个顾客，第1个顾客到达时刻为0，第41个顾客在第142分钟时到达，全部服务时间为127分钟。求平均间隔时间、平均到达率、平均服务时间、平均服务率。平均间隔时间=142/41=3.46(分钟/人)平均到达率=41/142=0.288(人/分钟)平均服务时间=127/41=3.12(分钟/人)平均服务率=41/127=0.32(人/分钟)排队论课件17设N(t)表示在时间区间[t0,t0+t)内到达的顾客数,是随机变量。当N(t)满足(1)平稳性，(2)无后效性，(3)普通性，顾客的到达符合泊松分布。在t时间内有n个顾客到达的概率1、泊松分布Poissondistribution(λt)nPn(t)＝———e-λtn=0,1,2,……n!其中λ表示单位时间平均到达的顾客数，即到达率。N(t)的数学期望和方差分别是：E[N(t)]＝λtVar[N(t)]＝λt四排队论中常见的几种概率分布排队论课件181)、平稳性顾客到达是均匀的在时间区间[t0,t0+t)内到达的顾客数N(t)，即N个顾客到达的概率仅与区间长度t有关,而与这段时间的起始时刻无关。2)、无后效性任一时段的到达数不受前一时段的影响在时间区间[t0,t0+t)内到达的顾客数N(t)，与t0以前到达的顾客数独立，即与时刻t0以前时间所发生的概率无关。3)、普通性（稀有性瞬时内只可能有1个顾客到达在充分短的时间区间Δt内，即在某一瞬间同时到达两个或两个以上顾客的概率极小，即∞∑Pn(Δt)＝o(Δt)n=2例：餐厅就餐，柜台购物，急诊抢救。排队论课件192、负指数分布negativeexponentialdistribution随机变量T服从负指数分布，它的概率密度和分布函数若是λe-λtt≥0fT(t)＝0t01-e-λtt≥0FT(t)＝0t0T的数学期望和方差分别为：E[T]＝1/λ，Var(T)＝1/λ21）当顾客到达符合泊松分布时，顾客相继到达的间隔时间T必服从负指数分布。对于泊松分布，λ表示单位时间平均到达的顾客数（平均到达率），所以1/λ表示顾客相继到达的平均间隔时间，而这正和E[T]的意义相符。2）服务时间常用的概率分布为负指数分布时，设它的概率密度函数和分布函数分别为fv(t)＝μe-μt；Fv(t)＝1-e-μt(t≥0)其中μ表示单位时间能够服务完的顾客数，为服务率；而1/μ表示一个顾客的平均服务时间，正是v的期望值。fT(t)t1)(TE排队论课件203、定长分布（deterministicdistribution）顾客相继到达时间间隔或每个顾客接受服务的时间是一个确定的常数4、K阶爱尔朗分布（Erlangdistribution）k个串联服务台，每个服务台的服务时间相互独立，且服从平均服务时间均为1/k的负指数分布，则该顾客走完这k个服务台所需时间t的概率密度。K=1时，Ｅ１分布就是负指数分布，ｋ大于等于３０时，ＥＫ分布近似正态分布排队论课件215、指数分布与泊松分布的关系指数分布0fort00)(tforetftT1)(TE!)())((netntXPtnPoisson分布ttXE))((到达间隔时间的概率=t在t时间内到达n个顾客的概率1/:平均服务时间平均服务率=排队论课件22排队分布的检验表9-1患者在单位时间内到达数的频数分布【例３】某医院外科手术室任意抽查了100个工作小时，每小时患者到达数的出现次数如表9-1，问每小时患者的到达数是否服从泊松分布。到达数n0123456≥7出现次数f1028291610610排队论课件23【例３】求解解：依题意，患者平均到达率（人/小时）。现检验这个经验分布是否适合=2.1的泊松分布，利用2检验法计算统计量，结果如表。2.1100nnfX05.0,488.93026.124,05.02P所以可认为患者到达数的分布服从=2.1的泊松分布。返回首页排队论课件24思考题：单级决策－有一个决策点的决策例：某项目工程,施工管理人员要决定下个月是否开工。若开工后遇天气不下雨，则可按期完工，获利润5万元；遇天气下雨，则要造成1万元的损失；假如不开工，不论下雨还是不下雨都要付窝工费1000元。据气象预测下月天气不下雨的概率为0.2，下雨概率为0.8。施工管理人员如何作出决策？排队论课件252概率分枝可能结果点3自然状态点画图计算-1000下雨P1=0.8－10000123不下雨P2＝0.22000-1000P1＝0.8P2＝0.250000-1000淘汰决策点1