运筹学-排队论

1、1第十二章第十二章排队论排队论(Queuing Theory)1 排队论的基本概念排队论的基本概念2 到达间隔的分布和服务时到达间隔的分布和服务时间的分布间的分布3 排队系统的分析排队系统的分析2排队论排队论(Queuing Theory)，又称随机服务系统理论又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象是一门研究拥挤现象(排队、等待排队、等待)的科学。具体地说，它是在研究各种排队的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。设计和最优控

2、制问题。排队论是排队论是1909年由丹麦工程师年由丹麦工程师爱尔朗爱尔朗(A.KErlang)在研在研究电话系统时创立的，几十年来排队论的应用领域越究电话系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪来越广泛，理论也日渐完善。特别是自二十世纪60年年代以来，由于计算机的飞速发展，更为排队论的应用代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。开拓了宽阔的前景。3第一节第一节 基本概念基本概念一、排队系统的一般表示一、排队系统的一般表示例例1、各个顾客由顾客源出发，到达服务机构前排队等候、各个顾客由顾客源出发，到达服务机构前排队等候 服务，服务

3、完了后就离开。服务，服务完了后就离开。排队结构指队列的数目和排列方式排队结构指队列的数目和排列方式排队规则和服务规则是说明顾客在排队系统中按怎样排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。的规则、次序接受服务的。顾客源顾客源排队结构排队结构排队规则排队规则服务规则服务规则服服务务机机构构离去离去顾客到来顾客到来排队系统排队系统4排队是我们在日常生活和生产中经常遇到的现象排队是我们在日常生活和生产中经常遇到的现象:q 上、下班搭乘公共汽车；上、下班搭乘公共汽车；q 顾客到商店购买物品；顾客到商店购买物品；q 病员到医院看病；病员到医院看病；q 旅客到售票处购买车票；旅客

4、到售票处购买车票；q 学生去食堂就餐等就常常出现排队和等待现象。学生去食堂就餐等就常常出现排队和等待现象。q 排队的不一定是人，也可以是物：排队的不一定是人，也可以是物：w通讯卫星与地面若干待传递的信息；通讯卫星与地面若干待传递的信息；w生产线上的原料、半成品等待加工；生产线上的原料、半成品等待加工；w因故障停止运转的机器等待工人修理；因故障停止运转的机器等待工人修理；w码头的船只等待装卸货物；码头的船只等待装卸货物；w要降落的飞机因跑道不空而在空中盘旋等等。要降落的飞机因跑道不空而在空中盘旋等等。5一般排队的过程一般排队的过程 顾客到达顾客到达队队 列列（排队规则）（排队规则）服务台服务台（

5、接受服务）（接受服务）顾客离去顾客离去6二、排队系统的组成和特征二、排队系统的组成和特征输入即指顾客到达排队系统，可能有以下不同情况。输入即指顾客到达排队系统，可能有以下不同情况。1、输入过程、输入过程 （1）顾客源的组成）顾客源的组成有限的有限的无限的无限的（2）顾客到来的方式）顾客到来的方式 一个一个的一个一个的成批的成批的（3）顾客相继到达的间隔时间）顾客相继到达的间隔时间确定型的确定型的随机型的随机型的（4）顾客的到来）顾客的到来相互独立的相互独立的关联的关联的（5）输入过程）输入过程平稳的，或称对时间是齐次的平稳的，或称对时间是齐次的非平稳的非平稳的72、排队规则、排队规则顾客在排队

6、系统中按怎样的规则、次序接受服务的。顾客在排队系统中按怎样的规则、次序接受服务的。（1）顾客到达时，所有服务台被占用）顾客到达时，所有服务台被占用随即离去的随即离去的 称为即时制（损失制）称为即时制（损失制）排队等候称为等待制排队等候称为等待制先到先服务先到先服务后到先服务后到先服务随机服务随机服务有优先权有优先权（2 2）从队列占用空间）从队列占用空间有限的有限的无限的无限的（3）从队列的数量）从队列的数量单列单列多列多列83、服务机构、服务机构（1）服务员数量）服务员数量没有没有一个或多个一个或多个（2）多服务台时）多服务台时单队单队单服务台单服务台单队单队多服务台（并列）多服务台（并列）

7、9多队多队多服务台（并列）多服务台（并列）多服务台（串列）多服务台（串列）10（3）服务方式）服务方式对单个顾客进行对单个顾客进行对成批顾客进行对成批顾客进行（4）服务时间）服务时间确定型确定型随机型随机型（5）服务时间的分布我们总假定是平稳的，即）服务时间的分布我们总假定是平稳的，即 分布的期望值、方差等参数都不受时间的影响分布的期望值、方差等参数都不受时间的影响12312多服务台混合多服务台混合11一个排队系统的特征可以用六个参数表示，形式为：一个排队系统的特征可以用六个参数表示，形式为： X/Y/Z /A/B/C其中其中qX 顾客到达的概率分布，可取顾客到达的概率分布，可取M、D、Ek等

8、；等；qY 服务时间的概率分布，可取服务时间的概率分布，可取M、D、Ek等；等；qZ 服务台个数，取正整数；服务台个数，取正整数；qA 排队系统的最大容量，可取正整数或排队系统的最大容量，可取正整数或 ；qB 顾客源的最大容量，可取正整数或顾客源的最大容量，可取正整数或 ；qC 排队规则，可取排队规则，可取FCFS、LCFS等。等。 三、排队模型的分类三、排队模型的分类(条件参数条件参数)12表示相继到达间隔时间和服务时间的各种分布的符号表示相继到达间隔时间和服务时间的各种分布的符号:M负指数分布负指数分布D 确定型确定型Ekk阶爱尔朗分布阶爱尔朗分布GI 一般相互独立的时间间隔的分布一般相互

