排队论模型课件

排队论方法建模排队是日常生活中常见的现象，某些资源、设备或空间的有限及社会部门对它们的需求是排队现象的主要因素，而诸如服务机构的管理水平低劣，服务效率不高，或顾客的无计划性以及其他原因也往往使不该有的排队现象出现。例如医院与病人，商店与顾客，机场与飞机，网络与用户，等等，诸如此类问题在一个排队系统中都有共同的特点：随机服务模型1)有一个或多个服务设施，如医生，飞机跑道等，可称此为“服务员”。2)有许多需要进入服务系统的被服务者，例如，候诊的病人，请求着陆的飞机等，称此为“顾客”。3)当被服务者随机地一个一个(或者一批一批)进入系统后，每位需要服务的时间不一定是确定的，服务过程的这种随机性造成某阶段不能立即得到服务，而有时服务员又空闲无事。随机服务模型一个服务系统总是有服务设施与被服务者构成。排队论主要是对系统建立数学模型，研究诸如单位时间内服务系统能够服务的顾客平均数、顾客平均的排队时间、排队顾客的平均数等数量规律。§1、排队论的基本概念随机服务模型§2、单服务窗的排队模型(M/M/1)§4、排队系统的优化模型§3、多服务窗的排队模型(M/M/n)§1、排队论的基本概念一、排队过程的一般模型二、排队系统的目标参量(或运行指标)四、系统状态的概率三、排队模型的分类与记号五、排队论问题中常见的概率分布设要求服务的顾客从顾客总体进入排队系统(输入)，到达服务机构前排队等候服务，服务完后立即离开(输出)。排队系统主要有输入、排队规则和服务机构三个部分组成。一、排队过程的一般模型随机服务模型(一)输入过程：顾客到达排队系统的过程，具有如下的特征：1)顾客总体(顾客源)可以是有限的，也可以是无限的；2)顾客到来的方式可能是一个一个的，也可能是成批的；3)顾客相距到达的间隔时间可以是确定的，也可以是随机的；4)顾客的到达是相互独立的；5)输入过程是平稳的，即相继到达的时间间隔分布与时间无关。(二)排队规则：顾客到达后的排队方式、队形和队列数目，有三条特征：1)排队方式损失制：顾客到达系统时，如果系统中所有服务窗均被占用，且没有场地供顾客等待，则到达的顾客随即离去。比如打电话。等待制：顾客到达系统时，虽然发现服务窗忙着，但系统有场地供顾客排队等候使用，于是到达系统顾客按先后顺序进行排队等候服务。通常的服务规则是先到先服务，后到先服随机服务模型随机服务模型务，随机服务，优先服务(比如急诊，快递等)。混合制：它是损失制与等待制混合组成的排队等候系统。此系统仅允许有限顾客等候排队，其余顾客只好离去或顾客中有的见到排队队伍长而不愿意费时等候，也有排队等候的顾客当等候时间超过某个时间就离去，均属这种系统。随机服务模型2)排队可以是有形的，也可以是无形的。有的排队容量是有限的，有的是无限的。3)排队数目可以是单列，也可以是多列，有的可相互转移，有的不可相互转移。(三)服务机构：对顾客提供服务的设施或对象，有以下特征：1)服务机构可以没有服务员(台)，也可以有一或多个服务员(台)；2)对于多个服务员(台)的情况，可以并联或串联；3)服务方式可以是一个一个地进行，也可以是成批成批地进行(如团购)；4)服务时间可以是确定型的，也可以是随机型的，对于随机型需要知道它的概率分布。随机服务模型随机服务模型5)服务时间的分布对时间是平稳的，即分布的期望值和方差参数都不受时间的影响。顾客的输入过程，服务时间都是随机的，其概率分布要依原始数据的规律做出经验分布，利用统计学的方法，确定服从哪种分布，并估计其参数。排队系统主要是研究系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理、研究设计改进措施。因此研究排队问题，首先要确定用以判断系统运行优劣的基本量化指标，然后求出这些指标的概率分布和数字特征。系统运行的主要指标有：1)逗留队长：排队的顾客数，其期望值记为Ls。2)等待队长：系统中排队等待服务的顾客数，其期望值记为Lq。二、排队系统的目标参量(或运行指标)随机服务模型若记正在接受服务的顾客数为Ln，则Ls=Lq+Ln。3)逗留时间：指一个顾客在系统中的停留时间，其期望值记为Ws。4)等待时间：指一个顾客在系统中排队等待时间，其期望值记为Wq。若记为接受服务时间，则Ws=Wq+。5)忙期：服务机构连续工作的时间长度，记作Tb6)损失概率：因系统条件限制，使顾客被拒绝服务而使服务部门受到损失的概率，记为P损。7)绝对通过能力A，表示单位时间内能被服务完顾客的期望值，或称平均服务率。8)相对通过能力Q，表示单位时间能被服务完的顾客的期望值与请求服务的顾客数之比值。随机服务模型排队模型的标准形式为X/Y/Z/A/B/C，其中X表示顾客相继到达间隔时间的概率分布，Y表示服务时间的概率分布，Z表示系统内服务台的个数，A表示系统的容量限制，B表示顾客数，C表示服务规则，通常只考虑先到先服务情况。三、排队模型的分类与记号比如M/M/C/N/m表示含义为顾客到达间隔和服务时间服从指数分布，服务台为C个，系统容量N，顾客源为m，先到先服务，其中M表示指数分布。所谓系统的状态是指系统中顾客的数量。它是求运行指标的基础。1)当队长无限制时，则顾客数n=0,1,2,…，2)当队长有限制且最大值为N时,n=0,…,N,3)当服务台个数为C且服务即时制时,n=0,…,C。四、系统状态的概率一般说来，状态的取值与时间t有关，因此在时刻t系统状态为n的概率为Pn(t)，如果limP()Pnntt则称系统为稳态，通常情况都认为是稳态情形。排队论中常见的分布有三种：泊松分布，指数分布，埃尔朗分布。1.泊松分布设N(t)表示在时间[0,t)内到达的顾客数，Pn(t1,t2)表示在时间段[t1,t2)内有n位顾客到达的概率，即Pn(t1,t2)=P{N(t2)-N(t1)=n}，当Pn(t1,t2)满足如下三个条件时，称顾客的到达形成泊松流。五、排队论问题中常见的概率分布1)无后效性：在互不相交的时间区间内顾客到达数是相互独立的，即在时间段[t,t+t)内到达k个顾客的概率与t之前到达多少顾客无关。2)平稳性：对充分小的t，在时间间隔[t,t+t]内有一位顾客到达的概率只与时间段t有关，与t无关，且P1(t,t+t)=t+o(t)，(0为平稳流强度)表示单位时间内有一个顾客到达的概率。随机服务模型3)普通性：在充分小的时间间隔[t,t+t]内最多到达1位顾客，到达2位或2位以上顾客的概率极小，可忽略不计，即随机服务模型)(),(P2totttnn随机服务模型下面求系统状态为n的概率：取初始时刻为t=0，则可记Pn(0,t)=Pn(t)，在[t,t+t)内，由于1),(P),(P),(P),(P2100ttttttttttttnnnn在[t,t+t)内，没有顾客到达的概率为012P(,)1P(,)P(,)1()nnttttttttttot即P0(t,t+t)=1-t+o(t)。将[0,t+t)分为[0,t)和[t,t+t)，则在时间段随机服务模型[0,t+t)内到达n位顾客的概率应为001P()P{N()N(0)}=P{N()N()}P{N()N(0)}P()P(,)P()(1)P()()nnknnkkknnttttntttktnkttttttttot1P()P()()P()P()nnnntttottttt(注意独立性)随机服务模型令t0，有1dP()P()P(),P(0)0(1)nnnntttndt特别地，当n=0时，有000dP()P(),P(0)1ttdt解得，P0(t)=e-t，代入上式得P1(t)=te-t，……()P(),0,1,2,,0!ntnttentn……，随机服务模型结果表明在长为t的时间内到达n位顾客{N(t)=n}的概率服从泊松分布，其数学期望与方差分别为E(N(t))=t，D(N(t))=t。2指数分布当顾客流为泊松流时，用T表示两个顾客到达的时间间隔，T为一随机变量，其分布函数为FT(t)=P{Tt}=1-P{Tt}=1-P{N(t)=0}=1-e-t，分布密度为fT(t)=e-t,t0。所以T服从指数分布，且E(T)=1/，D(T)=1/2，其中1/表示平均每到达一位顾客的时间间隔，因此可看做单位时间内进入系统的顾客数，也称平均到达率。随机服务模型随机服务模型类似地，对一个顾客接受服务的时间X(即在忙期内相继离开系统的两个顾客的时间间隔)服从指数分布，设分布函数与分布密度分别为FX(t)=1-e-t,fX(t)=e-t,t0,其中1/表示平均一位顾客接受服务的时间，表示单位时间内离开系统(被服务完)的顾客数，也称平均服务率。随机服务模型3埃尔朗(Erlang)分布当顾客流为泊松流时，用Yk表示第k个顾客到达的时刻，Yk为一随机变量，其分布函数为10()1!iktitei1Y(),0(1)!kkktfttetkFYk(t)=P{Ykt}=P{N(t)k}此分布是参数为k,的埃尔朗分布。随机服务模型2)到达间隔T1,T2,…,Tk,…相互独立，同服从参数为的指数分布。3)第k个顾客的到达时刻Yk服从参数为k,的埃尔朗分布。显然1)在[0,t]内到达的顾客数N(t)服从参数为t的泊松分布,泊松流过程所以k个相互独立同服从参数为的指数分布随机变量之和服从参数为k,的埃尔朗分布。Y1Y2YkOT1T2TktYk-1Yk=T1+T2+…+Tk随机服务模型设系统中有串联的k个服务台，每个服务台对顾客的服务时间相互独立，同服从指数分布，则顾客接受k台服务的总时间T服从埃尔朗分布。随机服务模型在伯努利试验中，到时刻t为止，共进行n次试验，这时成功次数服从二项分布。而在泊松过程中，到时刻t的来到数则服从泊松分布。为等待第一次成功，伯努利试验中的等待次数服从几何分布；而泊松过程中则服从指数分布，它们都具有无记忆性。为等待第r次成功，伯努利试验中的等待次数服从帕斯卡分布；而泊松过程中则服从埃尔朗分布。§2、单服务窗的排队模型(M/M/1)一、单服务窗损失制排队模型(M/M/1/1)二、单服务窗等待制排队模型(M/M/1)四、单服务窗闭合式排队模型(M/M/1/m/m)三、单服务窗混合制排队模型(M/M/1/m)五、可变服务率的M/M/1排队模型六、可变输入率的M/M/1排队模型(M/M/1/1)表示顾客到达间隔与被服务时间均服从指数分布，设参数分别为,,系统只设一个服务窗，且只容一人，先到先服务。如果顾客到达发现服务窗忙着，他即离开。比如一条电话线。一、单服务窗损失制排队模型(M/M/1/1)令t时刻,系统处于空闲或忙的概率为P0(t)或P1(t)，在[t,t+t)内，1)有一个顾客到达系统的概率为t+o(t)，2)没有顾客到达系统的概率为1-t+o(t)，随机服务模型1.确定系统在任意时刻t的状态概率010表示服务台闲，1表示服务台忙，系统状态流图随机服务模型3)有一个顾客被服务完离开系统的的概率为t+o(t)，4)没有顾客离开系统的概率为1-t+o(t)，在t+t时刻，服务窗空闲着及忙着的概率分别为P0(t+t)=P0(t)(1-t)+P1(t)t+o(t)，整理得P1(t+t)=P0(t)t+P1(t)(1-t)+o(t)，整理得P0(t+t)-P0(t)=-P0(t)t+P1(t)t+o(t)，P1(t+t)-P1(t)=P0(t)t-P1(t)t+o(t)随机服务模型上式两端同除以t，令t0得001dP()P()P(),tttdt110dP()P()P()tttdt设初始条件为:P0(0)=1,P