2012年排队论模型

长沙理工大学排队论2012年11月长沙理工大学0概述排队论是20世纪初才发展起来的，1905年丹麦哥本哈根的电话工程师爱尔朗最早在电话自动交换机设计上应用了排队论，第二次世界大战之后，排队论在很多领域被广泛采用。排队是日常生活中经常遇到的现象，由于有排队，那么就有顾客要等待了，如果增加服务设备的数量，那么就要增加投资或者发生设备的浪费；如果服务设备太少，那么排队就得不到消散。为了协调好“服务”与“需求”之间的矛盾，就产生了排队论。排队论又称作为随机服务系统理论，是研究“服务”系统因“需求”拥挤而产生排队的现象以及合理协调“服务”与“需求”关系的一种数学理论。排队论仍以概率论为基础，是运筹学的一个重要分支。排队论在交通工程方面有很广的应用，如用于分析交叉口的通行能力；计算交通延误；用于交通工程设施的设计，例如收费站的设计、加油站的设计、停车场的设计、服务区的设计、信号配时的设计等方面。长沙理工大学1相关基本概念排队过程的一般表示排队系统的三个组成部分顾客：要求服务的人或物，如要通过交叉口的车辆服务台：为顾客服务的人或物排队：排队机构本身相应地，排队系统模型从三个方面描述排队系统：输入过程、排队规则、服务方式。客源排队机构服务机构顾客到达排队规则服务规则离去长沙理工大学1相关基本概念排队和排队系统排队系统的三个组成部分输入过程：顾客按照一种什么样的规律到达排队系统。顾客的总体：有限、无限。顾客的到来方式：一个一个到达、成批到达。顾客到达时间间隔：定长输入、泊松输入、爱尔朗输入、G输入。顾客的到达是否相互独立顾客的输入过程是否是平稳的长沙理工大学1相关基本概念排队规则：顾客在排队系统中按什么样的规则、次序接受服务。损失制等待制混合制：排队长度有限制、排队时间有限制的服务系统。对于等待制和混合制，排队规则又可以细分为：先到先服务（FCFS）、后到先服务（LCFS）、优先服务（PR）、随机服务（RSS）。服务方式服务台的数量及其排列方式：单通道服务系统（单通道单服务台系统、单通道多服务台串联系统）；多通道服务系统（单路排队多通道服务系统、多路排队多通道服务系统）顾客的服务时间及其分布：定长分布的服务、负指数分布的服务、爱尔朗分布的服务、一般分布的服务。长沙理工大学1相关基本概念排队系统的表示方式到达规律/服务规律/服务台的个数/系统容量/顾客源容量/排队规则排队系统的主要数量指标队长：系统中顾客数的期望排队长：系统中排队等待服务的顾客数的期望平均逗留时间：又称为平均消耗时间，指一个顾客在系统中的停留时间的期望值。平均等待时间：又称平均排队时间，指一个顾客在系统中排队等待服务的时间的期望值。服务强度：又称作交通强度或利用系数，是衡量排队系统是否稳定的一个重要指标。忙期：服务台连续繁忙的时间。时稳定1长沙理工大学2生灭过程生灭过程的定义：生灭过程（BirthandDeathProcess）是研究系统内部的状态变化，建立状态概率的过程。生灭过程是随机过程的一种，是研究排队论的重要数学工具。对于排队系统而言，系统中有0个顾客数是一个状态，有1个顾客又是一个状态…。对不同的状态对应到系统中的顾客数不一致，并且各个状态之间是可以转化的。生灭过程是系统的状态随时间变化的过程，关键是建立状态概率方程，确定系统中各个状态的概率。设某个系统，具有0、1、2…个状态，N(t)表示系统在时刻t所处的状态（对于排队系统，即t时刻的顾客数）。在任一时刻，若系统处于状态i，且系统状态随时间变化的过程满足下面3个条件，就称之为一个生灭过程。长沙理工大学2生灭过程生灭过程的三个条件在(t,t+t)内系统由状态ii+1的概率为：it+o(t)，其中i0为固定常数，称之为从状态i到状态i+1的转移率〔到达率〕，流的平稳性条件。在(t,t+t)内系统由状态ii-1的概率为：it+o(t)，其中i0为固定常数，并称之为从状态i到状态i-1的转移率〔服务率〕，流的平稳性条件。在(t,t+t)内系统发生两次以上状态转移的概率为o(t)，即有两个以上顾客到达或离开的概率。从生灭过程的定义可知，对于一个排队系统，只要输入过程和服务过程符合泊松流，那么其排队过程肯定符合生灭过程。0)(2tPn长沙理工大学2生灭过程生灭过程图方框表示系统的状态箭头表示从一个状态向另一个状态的转移箭头上的标志表示状态平均转移率，或称转移流的强度生灭过程图中包含的信息状态各个状态的转出率各个状态的转入率各个状态的服务强度=/，要求服务强度1S0S1Sn011223n-1n-1nn+1n+1n+2S2……Sn+1长沙理工大学2生灭过程状态随时间的转移：可以证明，当时间t时，各个状态的概率趋于一个常数。即在系统稳定的情况下，转入率的期望值等于转出率的期望值。状态方程：利用系统稳定时，各状态的转入率平均值等于转出率的平均值建立状态方程。初始状态概率P0的计算：利用正则关系计算，即所有状态的概率总和为1。系统容量有限（最多n+1个状态）：系统容量无限：生灭过程应用举例10niiP10iiP长沙理工大学2生灭过程利用生灭过程求解系统状态概率的步骤根据给定的模型或问题的性质建立状态转移图；根据极限平衡条件建立状态方程式；根据正则条件利用状态方程式求解状态指标，即各状态的概率大小。各状态的概率是求解排队系统问题的基础，要基于系统的状态指标来计算其运营指标。长沙理工大学3M/M/1排队系统M/M/1排队系统简介系统特性：输入过程、服务时间、服务台数量。系统分类：系统容量和顾客源是有穷还是无穷划分。标准的M/M/1系统（M/M/1///FCFS系统）适用条件输入过程：顾客源无限，顾客单个到来，相互独立，一定时间内的到达数服从泊松分布；排队规则：单队，先到先服务，对队长无限制；服务方式：单服务台，顾客的服务时间相互独立，服从相同的负指数分布。到达排队服务长沙理工大学3M/M/1排队系统生灭过程图根据生灭过程定义，M/M/1系统的排队过程是一个生灭过程，且生灭过程的状态数为无穷，同时有i=，i=，即各个状态的到达率和服务率相等，均为平均到达率和平均服务率。从状态S0出发，到达一个顾客后就到了状态S1；从状态S1出发，到达一个顾客就转到了状态S2、离去一个顾客后又回到状态S0。S0S1SnS2……Sn+1长沙理工大学3M/M/1排队系统状态转移方程对于状态S0：对于状态S1：对于状态Sn-1：00110PPPPP02022200012120)()()(PPPPPPPPPPP0PPnn长沙理工大学3M/M/1排队系统对服务强度的讨论为顾客的平均到达率，1/为顾客到达的平均时距；为系统的平均服务率，1/为每位顾客的平均服务时间。在M/M/1/排队系统中，必须要有1。如果1，即单位时间内到达服务系统的顾客数大于离开服务系统的顾客数，那么当t时，排队长度将无限增加，系统达不到稳定状态。当=1时，系统的负荷水平达到100%，这时系统也无法达到稳定状态，虽然这时平均到达率等于平均服务率，但由于到达是随机的，可能有些时候服务台是空闲的，因而失去了一些可用于服务的时间，这种时间损失越多，排队积累越快，队列渐渐的越排越长，从而达不到统计平衡。长沙理工大学3M/M/1排队系统M/M/1排队系统的状态指标nPPPPPPPPnnnnnii1,1),1(,11111)1(10202002000长沙理工大学3M/M/1排队系统M/M/1排队系统的运行指标队长（系统中的平均顾客数）排队长（平均排队长度）)10(1)2()32()1(32323201000iiiiiiiiiiiiPn111)1(1)1(220111PPiPiPqiiiiii长沙理工大学3M/M/1排队系统系统中顾客数的方差2222222222222'2'432'4'3'2323232432432432012202022)1()1()1()()()1()1(33)1(2413)1(213][213])()()[(213]432[2][3]432[2753)94()1694()()1()(xExEiiiPixEiiiiiii长沙理工大学3M/M/1排队系统非零平均排队长度（忙期内服务的顾客数）闲期（系统中没有顾客）的概率为:忙期（系统中有顾客）的概率为：设闲期的平均长度为，设忙期的平均长度为闲期的期望等于顾客到达的间隔时间，即当系统稳定时有非零平均排队长度为忙期的时间乘以忙期的服务率10PPI)1(110PPBIB1)(IE11)(1)(1)()(IEBEPPIEBEIB1111)(BEqwqnqw长沙理工大学3M/M/1排队系统平均逗留时间平均等待时间各运行指标间的相关关系111nd1)(112dqwqqnwdwqdn1长沙理工大学3M/M/1排队系统平均逗留时间和平均等待时间的另一种计算方法当有n个顾客时，新到达的顾客的平均消耗时间为(n+1)/，因此有：同理：M/M/1排队系统中顾客数不超过k的概率1)1(1]11[1]1[1][1)(11)1(0000nPnPPnPPndnnnnnnnnn)(111100nnnnnPPnw111211011)(kkkkkkkPPPPkP长沙理工大学3M/M/1排队系统标准的M/M/1排队系统应用举例对M/M/1排队系统的分析02468100.00.20.40.60.81.002550751000.00.20.40.60.81.0排队队长度显著增时,1当)1(1)(12'nn长沙理工大学4M/M/1/m排队系统_容量有限系统含义M/M/1/m//FCFS排队系统指系统容量受到限制、顾客源为无限、先到先服务的单通道排队系统。该排队系统的容量最多为m，排队的容量为(m-1)系统状态系统容量为m，其排队容量为(m-1)。具有(m+1)个状态，S0、S1、S2……Sm。生灭过程图S0S1Sm-1S2……Sm长沙理工大学4M/M/1/m排队系统_容量有限状态概率计算对状态S0：P0＝P1P1=P0对状态S1：P0+P2＝(+)P1P2=2P0对状态Sm：Pm-1＝PmPm=Pm-1=mP0根据正则关系：1)1(102002000PPPPPPmmmii长沙理工大学4M