9、独立的时间间隔的分布G 一般服务时间的分布一般服务时间的分布例如：某排队问题为例如：某排队问题为 M / M / s / / /FCFS 则表示顾客到达间隔时间为负指数分布则表示顾客到达间隔时间为负指数分布(泊松流泊松流)；服务时；服务时间为负指数分布；有间为负指数分布；有s(s1)个服务台；系统等待空间容量无个服务台；系统等待空间容量无限限(等待制等待制)；顾客源无限，采用先到先服务规则。；顾客源无限，采用先到先服务规则。可简记为：可简记为： M / M / s 13四、排队系统的参数四、排队系统的参数(分析结果分析结果)1、队长（、队长（Ls） 指在系统中的顾客数指在系统中的顾客数,期望值

10、期望值2、排队长（、排队长（Lq） 指系统中排队等候服务的顾客数指系统中排队等候服务的顾客数3、逗留时间（、逗留时间（Ws） 指一个顾客在系统中的停留时间指一个顾客在系统中的停留时间4、等待时间（、等待时间（Wq） 指一个顾客在系统中排队等待的时间指一个顾客在系统中排队等待的时间Ls=Lq+正被服务的顾客数正被服务的顾客数Ws=Wq+服务时间服务时间这四项主要性能指标这四项主要性能指标(又称主要工作指标又称主要工作指标)的值越小，说明系的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。们

11、是顾客与服务系统的管理者都很关注的。145、忙期、忙期 指从顾客到达空闲服务机构起到服务机构再次空指从顾客到达空闲服务机构起到服务机构再次空闲止闲止 这段时间长度，即服务机构连续繁忙的时间长度。这段时间长度，即服务机构连续繁忙的时间长度。6、系统的状态、系统的状态n：指系统中的顾客数。：指系统中的顾客数。8、稳定状态：、稳定状态：t 时，时，t=0时的系统不稳定状态将消失，时的系统不稳定状态将消失，系统的状态概率分布不再随时间变化，即系统的状态概率分布不再随时间变化，即 limPn(t)Pn。7、系统状态的概率、系统状态的概率Pn(t)：指时刻：指时刻t、系统状态为、系统状态为n的概率。的概率

12、。一般为关于一般为关于t的微分方程、关于的微分方程、关于n的差分方程。的差分方程。159、其他常用数量指标、其他常用数量指标q s 系统中并联服务台的数目；系统中并联服务台的数目；q 平均到达率；平均到达率；q 1/ 平均到达间隔。平均到达间隔。q 平均服务率；平均服务率；q 1/ 平均服务时间。平均服务时间。q 服务强度，服务强度，每个服务台单位时间内的平均服务时间；每个服务台单位时间内的平均服务时间； 一般有一般有 s ；当；当s=1时：时： 16对于损失制和混合制的排队系统，顾客在到达服务系统时，对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已满，则自行消失。这就是说，到

13、达的顾客不若系统容量已满，则自行消失。这就是说，到达的顾客不一定全部进入系统，为此引入：一定全部进入系统，为此引入：q e 有效平均到达率有效平均到达率, 即每单位时间实际进入系统的即每单位时间实际进入系统的平均顾客数（期望值），不同于平均顾客数（期望值），不同于 . 对于等待制的排队系统，对于等待制的排队系统， e 17一、经验分布一、经验分布例例2 某服务机构单服务台，先到先服务，对某服务机构单服务台，先到先服务，对41顾客记录到达顾客记录到达时刻时刻 和服务时间和服务时间s（单位：分钟）如下表，表中第（单位：分钟）如下表，表中第1号顾客到号顾客到达时刻为达时刻为0。全部服务时间为。全部服

14、务时间为127（分钟）。（分钟）。第二节第二节 到达间隔的分布和服务时间的分布到达间隔的分布和服务时间的分布(1) i(2)i(3)si(4)ti(5)wi(1) i(2)i(3)si(4)ti(5)wi(1) i(2)i(3)si(4)ti(5)wi1052051227109361202274361943510 38270361567223461145520411912826310 512 4742318(1) i(2) i(3)si(4)ti(5)wi(1) i(2) i(3)si(4)ti(5)wi(1) i(2) i(3)si(4)ti(5)wi13491352386622331174

15、4714522932488546341212671561110259213735127123166223026953653612961217651502710124237130337187032028105210381335271972481291061313913524102080310301092504013943821812223111412041142119228333232116810各栏意义：各栏意义：（1）i，顾客编号；（，顾客编号；（2）i：顾客：顾客i到达的时刻；（到达的时刻；（3）si：服务时间；以上三栏是原始数据；：服务时间；以上三栏是原始数据；（4） ti ：到达间隔；

16、（：到达间隔；（5）wi：排队等待时间；这俩栏是可以通过计算得到的：排队等待时间；这俩栏是可以通过计算得到的19到达间隔分布表到达间隔分布表服务时间分布表服务时间分布表到达间隔（分钟）到达间隔（分钟） 次数次数12345678910以上以上11122368106合计合计40服务时间（分钟）服务时间（分钟） 次数次数123456789以上以上11214571010合计合计41平均间隔时间平均间隔时间=142/40=3.55(分钟分钟/人人)平均到达率平均到达率=41/142=0.28(人人/分钟分钟)平均服务率平均服务率=41/127=0.32(人人/分钟分钟)平均服务时间平均服务时间=127/

