运筹学排队论课件

62338357(O)[e-mail]运筹学千里之外决胜帷幄之中运筹主讲教师赵玉英北京林业大学理学院排队常常是件很令人恼火的事情……尤其是在我们这样的人口大国第八章排队论基础理论基础：数理统计和随机过程排队论(queuingtheory)研究内容：由于随机因素的影响而产生的拥挤现象，也称为随机服务系统理论。排队论是研究排队服务系统的数学理论和方法。第8章排队论基础随机服务系统概论无限源的排队系统起源和发展生活中的排队现象随机服务系统的基本组成部分几个常用的概率分布和最简单流排队系统的符号表示（模型分类）§8.1随机服务系统概论1起源和发展起源：1909年丹麦的数学家电话工程师爱尔朗（Erlang）用随机过程理论研究电话网中的排队问题。发展：二战后，开始了对机器管理、陆空交通等方面的研究，1951年以后，理论工作有了新的进展，逐渐奠定了排队论（现代随机服务系统）的理论基础。上世纪七十年代，排队论开始应用于计算机系统和计算机网络领域。2生活中的排队现象生活中排队现象：购买物品，看病，上车，….广义的排队现象：电话的占线，等待装船的货物，等待加工的原料，等待修理的出故障的机器…..一般而言，如果要求服务的对象的数量超过了服务机构的数量便产生排队现象。“顾客”(client)：得到服务的对象“服务台”(server)：给与服务的系统顾客与服务台就构成了一个排队系统。2生活中的排队现象3随机服务系统的基本组成部分输入（顾客到达服务系统的规律）排队规则（顾客按怎样的规则排队等待服务）服务机构（服务机构的设置,服务台的数量,服务的方式,服务时间的分布等）这是排队系统的三个基本组成部分。顾客源顾客到达服务台离去排队服务系统3随机服务系统的基本组成部分(1)到达时间间隔确定的随机的到达人数情况单个到达成批到达顾客源总数无限有限输入3随机服务系统的基本组成部分(2)排队规则1。损失制：当顾客到达时，若所有服务设施均被占用，则自动离去。2。等待制：顾客到达时，若所有服务设施均被占用，就留下来等待服务，一直到服务完毕才离去。先到先服务（FCFS）后到先服务（LCFS）带优先权的服务（PR）随机服务（SIRO）3随机服务系统的基本组成部分(2)队长有限：系统中等待的空间有限。等待时间有限：顾客在系统中等待的时间不超过某一个给定的长度。逗留时间:（等待时间与服务时间之和）有限。3。混合制：损失制和等待制的结合，允许排队，但不允许队列无限长下去。3随机服务系统的基本组成部分(3)服务机构服务设施的数量连接方式服务方式单台多台串联并联混联单个成批4几个常用的概率分布和最简单流–顾客到达时间间隔:nT：第n个顾客到达的时刻；设nTTT100：第n个顾客与第n-1个顾客到达的时间间隔；nX,,2,1,1nTTXnnn令1T2TnT1nT1nT0TnX–服务时间:4几个常用的概率分布和最简单流（1）定长分布（D）：1)(aPatattPtF,1,0)()(aE)(（2）负指数分布（M）：4几个常用的概率分布和最简单流0,00,)(ttetft0,00,1)(ttetFt/1)(E2/1)(D负指数分布是在排队理论使用的最多的一种分布，常用来表示各种寿命的分布，它具有无记忆性，即:无论现在多大年龄，剩余寿命的分布不受已有年龄的影响。4几个常用的概率分布和最简单流(1)假定是独立同分布，分布函数为，排队论中常用的有两种：}{nX)(tF（1）定长分布（D）：顾客到达时间间隔为确定的。–顾客到达时间间隔分布:（2）最简单流（即Poisson流）（M）：顾客到达时间间隔为独立的，服从同一负指数分布，多个顾客随机出现组成的序列称为排队中常用最简单流。}{nX最简单流（即Poisson流）（M）特点：在某个时段内，到达的顾客数量只和时间长度有关，而和时间的起点无关（平稳性）。在某个时段内，到达的顾客数量和这个时间段之前到达的顾客数量无关（无后效性）。在充分小的时间区间内，到达两个或者两个以上的顾客的概率是时间长度的高阶无穷小（普通性）。4几个常用的概率分布和最简单流(1),2,1,0,!)()(kekttPtkk4几个常用的概率分布和最简单流(1)一般地，大量的稀有事件流，如果每一事件流在总事件流中起的作用很小，而且相互独立，则总的合成流可以认为是最简单流。1/λ——顾客的平均到达时间间隔λ——单位时间内平均到达的顾客数4几个常用的概率分布和最简单流(2)–服务时间分布:设某服务台的服务时间为V，其密度函数为f(t)，常见的分布有：（1）定长分布（D）：每个顾客接受服务的时间是一个确定的常数。（2）负指数分布（M）：每个顾客接受服务时间相互独立，具有相互独立的负指数分布：其中，为一常数。000)(ttetft01/μ——每个顾客的平均服务时间μ——单位时间平均服务完成的顾客数排队系统通常用下述符号形式表示：？/？/？/？其中：第一个符号表示顾客到达时间间隔的分布；第二个符号表示服务时间分布；第三个符号表示服务台数目；第四个符号表示服务系统允许的最大顾客容量。注：1971年，排队论的标准符号被规定为：？/？/？/？/？/？第五个表示顾客源数目，第六个表示服务规则5排队系统的符号表示（模型分类）M/M/1/∞系统：顾客到达时间间隔和服务时间服从负指数分布；服务台数目为1；系统的顾客容量没有限制；M/M/1/k系统：顾客到达时间间隔和服务时间服从负指数分布；服务台数目为1；系统的顾客容量为k；5排队系统的符号表示（模型分类）M/M/c/∞系统?M/M/c/k系统?已知:顾客到达间隔时间分布,服务时间分布.求:队长:L--系统中的顾客数.排队长(队列长):Lq--队列中的顾客数.L=Lq+正在接受服务的顾客数逗留时间:W--顾客在系统中的停留时间等待时间:Wq--顾客在队列中的等待时间.W=Wq+服务时间忙期,损失率,服务强度6评价排队问题的指标§8.2无限源的排队系统M/M/1/∞系统M/M/1/k系统1M/M/1/∞系统顾客源排队系统排队结构服务台排队规则服务规则接受服务后离去无限输入过程服从参数为的最简单流单队队长无限先到先服务服务时间服从参数为的负指数分布1M/M/1/∞系统生灭过程：设有某个系统，具有状态集S={0,1,2,…}，若系统的状态随时间t变化的过程{N(t):t=0}满足以下条件，则称为一个生灭过程。设在时刻t系统处于状态n的条件下，再经过长为△t的时间：（1）转移到n+1(0≤n∞)的概率为（2）转移到n-1(1≤n∞)的概率为（3）转移到S-{n-1,n,n+1}的概率为其中为与t无关的固定常数();ntot();ntot().ot0,0nn'00110'1111()()()n0()()()()()n1nnnnnnnnPtPtPtPtPtPtPt1M/M/1/∞系统np:系统达到平稳后，系统有n个顾客的概率。1n0)(0n01110nnnPPPPP平衡方程：1n)1(10nnPP1:令，且当时关于的几点说明：)1(/1/1(2)01(3)p顾客平均到达率顾客平均服务率顾客平均服务时间顾客平均到达时间——服务强度•系统中至少有一个顾客的概率；•服务台处于忙的状态的概率；•反映系统繁忙程度。,1)4(即顾客的平均到达率小于顾客平均服务率时，系统才能达到统计平稳。1M/M/1/∞系统1M/M/1/∞系统计算有关指标–平均队长1......)2(...)32()1(3232321n0nnnnnPL1)1(21n10nLPnPPnLnnnnq1M/M/1/∞系统–平均等待列长1M/M/1/∞系统–平均等待时间)()1(1100nnnnqnpnpW–平均逗留时间11)(1qWW•Little公式（相互关系）qqqqLL•小结：1WqWqLL1M/M/1/∞系统例：某火车站的售票处设有一个窗口。若购票者是以最简单流到达，平均每分钟到达1人，假定售票时间服从负指数分布，平均每分钟可服务2人，试研究售票窗口前的排队情况。1M/M/1/∞系统1L12qL)(qW1W2M/M/1/k系统顾客源排队系统排队结构服务台排队规则服务规则接受服务后离去无限输入过程服从参数为的最简单流单队队长有限先到先服务服务时间服从参数为的负指数分布2M/M/1/k系统np:系统达到平稳后，系统有n个顾客的概率。10111n0()0nk-1nknnnkkPPPPPPP,:令knPPnn,2,1,0,02M/M/1/k系统1,111,1110kkP11,11n1,2,...,k1,11nnkkP计算有关指标–平均队长–平均等待列长1,1)1(11,211kkkkL1,1)1(11,)1(2)1(1kkqkkkkL2M/M/1/k系统–平均等待时间–平均逗留时间2M/M/1/k系统1,)1(11,211kkkkW1,)1(1,211kkqkkW2M/M/1/k系统例：一个理发店只有一个理发师，有3个空椅子供等待理发的人员使用。设顾客以最简单流来到，平均每小时5人。理发师的理发时间服从负指数分布，平均每小时6人。试求L，Lq，W，Wq。第8章排队论结束