05排队论

排队论食堂就餐、超市购物收费、医院就诊、电话占线等常常要排队。在交通工程中，如车辆在交叉口、收费站、停车场、加油站等，乃至道路或筑路机械等的养护或维修也经常出现排队现象。排队论（QueueingTheory）也称为随机服务系统理论，是研究排队现象的一门科学。基本知识—排队过程排队过程（服务过程）的基本特征：(1)有要求服务的人或物（顾客）(2)有为顾客服务的人或物（服务台）(3)顾客到达服务系统（排队系统）的时刻是随机的基本知识—排队过程排队过程的一般模型：图8-1排队系统的模型顾客到来顾客来源排队结构服务机构排队规则服务规则离开排队系统基本知识—排队系统到达的顾客要求服务内容服务机构不能运转的机器修理修理技工修理技工领取修配零件管理员病人就诊医生文件稿打字打字员提货单提货仓库管理员到达机场上空的飞机降落跑道驶入港口的货船装卸货物码头河水进入水库放水，调整水位水闸管理员进入我方阵地的敌机我方高射炮进行射击我方高射炮基本知识—排队系统的分类(1)损失制排队系统电话占线；停车场客满。(2)等待制排队系统信号交叉口排队，食堂就餐。(3)混合制排队系统汽车加油（排队，客满离去）药品过期失效（排队，到期离去）基本知识—排队系统的组成输入过程：输入指顾客到达排队系统，输入过程指顾客到达排队系统的规律。①顾客的总体（顾客源）可能是有限的，可能是无限的；②顾客到达的方式可能是一个一个的，可能是成批的；③顾客相继到达的时间间隔可以是随机型的，可以是确定型的。④顾客到达可以是相对独立的，即以前到达情况对以后顾客的到来没有影响，否则就是有关联的；⑤输入过程可以是平稳的，或称对时间是齐次的，相继到达的间隔时间分布和所含参数（如期望值）与时间无关，否则称为非平稳的。基本知识—排队系统的组成排队规则：排队规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。①先到先服务（FCFS）②后到先服务（LCFS）③优先服务（PR）：在交通工程中，具有优先权的车辆（火车、警车等）或道路（主干道）优先服务（通过）。④随机服务（RSS）基本知识—排队系统的组成服务机构：服务机构包括为每个顾客服务所需的时间（概率分布），服务台的数目以及服务台的排列方式。①服务机构可以没有服务台，可以有一个或多个服务台②服务台的排列方式有单通道和多通道两种。单服务台和串联（前后排列）的多个服务台属于单通道服务方式。平行排列（并列）的多个服务台属于单通道服务方式。其中又分可通和不可通两种。还可以是混合排列。③服务方式可以是单个服务，可以是成批服务。基本知识—排队系统的组成服务机构：④服务时间可以是确定型的，可以是随机型的。⑤服务时间的分布可以是平稳型的，可以是非平稳型的。服务时间的概率分布形式和顾客到达时间间隔的分布形式主要有：M--负指数分布（Markov）D--确定型分布Ek--K阶爱尔朗分布G--一般分布基本知识—排队系统的表示顾客到达间隔时间的分布、服务时间的分布、服务台数、服务规则是确定排队系统的基本要素。肯道尔提出的排队模型的一般表示方法：到达时间间隔分布/服务时间分布/服务台数/系统容量N/顾客源容量n/服务规则基本知识—排队系统的表示到达时间间隔分布/服务时间分布/服务台数/系统容量N/顾客源容量n/服务规则例如：到达时间间隔为负指数分布、服务时间为负指数分布、服务台数为1、系统容量为m、顾客源无限、排队规则为先到先服务的排队模型表示为：M/M/1/m/∞/FCFS简化形式：如M/M/1表示：到达时间间隔为负指数分布、服务时间为负指数分布、服务台数为1、系统容量为∞、顾客源容量∞、服务规则为FCFS。基本知识—排队系统的运行指标分析和求解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以便决定系统结构是否合理、研究设计改进措施等。排队系统参数或运行指标有：队长、排队长、逗留时间、排队时间、忙期由于顾客到达时间间隔和服务时间一般是随机变量，并以概率来描述，所以这些指标也常用概率来衡量。基本知识—排队系统的运行指标队长：系统中顾客个数的期望值（）。排队长：系统中排队等待服务的顾客个数的期望值（）。正被服务的顾客个数的期望值逗留时间：一个顾客在系统中停留的时间的期望值（）。排队时间：一个顾客在系统中排队等待的时间的期望值（）。服务时间期望值sLqLqsLLqsWWsWqW基本知识—排队系统的运行指标忙期：顾客到达空闲服务机构到服务机构再次空闲的时间长度。在损失制和混合制的情形中，损失率和服务强度也是很重要的指标。研究排队系统就是研究这些运行指标，以合理地设计或改善排队系统。到达时间间隔分布和服务时间分布影响排队系统的主要因素是单位时间到达排队系统的顾客数和每个顾客的服务时间。利用其随机性的特点，一般用到达时间间隔和服务时间的分布（概率密度函数或概率的分布函数）来描述和表示。即单位时间内有K个顾客到达系统的概率，以及服务时间不少于某一时间长度的概率。到达时间间隔和服务时间的分布形式主要有：泊松分布、负指数分布、爱尔朗分布、二项分布、正态分布等。到达时间间隔分布和服务时间分布泊松流与泊松分布（顾客到达分布）满足下列三个条件的流为泊松流。平稳性：对，在时间区间内1个顾客到达的概率与无关，只与有关，且当时，与成正比，即：为单位时间内顾客到达的平均数，无后效性：在不相重叠的时间区间内顾客到达数相互独立，即前一顾客的到达不影响后一顾客的到达。0t),(ttt),(1tttPtt0tt)(),(1tOttttP0到达时间间隔分布和服务时间分布泊松流与泊松分布（顾客到达分布）普遍性：在同一时刻，即时在时间区间内有两个或两个以上顾客到达的概率很小，即：在时间区间内没有顾客到达的概率为：当时，则时：),(ttt0t)(1),(0tOttttP)(),(2tOtttPnn),(ttt0t)(),0(),(tPtPtttPnnn)(1)(0tOttP0n到达时间间隔分布和服务时间分布泊松流与泊松分布（顾客到达分布）设顾客到达过程符合泊松流，则在给定的内到达的顾客数为K个的泊松分布概率为：即：在内，顾客到达数服从参数为的泊松分布。期望值为：方差为：ttkkekttP!)()(),,2,1,0(kttttNE))((ttN))(var(到达时间间隔分布和服务时间分布泊松流与负指数分布（顾客到达时间间隔分布）当输入过程（到达过程）为泊松流时，则顾客相继到达的时间间隔H服从负指数分布。即到达间隔的负指数分布与到达过程的泊松流是等价的，故在排队模型中都用M表示。对于负指数分布：，这也表示了当是单位时间内顾客到达的平均数时，就是顾客到达的平均时间间隔。1)(HE21)var(H1到达时间间隔分布和服务时间分布泊松流与负指数分布（服务时间分布）设在内结束服务的顾客流符合泊松流，则在内有k个顾客结束服务的概率为：其中为平均服务率（单位时间顾客服务结束的平均数），则为每个顾客的平均服务时间。当时，ttkkekttP!)()(),,2,1,0(kt1tetP)(00k到达时间间隔分布和服务时间分布泊松流与负指数分布（服务时间分布）同样地，结束服务的顾客流符合泊松流时，服务时间T服从参数为的负指数分布，即：1)(TE21)var(Tt到达时间间隔分布和服务时间分布爱尔朗分布设是k个相互独立的随机变量，服从相同参数的负指数分布，则的概率密度为：这也称为T服从爱尔朗分布。当时，爱尔朗分布为负指数分布，随着的增大，逐渐近似于正态分布，时，（确定型）。kvvv,,,21kkvvvT21tkkkektkktf)!1()()(11)(TE1kkk0)var(T21)var(kT生灭过程—概念和定义研究生灭过程就是研究系统内部的状态变化，或建立状态概率。设有某系统，具有0，1，2，…个状态，在任一时刻，若系统处于某状态，系统随时间变化的过程满足以下三个条件，则称之为生灭过程。生灭过程—概念和定义①在时间内系统由状态转移到状态的概率为：（为平均转移率）②在时间内系统由状态转移到状态的概率为：（为平均服务率）③在时间内系统发生两次以上状态转移的概率为：对于输入过程和服务过程符合泊松流的排队系统，即M/M/C类排队系统，肯定是一个生灭过程。),(ttti1i)(tOtii),(ttt1ii)(tOti),(ttt)(tOi生灭过程—微分方程微分方程：边界条件：)()()()()()(lim)(11110tPtPtPttPttPdttdPiiiiiiiiiti)()()(11000tPtPdttdP)()()(11tPtPdttdPkkkkk生灭过程—代数方程当排队系统长期工作时，系统达到了统计平衡状态，状态概率趋于常数。即此时，微分方程变为代数方程：边界条件：0)(1111iiiiiiiPPP01100PP011kkkkPP0)(dttdPi上图是有K+1个状态的排队系统的状态转移图。在系统稳定条件下，对每个状态来说，转入率的期望值应该等于转出率的期望值，以求达到状态平衡。即：生灭过程—状态转移图S0S10112i-12i3S2Si-1iSii+1i+1i+2Si+1k-1Sk-1kSki-2i-1k-2k-1图8-2生灭过程1100PPkkkkPP11iiiiiiiPPP)(1111这就是生灭过程的代数方程，也称为平衡方程或平衡条件下的状态方程。生灭过程—状态方程1100PPkkkkPP11iiiiiiiPPP)(1111由系统的状态方程可以求出系统每一个状态的状态概率：当时：依此类推可以求得：另外，由正则条件：可以求得，从而求出其他状态的概率。生灭过程—状态概率021011212PPP1i0121012111PPPiiiiiiiikiiP010P（1）系统的到达过程、服务过程为泊松流，故其内部状态符合生灭过程。已知某排队系统，求该系统每一个状态的状态概率。生灭过程—例题3,2,//3/1//FCFSMM3210,,,SSSS（2）系统具有4个状态，设为：S0S1S2S3222333（3）状态转移图：（4）建立状态方程：（4）建立状态方程：由正则条件：则状态概率为：生灭过程—例题S0S1S2S3222333322231112010323232323232PPPPPPPPPPPP301iiP123.0,185.0,277.0,415.03210PPPP①输入过程服从参数为的泊松分布②顾客的服务时间是服从参数为的负指数分布③单个服务台④服务规则为FCFS根据顾客源及系统容量，可分为以下的几种情形：①标准的M/M/1/∞/∞系统②系统容量为m的M/M/1/m/∞系统③顾客源容量为K的M/M/1/∞/K系统M/M/1排队系统状态转移图：由状态方程可得：称为服务强度，当时，系统不稳定；当时，系统不稳定；当时，系统稳定。M/M/1/∞/∞排队系统图8-3M/M/1系统S2S0S1Si-1Si+1Si001PPP001PPPPiiiii111再由正则条件可以求得：系统运行指标：（1）系统中的平均顾客数-期望值（队长）（2）系统中排队的平均顾客数-期望值（排队长）M/M/1/∞/∞排队系统10PnnP)1(10SL1)(0nnSnPNEL