17、41=3.12(分钟分钟/人人)20 输入过程是描述各种类型的顾客以怎样的规律到达系统，输入过程是描述各种类型的顾客以怎样的规律到达系统，一般用相继两顾客到达时间间隔一般用相继两顾客到达时间间隔 来描述系统输入特征。主来描述系统输入特征。主要输入过程有：定长输入，泊松输入要输入过程有：定长输入，泊松输入1定长输入定长输入 是指顾客有规则地等距到达，每隔时间是指顾客有规则地等距到达，每隔时间到达一个顾客。到达一个顾客。这时相继顾客到达间隔这时相继顾客到达间隔 的分布函数的分布函数F(t)为为定长输入定长输入 例如，生产自动线上产品从传送带上进入包装箱就是这例如，生产自动线上产品从传送带上进入包装

18、箱就是这种情况种情况 t0t1tPtF21二、二、泊松泊松(Poisson)输入输入泊松泊松(Poisson)输入，即泊松流，又称最简单流。输入，即泊松流，又称最简单流。 设随机变量设随机变量X服从服从Poisson分布，则概率密度分布，则概率密度,!2100nnenXPn 如果一个随机变量，概率分布与时间如果一个随机变量，概率分布与时间t有关，则称这个随机有关，则称这个随机变量为一随机过程，变量为一随机过程，排队系统中顾客到达的个数排队系统中顾客到达的个数就是一个就是一个随机过程。随机过程。 (1) Poisson流的定义流的定义 满足以下四个条件的输入流称为满足以下四个条件的输入流称为Po

19、isson流流(Poisson过程过程)22平稳性平稳性：增量与时间起点无关：增量与时间起点无关 在时间区间在时间区间t, t+ t)内到达内到达k个顾客的概率与个顾客的概率与t无关，只与无关，只与 t有关。记为有关。记为pk( t）。）。无后效性无后效性 不相交的时间区间内到达的顾客数互相独立。不相交的时间区间内到达的顾客数互相独立。稀有性稀有性：瞬时内只可能有：瞬时内只可能有1个顾客到达个顾客到达 设在设在t, t+ t）内到达多于一个顾客的概率为内到达多于一个顾客的概率为q( t），），则则 q( t)=o( t). 即即有限性有限性 任意有限个区间内到达有限个顾客的概率等于任意有限个区

20、间内到达有限个顾客的概率等于1。即。即 0ttq0t lim 1tp0kk 23区间情况0,t)t,t+ t)0,t+ t)个数概率个数概率个数概率(A)nPn(t)01-t+o(t)nPn(t)(1-t+o(t)(B)n-1Pn-1(t)1t +o(t)nPn-1(t) (t +o(t)(C)n-2Pn-2(t)2o(t)no(t)n-3Pn-3(t)3n0P0(t)nn简记简记 Pn(0,t)= Pn(t)。表示表示0,t)时间内到达时间内到达n个顾客的概率，即输入。个顾客的概率，即输入。对于区间对于区间0,t+ t)，可分成两个互不重叠的区间，可分成两个互不重叠的区间0,t)和和t,t+

21、 t)。设。设在区间在区间0,t+ t)上，到达总数为上，到达总数为n，会出现，会出现A,B,C三种情况：三种情况：区间区间0,t+ t)内到达内到达n个顾客应是表中三种互不相容的情况之一，个顾客应是表中三种互不相容的情况之一，所以概率所以概率Pn(t+ t)应是三个概率之和应是三个概率之和 ，即：，即：24 Pn（t+t）= Pn（t）（）（1- t ）+Pn-1（t） t+ o（t）Pn（t+t）- Pn（t）/ t = Pn（t）+ Pn-1（t）+ o（t）/ t 令令t0d Pn（t）/dt= - Pn（t） + Pn-1（t）Pn（0）=0（n 1）d P0（t）/dt= - P0

22、（t）P0（0）=1（n=0）求求出出 整理后得：整理后得：,!)()(2100nnettPtnn tetP )(0由此可见，泊松输入，即在由此可见，泊松输入，即在 t 时段内到达时段内到达n个顾客的概率服从个顾客的概率服从参数为参数为的泊松分布。的泊松分布。注意：我们要把泊松输入同前面提到的系统状态注意：我们要把泊松输入同前面提到的系统状态Pn区分开区分开25参数参数 的实际意义的实际意义 设设N(t)表示在表示在0，t）内到达的顾客数的期望值内到达的顾客数的期望值由此得到由此得到 即即 的实际意义为的实际意义为单位时间内到达的顾客数的期望值单位时间内到达的顾客数的期望值，或，或称称平均到达

23、速率平均到达速率。ktkk 0k 1k 1tttk 1( t )N(t )kp (t )kek!( t )( t )e( t )e et(k1)! N(t )t 26泊松分布泊松分布由概率论可知，如果随机变量由概率论可知，如果随机变量X服从参数为服从参数为泊松分布，则泊松分布，则其分布函数为（其分布函数为（注：不是很重要注：不是很重要）密度函数为密度函数为X的期望值为的期望值为X的方差为的方差为F( x )P Xx E( X )t D( X )Var( X )t ,!)(2100nnetnXptn 27由概率论可知，如果随机变量由概率论可知，如果随机变量T服从负指数分布，则其分服从负指数分布，

24、则其分布函数为布函数为密度函数为密度函数为T的期望值为的期望值为T的方差为的方差为tF(t )1et00 tf (t )et00 t001E(T )tf (t )dtt edt21D(T )Var(T )三、负指数分布三、负指数分布（指数分布指数分布）28Poisson流与负指数分布之间的关系流与负指数分布之间的关系定理定理 在排队系统中，如果到达的顾客数服从以在排队系统中，如果到达的顾客数服从以 为参数的为参数的Poisson分布，则顾客相继到达的时间间隔服从以分布，则顾客相继到达的时间间隔服从以 为参为参数的负指数分布。数的负指数分布。证明：设证明：设Poisson流中顾客相继到达的时间间

25、隔为随机变量流中顾客相继到达的时间间隔为随机变量T，并且在时刻并且在时刻0有一个顾客到达，则下一个顾客将在时有一个顾客到达，则下一个顾客将在时刻刻T到达。到达。T的分布函数为的分布函数为其中其中pTt表示在表示在0，t）内没有顾客到达的概率，因此内没有顾客到达的概率，因此所以，所以，T的分布函数为的分布函数为tTPtTPtF1)( tetTP tetF 1)(29T的密度函数为的密度函数为因此，顾客相继到达的时间间隔服从以因此，顾客相继到达的时间间隔服从以 为参数的负指数分为参数的负指数分布。布。 可以看出，可以看出，“到达的顾客数是一个以到达的顾客数是一个以 为参数的为参数的Poisson流

26、流”与与“顾客相继到达的时间间隔服从以顾客相继到达的时间间隔服从以 为参数的负指数分为参数的负指数分布布”两个事实是等价的。两个事实是等价的。tetf )(顾客相继到达的时间间隔服从以顾客相继到达的时间间隔服从以 为参数的负指数分布为参数的负指数分布30服务时间服务时间 服从负指数分布，概率密度为服从负指数分布，概率密度为0 0,0,)(ttetftv 参数参数 同样具有两层含义同样具有两层含义：单位时间内服务的顾客人数的期单位时间内服务的顾客人数的期望值望值，或称，或称平均服务率平均服务率。 由于由于 的均值为的均值为1/ ，即平均对每位顾客的服务时间，即平均对每位顾客的服务时间为为1/ .

27、服务时间服从以服务时间服从以 为参数的负指数分布为参数的负指数分布31负指数分布具有无记忆性负指数分布具有无记忆性定理定理 设对顾客的服务时间设对顾客的服务时间X服从参数为服从参数为 的负指数分布。的负指数分布。在对某一个顾客的服务已经进行了一定时间的条件下，在对某一个顾客的服务已经进行了一定时间的条件下，这个顾客的剩余的服务时间仍服从以这个顾客的剩余的服务时间仍服从以 为参数的负指数分为参数的负指数分布。布。证明：设服务已经进行的时间为证明：设服务已经进行的时间为 ，则剩余时间不少于，则剩余时间不少于t的条的条件概率为件概率为由此看出，服务剩余时间的分布独立与已经服务过的时间由此看出，服务剩

28、余时间的分布独立与已经服务过的时间，并且与原来的服务时间的分布相同。，并且与原来的服务时间的分布相同。( t)tP Xt,XP Xt| XP XP XteeP Xt P Xe 32设设v1，v2，vk是是k个互相独立的，具有相同参数个互相独立的，具有相同参数 的负指的负指数分布随机变量，则随机变量数分布随机变量，则随机变量服从服从k阶阶Erlang分布，分布，S的密度函数为的密度函数为12kSvvvk 1t( t )f (t )et0(k1)! 四、四、k阶爱尔朗阶爱尔朗(Erlang)分布分布期望值为期望值为 方差为方差为1E(T )21D(T )Var(T )k注意：当注意：当k=1时，爱

29、尔朗分布就是负指数分布，是完全随机的；当时，爱尔朗分布就是负指数分布，是完全随机的；当k=30时，近似于正态分布；一般时，近似于正态分布；一般k阶爱尔朗分布可看成是完全随机阶爱尔朗分布可看成是完全随机与完全确定的中间型，有更广泛的适应性。与完全确定的中间型，有更广泛的适应性。33一、一、M/M/1模型模型1 1、假设、假设（1 1）顾客到达的间隔时间满足参数为）顾客到达的间隔时间满足参数为的负指数分布的负指数分布（2）服务时间满足参数为）服务时间满足参数为的负指数分布（的负指数分布（ ）（3）服务机构是单服务台）服务机构是单服务台（4）顾客源是无限的，顾客到来相互独立）顾客源是无限的，顾客到来

30、相互独立（5）单队排列，且对队长没有限制）单队排列，且对队长没有限制第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析求：求：（1）系统状态概率）系统状态概率Pn； （2）系统运行指标系统运行指标Ls，Lq，Ws，Wq。342、Pn的计算的计算情况情况在时刻在时刻t顾客数顾客数在区间（在区间（t，t+t）到达到达离去离去在时刻在时刻t+t顾客数顾客数ABCDnn+1n-1nnnnn注：注：表示发生（表示发生（1个），个）， 表示没有发生。表示没有发生。nnn 1n 1nP (tt )P (t )1t )1t P(t )1t t P(t )t 1t P (t )t )

31、t 35整理后得：整理后得：nnn 1n 1nnn 1n 1P (tt )P (t )1tt P(t )t P(t )t o( t )P (t )()P (t ) tP(t ) tP(t ) to( t ) 将将Pn(t)移到左边，两边同除以移到左边，两边同除以 t，得到，得到nnnn 1n 1P (tt )P (t )o( t )()P (t )P(t )P(t )tt 令令 t0时，得到关于时，得到关于Pn(t)的微分方程：的微分方程：nn 1n 1ndP (t )P(t )P(t )()P (t )(1)dt 001P (tt )P (t )1t P (t )1t t 当当n=0，则只有

32、表中，则只有表中A，B两种情况，即两种情况，即同理，求得：同理，求得：010dP (t )P (t )P (t )(2)dt36Pn(t)的稳态解的稳态解Pn如果能够求解由无限个方程组成的差分微分方程组，就可如果能够求解由无限个方程组成的差分微分方程组，就可以得到以得到Pn(t)的瞬态解，即系统中有的瞬态解，即系统中有n个顾客的概率随时间变个顾客的概率随时间变化的解析表达式，但这是十分困难的。化的解析表达式，但这是十分困难的。如果假定当时间足够长，系统有如果假定当时间足够长，系统有n个顾客的概率个顾客的概率Pn(t)会趋于会趋于某个稳定值，即当某个稳定值，即当t时系统趋于概率稳态，这个稳态解是

33、时系统趋于概率稳态，这个稳态解是可以求出来的。可以求出来的。设当设当t时，时，Pn(t)趋于一个常数，这时趋于一个常数，这时Pn(t)与与t无关，可无关，可记记为为Pn，则则Pn关于关于t的导数为的导数为0。0ndP (t )dP (t )00dtdt10PP0(3)n 1n 1nPP()P0(4 ) 这时这时(1)式和式和(2)式可得式可得37状态转移图状态转移图以系统中的顾客数以系统中的顾客数0，1，2，n-1，n，n+1，作为系作为系统的状态，统的状态， (3)和和(4)表示系统位于某一状态的概率仅与其表示系统位于某一状态的概率仅与其相邻状态的概率以及从相邻状态转移到该状态的概率有相邻状

34、态的概率以及从相邻状态转移到该状态的概率有关关。系统状态（系统状态（n）随时间变化的过程是生灭过程的一个特殊情）随时间变化的过程是生灭过程的一个特殊情况，况， (3)和和(4)关于关于Pn的差分方程，可以用状态转移图来表的差分方程，可以用状态转移图来表示各状态间的转移关系，并能求解。示各状态间的转移关系，并能求解。0n12310PP0(3)n 1n 1nPP()P0(4 ) 38由由(3)和和(4)可以递推求解可以递推求解P1，P2，Pn，。由由(3)得到得到 (5)由由(4)得到得到 (6)将将(5)代入代入(6)用递推方法可以得到用递推方法可以得到 (7)10PP201PP(1)P 220

35、00PP(1)PP nn0PPn1,2,39由由得到得到令令 称称 为服务强度为服务强度，则，则当当 时，级数收敛，这时有时，级数收敛，这时有 (8)kk 0P12n01P1=102n1P1 0101P111 40代入代入(7)，得到，得到 (9)(8)和和(9)可以统一表示为可以统一表示为 (10)当当1时，级数发散，不存在稳态解时，级数发散，不存在稳态解(队列将会排至无限远队列将会排至无限远） ，因此，排队系统处于概率稳态的条件是因此，排队系统处于概率稳态的条件是,.,)(21010nPPnnn 10 01(1)0,1,2,.nnPPn 注：注： 是系统的服务强度，即是忙期，是系统的服务强

36、度，即是忙期，(1- )=P0就是系统空闲时间。就是系统空闲时间。41例例1高速公路入口收费处设有一个收费通道，汽车到达服高速公路入口收费处设有一个收费通道，汽车到达服从从Poisson分布，平均到达速率为分布，平均到达速率为100辆小时，收费时间辆小时，收费时间服从负指数分布，平均收费时间为服从负指数分布，平均收费时间为15秒辆。求秒辆。求1、收费处空闲的概率；、收费处空闲的概率；2、收费处忙的概率；、收费处忙的概率；3、系统中分别有、系统中分别有1，2，3辆车的概率。辆车的概率。解：解： 根据题意根据题意, =100辆辆/小时，小时， =15秒秒=240（小时（小时/辆）辆）,即即 240

37、（辆（辆/小时）。小时）。因此因此1125240100 42系统空闲的概率为：系统空闲的概率为：系统忙的概率为：系统忙的概率为：系统中有系统中有1辆车的概率为：辆车的概率为：系统中有系统中有2辆车的概率为：辆车的概率为：系统中有系统中有3辆车的概率为：辆车的概率为：583012712511P0. 417012511P10.)( 2430144351271251P1.)( 101017281751271251P222.)( 04220207368751271251P333.)( 433、M/M/1 参数计算参数计算（1）系统中平均顾客数队长（）系统中平均顾客数队长（Ls）kkskk 0k 0k

38、02LkPk(1)(1)k(1)(1)1 （2）队列中等待的平均顾客数（）队列中等待的平均顾客数（Lq）kqkk 1k 122k2k 1L(k1)P(k1)(1)(1)(k1)(1)(1)1 n即即Lq= Ls44（3）顾客逗留时间（）顾客逗留时间（Ws）WEWs 1（4）队列中顾客等待时间（）队列中顾客等待时间（Wq）ssqWWW 145将以上结果总结如下：将以上结果总结如下：对于对于M/M/1/ / /FCFS系统，系统，系统中由系统中由k个顾客的概率为：个顾客的概率为：系统中的平均顾客数为：系统中的平均顾客数为：队列的平均长度为：队列的平均长度为：顾客在系统中的平均逗留时间为：顾客在系统

39、中的平均逗留时间为：顾客在队列中的平均等待时间为：顾客在队列中的平均等待时间为：,)(210k1Pkk 101Ls 10L1Ls22q ssL1W qsqLWW 46Little公式公式一般化一般化Little公式的条件公式的条件: 排队系统能够进入统计平衡状态；排队系统能够进入统计平衡状态； 服务台的忙期与闲期交替出现；服务台的忙期与闲期交替出现； 系统中任一顾客不会永远等待，系统也不会永远无顾客系统中任一顾客不会永远等待，系统也不会永远无顾客到达。到达。 1WWLLWLWLqsqsqqss n0kkkeqseqsqeqsesP1WWLLWLWL 其其中中：47例例3 100个工作小时内每小

40、时个工作小时内每小时来就诊的病人数来就诊的病人数n出现次数如下出现次数如下 100个完成手术的病例所用时间个完成手术的病例所用时间v（小时）出现的次数如下（小时）出现的次数如下到达的病到达的病人数人数n出现次数出现次数fn0123456以上以上102829161061合合 计计1002517965为病人完成手术为病人完成手术时间时间v（小时）（小时）出现次数出现次数fv0.0-0.20.2-0.40.4-0.60.6-0.80.8-1.01.0-1.21.2以上以上380合合 计计10048)/( 1 . 2100)1(小时小时人人病人平均到达率病人平均到达率 nnf)/(4 . 0100人人

41、小小时时每每次次手手术术平平均均时时间间vvf)/(5 . 24 . 01小小时时人人平平均均服服务务率率）每每小小时时完完成成手手术术人人数数（ 0.842.52.1 5 . 2 , 1 . 2)2( 则则取取)(25. 51 . 25 . 21 . 2)3(人人 sL)( 1 . 21 . 25 . 284. 0小时小时qW)(5 . 21 . 25 . 21小时小时sW)(41. 425. 584. 0人人qL49假定系统最大容量为假定系统最大容量为N，单服务台情形，排队等待的顾客最，单服务台情形，排队等待的顾客最多为多为N-1，下面只考虑稳态情形：，下面只考虑稳态情形：二、二、M/M/

42、1/N/ 模型模型顾客到达顾客到达因队列满而离去因队列满而离去进入队列进入队列接受服务接受服务服务完毕后离去服务完毕后离去0N-112N-2N501 11011,)( NNnnnPPNnPPPPP 11 1 11n110NnPPNnN 解得：解得：0N-112N-2N51根据上式我们可以推导出系统的各项指标：根据上式我们可以推导出系统的各项指标：1 111L 1110s 其中其中）（）队长）队长（NNNnnNnP 11L 21q）（）（）队列长）队列长（osNnnPLPn 有效到达率有效到达率： 111 W30t ）（）（）顾客逗留时间）顾客逗留时间（NqsPLPL 1 W4q sW）顾客等待

43、时间）顾客等待时间（e=(1NP)e0=1P()52例例4 单人理发馆有六个椅子接待客人。当单人理发馆有六个椅子接待客人。当6个椅子个椅子都坐满时，后来的顾客不进店就离开。顾客平均到都坐满时，后来的顾客不进店就离开。顾客平均到达率为达率为3人人/小时，理发需时平均小时，理发需时平均15分钟。则：分钟。则： N=7为系统中最大的顾客数，为系统中最大的顾客数，=3=3人人/ /小时，小时，=4=4人人/ /小时小时（1）求某顾客一到达就能理发的概率。）求某顾客一到达就能理发的概率。2778.04/314/31P 80）（概概率率为为相相当当于于没没有有顾顾客客，所所求求（2）求需要等待的顾客数的期

44、望值。）求需要等待的顾客数的期望值。11. 2)4/3(1)4/3(84/314/3L88s39. 1)2778. 01(11. 2)1(L0qPLs53（3）求有效到达率。）求有效到达率。小时小时人人/89. 2)2778. 01(4)1(0e P分钟分钟小时小时8 .4373. 089. 2/11. 2/s esLW（4）求一顾客在理发馆内逗留的时间。）求一顾客在理发馆内逗留的时间。（5）在可能到达的顾客中有百分之几不等待就离开。）在可能到达的顾客中有百分之几不等待就离开。%7 . 3)43(1431()43()/(1/1()(87877 P54机器故障问题：设共有机器故障问题：设共有m台

45、机器，机器故障停机表台机器，机器故障停机表示到达，待修机器形成队示到达，待修机器形成队列，修理工是服务员。列，修理工是服务员。顾客总体虽然只有顾客总体虽然只有m个，个，但每个顾客服务后仍回到但每个顾客服务后仍回到总体，仍然可以到来。总体，仍然可以到来。三、顾客源有限的情形三、顾客源有限的情形(M/M/1/ /m)的含义发生改变的含义发生改变/: ( /) : m （）表示全体顾客的平均到达率表示全体顾客的平均到达率表示每个顾客的平均到达率表示每个顾客的平均到达率服务台服务台需要服务需要服务服务完毕服务完毕队列队列55系统外的平系统外的平均顾客数均顾客数 . )( )()()( )( , 0,/

46、)3(seLmnEmnEmEnmEmnmnnmm 故平均到达率故平均到达率（为什么？）（为什么？）（）：）：（与状态无关）；（与状态无关）；）：）：（实际进入率实际进入率 )P-(1)(0 seLm56说明：进入率与状态有关说明：进入率与状态有关 若若m=5,n=3; 如下图所示：如下图所示：系统中已经有两人丁和戊系统中已经有两人丁和戊进入的为甲、乙或丙，所以为：进入的为甲、乙或丙，所以为： e=357 1)( )1(mmnnnPPmnPm-nPPnmPPm 1-,1,1110由此列出平衡方程：由此列出平衡方程：状态概率状态概率0m-112m-2m(m-1)2m(m-2)3581 110111

47、 ,)() 1( mmnnnPPmnPnmPnmPPmP )n(1 P)( )!(! )()!(!1000mimmPimmPnnmni 解得：解得：59根据上式我们可以推导出系统的各项指标：根据上式我们可以推导出系统的各项指标： )P-(1L 10s m）（ )P-(1-L)1)(L 20s0q Pm）（ 1-)1(mW30sP ）（ 1 W4q sW）（在机器故障问题中在机器故障问题中Ls就是平均故障台数，而就是平均故障台数，而数数。表表示示正正常常运运转转的的平平均均台台 )P-(10 sLm60例例 5 某车间有某车间有5台机器，每台机器的连续运转时间服从负台机器，每台机器的连续运转时间

48、服从负指数分布，平均连续运转时间指数分布，平均连续运转时间15分钟，有一个修理工，每分钟，有一个修理工，每次修理时间服从负指数分布，平均每次次修理时间服从负指数分布，平均每次12分钟。分钟。求求 （1）修理工空闲的概率；）修理工空闲的概率；（2）五台机器都出故障的概率；）五台机器都出故障的概率；（3）出故障的平均台数；）出故障的平均台数；（4）等待修理的台数；）等待修理的台数；（5）平均停工时间；）平均停工时间；（6）平均等待时间；）平均等待时间；（7）评价这些结果。）评价这些结果。618 . 0/ 1/12, 1/15, , 5 m0073. 08 .136/1)8 . 0(! 0! 5)8

49、 . 0(! 1! 5)8 . 0(! 2! 5)8 . 0(! 3! 5)8 . 0(! 4! 5)8 . 0(! 5! 5P )1(15432100 287. 0)8 . 0(!0!5P )2(055 P)(76.3)0073.01(8 .015L )3(5台台 )(77.2993.076.3L )4(q台台 )(4615)007.01(1215 W)5(s分分钟钟 )(341246 W)6(q分分钟钟 （7） 机器停工时间过长，修理工几乎没有空闲时间，应机器停工时间过长，修理工几乎没有空闲时间，应当提高服务率减少修理时间或增加修理工人。当提高服务率减少修理时间或增加修理工人。62第四节第

50、四节 多服务台指数分布排队系统的分析多服务台指数分布排队系统的分析一、一、M/M/c.21 c相相同同独独立立且且平平均均分分配配服服务务率率规规定定各各服服务务台台工工作作相相互互服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列63。当当；为为当当务务率率为为整整个个服服务务机机构构的的平平均均服服)cnncnc (.,.1,率率或或服服务务机机构构的的平平均均利利用用这这个个系系统统的的服服务务强强度度称称它它为为列列时时才才不不会会排排成成无无限限的的队队只只有有当当令令 ccc)(n ) ( 1 ,) ( ) 1(11 1101 nnnnnnPcPPccnPnPPnPP。，且且这

51、这里里110 iiP0N12N-1c2ccc-1ccc+13(c-1)cc64用递推法解上述差分方程，可求得状态概率。用递推法解上述差分方程，可求得状态概率。 c)(n )(cc!1c)(n )(n!1 )( 11 !1)(k!10c-n0-1c-1c00PPPcPnnnkk解得：解得：c)(n ) ( 1 ,) ( ) 1(11 1101 nnnnnnPcPPccnPnPPnPP。，且且这这里里110 iiP65根据上式我们可以推导出系统的各项指标：根据上式我们可以推导出系统的各项指标：012qs1L L PccPcnLcncnq ）！（！（）（）（平均队长平均队长右边右边）（！）（因为因为

52、 0111PcccnPnPcncnnnncncnnssqLWL ，间间：平平均均等等待待时时间间和和逗逗留留时时q W66例例6 某售票所有三个窗口，顾客到达服从某售票所有三个窗口，顾客到达服从Passion过程，平过程，平均到达率每分钟均到达率每分钟=0.9(人人),服务服务(售票售票)时间服从负指数分布时间服从负指数分布,平平均服务率每分钟均服务率每分钟=0.4(人人).）符符合合要要求求的的公公式式。（。，型型的的系系统统，其其中中如如下下图图。是是一一个个购购票票，队队，依依次次向向空空闲闲的的窗窗口口现现设设顾顾客客到到达达后后排排成成一一1 325225. 23/ cccMM窗口窗

53、口(1)=0.4窗口窗口(2)=0.4窗口窗口(3)=0.4=0.967（1）整个售票所空闲的概率）整个售票所空闲的概率0748. 03/25. 211! 3)25. 2(! 2)25. 2(! 1)25. 2(! 0)25. 2(13210 P（2）平均队长）平均队长（3）平均等待时间和逗留时间）平均等待时间和逗留时间分钟分钟分钟分钟39. 44/189. 189. 190. 0/70. 1 sqWW（4）顾客到达后必须等待（即系统中顾客数已有）顾客到达后必须等待（即系统中顾客数已有3人）的概率人）的概率70. 10748. 0)4/1( ! 34/3)25. 2(23 qL57. 0074

54、8. 0)4/1( ! 3)25. 2()3(3 nP68二、二、M/M/c型系统和型系统和c个个M/M/1系统的比较系统的比较上例中，排队方式不变，但顾客到达后在每个窗口前各排上例中，排队方式不变，但顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，这就形成一队，且进入队列后坚持不换，这就形成3个队列，如下图个队列，如下图二每个队列平均到达率为二每个队列平均到达率为=0.9/3=0.3（每分钟），这（每分钟），这样原来的系统就变成样原来的系统就变成3个个M/M/1型的子系统。型的子系统。窗口窗口(1)=0.4窗口窗口(2)=0.4窗口窗口(3)=0.4=0.9=0.3=0.3=0.369

55、现按现按M/M/1型解决这个问题，并与上表比较：型解决这个问题，并与上表比较：模型模型指标指标服务台空闲的概率服务台空闲的概率顾客必须等待的概率顾客必须等待的概率平均队列平均队列平均队长平均队长平均逗留时间平均逗留时间平均等待时间平均等待时间（1）M/M/3型型（2）M/M/1型型0.0748P(n 3)=0.571.703.954.39(分钟分钟)1.89(分钟分钟)0.25(每个子系统每个子系统)0.752.25(每个子系统每个子系统)9.00(整个系统整个系统)10(分钟分钟)7.5(分钟分钟)从表中各指标的对比可以看出单队比三队有显著的优越性从表中各指标的对比可以看出单队比三队有显著的

56、优越性70三、系统容量有限定的三、系统容量有限定的M/M/c/N/ 模型模型服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列因队列满而离去因队列满而离去0N-112N-2c2cNcc-1ccc+13(c-1)cc71系统的状态概率和运行指标如下系统的状态概率和运行指标如下: N)n1(c c!cc)n(0 n!)(c 1 1)( !k!)(c10c0c0k0PPPccPnnnNckc加以限制现在不必对其中c,)1()1()(1 )1( !)(20NqscNcNcqPcLLcNccPL 1 W )1(s qNqqWPLWP72四、顾客源为有限的四、顾客源为有限的M/M/c/ /m模型模型顾

57、客到达顾客到达修理速率修理速率发生故障等待修理的机器发生故障等待修理的机器修理速率修理速率修理速率修理速率正在修理的机器正在修理的机器到达速率到达速率 (m-n)修理速率修理速率s运行的机器数运行的机器数 m-n730m-112m-2m(m-1)2c2cmcc-1(m-c+1)c稳态概率方程稳态概率方程mncPsnmcnPnnmPnnn1111 求得求得 N)n1(c )(cc!n)!-(mm!c)n(0 )(n!n)!-(m! )m( k)!-(m1 !)c(k)!-(mk!11!1 )1(0c -n0km1ckc00PPmPcmccmmPnnnkck 其中：其中：74 mcnnnnnPcn

58、nP1q1sL ,L 2）（）平均故障台数）平均故障台数（)( esLm 有效到达率有效到达率eqsessqeqLWLLmLL ，ssM );(L )3(75例例7 设有两个修理工人，负责设有两个修理工人，负责5台机器的正常运行，每台机台机器的正常运行，每台机器平均损坏的概率为每运转一小时器平均损坏的概率为每运转一小时1次，两个工人能以次，两个工人能以相同的平均修复率相同的平均修复率4（次（次/小时）修好机器。求小时）修好机器。求（1）等待修理的机器平均数）等待修理的机器平均数（2）需要修理的机器平均数）需要修理的机器平均数（3）有效损坏数）有效损坏数（4）等待修理时间）等待修理时间（5）停工

59、时间）停工时间1/4,/mc2,c /4)/1(5,m 小时），小时），（台（台，小时小时次次解解 0.3149 )81()81()81(! 21! 22)41(! 3 ! 21)41(! 41)41(! 51! 51154322100 P002. 0,018. 0,074. 0,197. 0,394. 054321 PPPPP76(1) Lq=P3+2P4+3P5=0.118(3) e=1(5-1.094)=3.906(4) Wq=0.118/3.906=0.03小时小时 (5) Ws=1.094/3.906=0.28小时小时094. 12 )2(101 PPcLnPLqmnns77第五节第

60、五节 一般服务时间一般服务时间M/G/1M/G/1模型模型一、一、M/G/1即：即：=ET 1TTE132Poisson12 方差均存在，且方差均存在，且服务时间的期望值和均服务时间的期望值和均分布；分布；服务时间服从一般独立服务时间服从一般独立分布；分布；的的顾客到达服从参数为顾客到达服从参数为基本条件：基本条件：.78 11212220 qqqqqWWLWLLLPPollaczek-Khinchine 公式公式qqssqsseqWLWLTEWWLL , L s 112 TTE注：服务时间是任意分布，上述注：服务时间是任意分布，上述PK公式仍然成立的；所以只要知道公式仍然成立的；所以只要知道