第八章排队论

1、第七章第七章连续时间马尔科夫过程连续时间马尔科夫过程 第七章第七章 连续时间马尔科夫过程连续时间马尔科夫过程 7.17.1、ItoIto过程过程7.27.2、增量过程、增量过程7.37.3、泊松过程、泊松过程7.47.4、排队论与生灭过程、排队论与生灭过程7.47.4、排队论与生灭过程、排队论与生灭过程 排队论（Queuing theory），又称随机服务系统，是通过研究各种服务系统在排队等待现象中的概率特性，解决服务系统最优设计与最优控制的一种理论。4排队论起源于20世纪初的电话通话。9091920年丹麦数学家、电气工程师爱尔朗（A.K.Erlang）用概率论方法研究电话通话问题，20世纪3

2、0年代，费勒(W.Feller)引进了生灭过程20世纪50年代，D.G.Kendall用嵌入马尔柯夫链方法研究排队论7.47.4、排队论与生灭过程、排队论与生灭过程7.47.4、排队论与生灭过程、排队论与生灭过程顾客要求的服务服务台1借书的学生2打电话3提货者4待降落的飞行器5储户6河水进入水库7购票旅客8十字路口的汽车借书通话提货降落存款、取款放水、调整水位购票通过路口图书管理员交换台仓库管理员指挥塔台储蓄窗口、ATM取款机水库管理员售票窗口红绿灯或交警排队系统的例子(1)单服务台单队单服务台单队图图7.4.1 单服务台单队系统单服务台单队系统 顾客到达顾客到达进入队列进入队列服务台服务台接

3、受服务接受服务顾客离去顾客离去7.47.4、排队论与生灭过程、排队论与生灭过程根据服务台的数量及排队方式，排队系统可以分为四类根据服务台的数量及排队方式，排队系统可以分为四类 (2)多服务台单队多服务台单队顾客到达顾客到达服务台服务台顾客离去顾客离去服务台服务台服务台服务台图图7.4.2 多服务台单队系统多服务台单队系统7.47.4、排队论与生灭过程、排队论与生灭过程根据服务台的数量及排队方式，排队系统可以分为四类根据服务台的数量及排队方式，排队系统可以分为四类 (3)多队多服务台多队多服务台图图7.4.3 多服务台多队系统多服务台多队系统顾客到达顾客到达服务台服务台顾客离去顾客离去服务台服务

4、台服务台服务台7.47.4、排队论与生灭过程、排队论与生灭过程根据服务台的数量及排队方式，排队系统可以分为四类根据服务台的数量及排队方式，排队系统可以分为四类 (4)多服务台串联服务多服务台串联服务 图图7.4.4 多服务台串联系统多服务台串联系统顾客到达顾客到达服务台服务台顾客离去顾客离去服务台服务台7.47.4、排队论与生灭过程、排队论与生灭过程根据服务台的数量及排队方式，排队系统可以分为四类根据服务台的数量及排队方式，排队系统可以分为四类 排队过程的组成部分排队过程的组成部分 实际中的排队系统各有不同，但概括起来都由三个基本部分组成： 输入过程、 排队及排队规则、 服务机制7.47.4、

5、排队论与生灭过程、排队论与生灭过程排队过程的组成部分排队过程的组成部分1、输入过程（1）顾客总体数，又称顾客源、输入源。顾客源可以是有限的，也可以是无限的。如到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的7.47.4、排队论与生灭过程、排队论与生灭过程排队过程的组成部分排队过程的组成部分1、输入过程、输入过程（1）顾客总体数，又称顾客源、输入源。顾客总体数，又称顾客源、输入源。（2）顾客到达的形式顾客到达的形式单个到达，还是成批到达。如大学生到图书馆借书是单个到达，而购买的材料入库则可以看成成批到达。7.47.4、排队论与生灭过程、排队论与生灭过程排队过程的组成部

6、分排队过程的组成部分1、输入过程、输入过程 顾客总体数，又称顾客源、输入源顾客总体数，又称顾客源、输入源 顾客到达的形式顾客到达的形式 顾客流的概率分布，即顾客流的概率分布，即单位时间内到达的顾客数单位时间内到达的顾客数，也可用也可用顾客相继到达的时间间隔顾客相继到达的时间间隔描述描述这是刻画输入过程的最重要的内容。排队论中常用的分布：定长分布(D)，这种分布顾客相继到达的时间间隔是确定的，如产品通过传送带进入包装箱就是定长分布的例子。泊松流(M), 在一定时间区间内，恰好到达k个顾客的概率仅与区间长度有关，而与区间起始时刻无关7.47.4、排队论与生灭过程、排队论与生灭过程排队过程的组成部分

7、排队过程的组成部分2、排队规则、排队规则 排队系统排队系统7.47.4、排队论与生灭过程、排队论与生灭过程排队分为有限排队和无限排队两类。前者是指系统的空间是有限的，当系统被占满时，后面再来的顾客将不能进入系统；后者是指系统中的顾客数可以是无限的，队列可以排到无限长，顾客到达后均可进入系统排队或接受服务。具体又分为： 等待制：等待制：即无限排队 损失制：损失制：这种系统是指排队空间为零的系统，实际上是不允许排队。当顾客到大系统时，如果所有服务台均被占用，则自动离去，并不再回来，这部分顾客就被损失掉了。 混合制混合制：该系统是等待制和损失制系统的结合，一般是指允许排队，但又不允许队列无限长下去排

8、队过程的组成部分排队过程的组成部分2、排队规则、排队规则 排队规则排队规则7.47.4、排队论与生灭过程、排队论与生灭过程先来先服务先来先服务(FCFS)后来先服务后来先服务(LCFS) ：在许多库存系统中会出现这种情形，如钢板存入仓库后，需要时总是从最上面的取出；又如在情报系统中，后来到达的信息往往更加重要，应首先加以分析和利用。 具有优先权的服务具有优先权的服务(PS)：如病危的患者应优先治疗，加急的电报电话应优先处理等随机服务随机服务(SIRO)排队过程的组成部分排队过程的组成部分3、服务机制、服务机制 服务员的数量及构成形式服务员的数量及构成形式7.47.4、排队论与生灭过程、排队论与

9、生灭过程从数量上说，服务台有单台和多台之分。从构成形式上看，有单队单服务台式、单队多服务台并联式、多队多服务台并联式、单队多服务台串联式等。排队过程的组成部分排队过程的组成部分3、服务机制、服务机制 服务员的数量及构成形式服务员的数量及构成形式7.47.4、排队论与生灭过程、排队论与生灭过程 服务方式服务方式指在某一时刻接受服务的顾客数，有单个服务和成批服务两种。排队过程的组成部分排队过程的组成部分3、服务机制、服务机制 服务员的数量及构成形式服务员的数量及构成形式7.47.4、排队论与生灭过程、排队论与生灭过程 服务方式服务方式 服务时间的分布服务时间的分布定长分布(D)指每个顾客接受服务的

10、时间是一个确定的常数。排队过程的组成部分排队过程的组成部分3、服务机制、服务机制 服务员的数量及构成形式服务员的数量及构成形式7.47.4、排队论与生灭过程、排队论与生灭过程 服务方式服务方式 服务时间的分布服务时间的分布定长分布(D)负指数分布(M)负指数概率分布能较好地描述一些排队系统里服务时间的概率分布情况。在负指数分布里，服务时间小于或等于时间长度t的概率：F（t）=P（服务时间t）=1-e-t这里的为单位时间里被服务完的平均顾客数。排队过程的组成部分排队过程的组成部分3、服务机制、服务机制 服务员的数量及构成形式服务员的数量及构成形式7.47.4、排队论与生灭过程、排队论与生灭过程

11、服务方式服务方式 服务时间的分布服务时间的分布定长分布(D)负指数分布(M)K阶爱尔朗分布1()( )0(1)!kk tkk tf tetkK阶爱尔朗分布阶爱尔朗分布 设X1，X2，Xk是k个互相独立的，具有相同参数的负指数分布随机变量，则随机变量：X=X1+X2+X3+Xk 服从k阶爱尔朗分布，X的密度函数为： 随机变量X的均值和方差分别为： E(X)=1/，Var(X)=1/k2 如果顾客连续接受串联的k个服务台的服务，各服务台的服务时间相互独立，且均服从参数为的负指数分布，则顾客接受k个服务台总共所需的时间就服从k阶爱尔朗分布。7.47.4、排队论与生灭过程、排队论与生灭过程 当一个排队

12、服务系统开始运转时，系统状态很大程度上取决于系统的初始状态和运转经历的时间，但过了一段时间后，系统的状态将独立于初始状态及经历的时间，这时称系统处于平稳状态。由于对系统的瞬时状态研究分析起来很困难，所以排队论中主要研究系统处于平稳状态的工作情况。排队过程的平稳状态排队过程的平稳状态7.47.4、排队论与生灭过程、排队论与生灭过程 X/Y/Z/A/B/C 这里的X记顾客相继到达的时间间隔的分布，M表示服从泊松分布或负指数分布，D表示定长分布，Ek表示爱尔朗分布，G表示一般相互独立任意分布； Y记服务时间的分布，类型同X； Z记服务台数目，取正整数； A记系统的容量，表示系统中顾客容量限额，若系统

13、中有k个等待位子(0k=0具有具有马马 尔可夫性质尔可夫性质, , 为为一个生灭过程一个生灭过程.7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）设某系统具有状态集设某系统具有状态集S=0,1,2,或或S=0,1,2,k,N(t)表示系统在时刻表示系统在时刻 t (t=0) 的状态。的状态。若在若在N(t)=n的条件下的条件下,随随机过程机过程N(t),t=0满足以下条件满足以下条件: (1) N(t+ t)转移到转移到“n+1”的概率为的概率为Pn,n+1( t )=n t ; (2) N(t+ t)转移到转移到“n-1”的概率为的概率为Pn,n-1(

14、t )= n t ); (3) N(t+ t)转移到其他状态转移到其他状态“S-n+1,n-1”的概的概 率为率为o( t )(高阶无穷小高阶无穷小) ;则称则称随机过程随机过程N(t),t=0为为生灭过程生灭过程。Definition 7.2(Birth-death process)7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论） (1) 在无穷小在无穷小 t内内,系统或生长系统或生长1个个;或灭亡或灭亡1个个;或既或既 不生长又不灭亡不生长又不灭亡的概率的概率: 1- n( t ) -n( t ); (2)系统生长一个的概率系统生长一个的概率n( t

15、)与与 t有关，而与有关，而与t无无 关关; 与系统当前状态与系统当前状态n有关，而与以前的状态无关；有关，而与以前的状态无关； (3)系统灭亡一个的概率系统灭亡一个的概率n( t )与与 t有关，而与有关，而与t无无 关关; 与系统当前状态与系统当前状态n有关，而与以前的状态无关；有关，而与以前的状态无关；马尔可夫性马尔可夫性生灭过程生灭过程状态变化的性质状态变化的性质7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）生灭过程的生灭过程的状态平衡方程状态平衡方程0011PP1112200)P(PP1223311)P(PP1 -n1 -n1 -nnn2-n2

16、n)P(PPnnn1n1n1-n1)P(PPn状态状态输入率输入率=输出率输出率012n-1n7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）生灭过程的生灭过程的跳跃强度矩阵跳跃强度矩阵0011112222333310000000()0000000()0000000()000000000. .00000000mmmQ7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）生灭过程的生灭过程的状态转移图状态转移图 无限状态的： m个状态的：2103i-1i01122334i2i-1i1iii+1210m-1m3i01122334

17、i1iii+1m2m-1m1m7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）排队系统状态转移图排队系统状态转移图012nn-10122n1nn1231nn1n在任意状态在任意状态n达到稳态平衡的条件：达到稳态平衡的条件： 产生该状态的平均速率产生该状态的平均速率 =该状态转变成其他状态的平均速率该状态转变成其他状态的平均速率 （流入（流入=流出）流出）012nn-10122n1nn1231nn1n0011pp012nn-10122n1nn1231nn1n2223311)(ppp012nn-10122n1nn1231nn1n11122)(nnnnnnnpp

18、p012nn-10122n1nn1231nn1nnnnnnnnppp)(111101011020211210012112100121,1, 2,nnnnnnnnnnnnppppppCpC pn ，记， 则，生灭过程的生灭过程的稳态概率稳态概率1100110001,111)1 (1nnnnnnnnnnnnCCpCppCpCpp 一般来说，得到N(t)的分布的分布Pn(t)=PN(t)=n,n=0,1,2,是比较困难的，因此是比较困难的，因此通常是求当系统运行一段时间达到平稳状态后的通常是求当系统运行一段时间达到平稳状态后的状态分布，记为状态分布，记为Pn。 当系统运行长时间达到平稳状态后，对于任

19、一个当系统运行长时间达到平稳状态后，对于任一个状态状态n，单位时间内进入该状态的平均次数和单，单位时间内进入该状态的平均次数和单位时间离开该状态的平均次数应该相等，这就是位时间离开该状态的平均次数应该相等，这就是系统的统计平衡下的系统的统计平衡下的“流入流入=流出流出”原理。原理。7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）2. 2. 生灭过程稳态方程生灭过程稳态方程 1,)(11110011npppppnnnnnnn 11010101nPPPnnn输入（出）率=某一稳态概率平均转换率2. 2. 生灭过程稳态方程生灭过程稳态方程 1,)(1111001

20、1npppppnnnnnnn 11010101nPPPnnn方程为：方程为：由此可求得生灭过程的平稳状态分布：由此可求得生灭过程的平稳状态分布：10nnP110 nPPP10101012010100 PPPXPnn1100101 nnnP由于由于即有即有即有即有即有即有7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论） 1001nnn即当即当时，此生灭过程存在平稳状态分布：时，此生灭过程存在平稳状态分布：110010120011113 1,1,2,nnnnnnnnPPP n 7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论

21、）基于生灭过程的排队系统的六个模型3. M/M/1/m/FCFS （单服务台无限队列）到达过程/服务时间/系统容量/顾客源/排队规则1. M/M/1/FCFS（单服务台无限队列）2. M/M/1/N/FCFS （单服务台无限队列）5. M/M/s/N/FCFS4. M/M/s/FCFS6. M/M/s/m/FCFS7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）设单位时间到达系统的顾客数为设单位时间到达系统的顾客数为 ，单位时间被服务完的顾客，单位时间被服务完的顾客数为数为。由于是单服务台，且顾客源无限，因此，在各种状态。由于是单服务台，且顾客源无限，因此

22、，在各种状态的情况下，系统的的情况下，系统的“出生率出生率”为为，系统的，系统的“死亡率死亡率”为为。系统在稳态情况下的状态转移如图系统在稳态情况下的状态转移如图9-6所示所示 0 1 2n-1 nn+1P0 P1 P2 Pn-1 Pn Pn+1 图图9-6/1/MMFCFS 单服务台排队系统模型之一：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）根据以上状态转移图，可以得出如下平衡方程根据以上状态转移图，可以得出如下平衡方程 系统状态概率系统状态概率Pn(t)的计算的计算/1/MMFCFS 单服务台排队系统模型之一：10PP021PP()P131PP(

23、Pn-2nn-1PP()Pn-1n 1nPP()P状态状态输入率输入率=输出率输出率012n-1n7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）根据平衡方程，可递推得到各状态概率为：根据平衡方程，可递推得到各状态概率为： 系统状态概率系统状态概率Pn(t)的计算的计算/1/MMFCFS 单服务台排队系统模型之一：状态状态概率012n-1n10(PP )22010(1)(PPPP )0(nnPP )00PP7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）1设210200,nnPP PPPP01nnP由，有20000.1

24、nPPPP20(1.)1nP20(1.)1nP 上面两式做差，得01 1P 10P(1)nnP 表示平均到达率与平均服务率之比，称为服务强度表示平均到达率与平均服务率之比，称为服务强度 系统状态概率系统状态概率Pn(t)的计算的计算/1/MMFCFS 单服务台排队系统模型之一：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）根据平衡方程，可递推得到各状态概率为：根据平衡方程，可递推得到各状态概率为： 系统状态概率系统状态概率Pn(t)的计算的计算/1/MMFCFS 单服务台排队系统模型之一：状态状态概率012n-1n1(1)P 22(1)P (1)nnP

25、01P 7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）高速公路收费处设有一个收费通道，汽车到达服从泊松分布，高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为平均到达速率为150辆小时，收费时间服从负指数分布，平均辆小时，收费时间服从负指数分布，平均收费时间为收费时间为15秒辆。求秒辆。求(4)系统中的平均顾客数（系统中顾客数的期望值）系统中的平均顾客数（系统中顾客数的期望值）Ls (5)队列中的平均顾客数（等待）队列中的平均顾客数（等待）(6)服务中的平均顾客数服务中的平均顾客数(7)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时

26、间W(8)顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间 Wq(1)收费处空闲的概率；收费处空闲的概率；(2)收费处忙的概率；收费处忙的概率；(3)系统中分别有系统中分别有1，2，3辆车的概率辆车的概率7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMFCFS 单服务台排队系统模型之一：根据题意根据题意, =150辆辆/小时小时, 1/=15秒秒=1/240（小时（小时/辆）辆）,即即240（辆（辆/小时）小时）/=150/240=5/8，高速公路收费处设有一个收费通道，汽车到达服从泊松分布，高速公路收费处设有一个收费通道，汽车到达服从泊松分

27、布，平均到达速率为平均到达速率为150辆小时，收费时间服从负指数分布，平均辆小时，收费时间服从负指数分布，平均收费时间为收费时间为15秒辆。求秒辆。求7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）高速公路收费处设有一个收费通道，汽车到达服从泊松分布，高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为平均到达速率为150辆小时，收费时间服从负指数分布，平均辆小时，收费时间服从负指数分布，平均收费时间为收费时间为15秒辆。求秒辆。求(1)系统空闲的概率为：系统空闲的概率为： P0=1=1(5/8)=3/8=0.3757.47.4、排队论与生

28、灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMFCFS 单服务台排队系统模型之一：(2)系统忙的概率为：系统忙的概率为：1-P0=5/8=0.625高速公路收费处设有一个收费通道，汽车到达服从泊松分布，高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为平均到达速率为150辆小时，收费时间服从负指数分布，平均辆小时，收费时间服从负指数分布，平均收费时间为收费时间为15秒辆。求秒辆。求7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMFCFS 单服务台排队系统模型之一：(3)系统中有系统中有1辆车的概率为：辆

29、车的概率为：高速公路收费处设有一个收费通道，汽车到达服从泊松分布，高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为平均到达速率为150辆小时，收费时间服从负指数分布，平均辆小时，收费时间服从负指数分布，平均收费时间为收费时间为15秒辆。求秒辆。求P1=(1)=0.6250.375=0.234P2= 2(1)= 0.2340.625=0.146 P3=3(1)=0.1460.625=0.091系统中有系统中有3辆车的概率为：辆车的概率为：系统中有系统中有2辆车的概率为：辆车的概率为：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/M

30、MFCFS 单服务台排队系统模型之一：(4)系统中的平均顾客数（系统中顾客数的期望值）系统中的平均顾客数（系统中顾客数的期望值）Ls 0002(1)(1)(1)(1)11kkskkkkLkPkk 即即队长为系统中顾客数的期望值队长为系统中顾客数的期望值（系统中各种状态的加权平均值）（系统中各种状态的加权平均值） 高速公路收费处设有一个收费通道，汽车到达服从泊松分布，高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为平均到达速率为150辆小时，收费时间服从负指数分布，平均辆小时，收费时间服从负指数分布，平均收费时间为收费时间为15秒辆。求秒辆。求7.47.4、排队论与生灭过程、

31、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMFCFS 单服务台排队系统模型之一：(5)队列中的平均顾客数（等待）队列中的平均顾客数（等待）1111220(1)()(1)11()qkkkkkkkkkLkPkPPkPPLPL 高速公路收费处设有一个收费通道，汽车到达服从泊松分布，高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为平均到达速率为150辆小时，收费时间服从负指数分布，平均辆小时，收费时间服从负指数分布，平均收费时间为收费时间为15秒辆。求秒辆。求7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMFCFS

32、 单服务台排队系统模型之一：57(6)服务中的平均顾客数服务中的平均顾客数f01230L0 P1P P P1 P11/ （）（）高速公路收费处设有一个收费通道，汽车到达服从泊松分布，高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为平均到达速率为150辆小时，收费时间服从负指数分布，平均辆小时，收费时间服从负指数分布，平均收费时间为收费时间为15秒辆。求秒辆。求7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMFCFS 单服务台排队系统模型之一：(7)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间W1()sWE X7.47.

33、4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）高速公路收费处设有一个收费通道，汽车到达服从泊松分布，高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为平均到达速率为150辆小时，收费时间服从负指数分布，平均辆小时，收费时间服从负指数分布，平均收费时间为收费时间为15秒辆。求秒辆。求/1/MMFCFS 单服务台排队系统模型之一：(8)顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间 Wq111()()()qssWWW 7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）高速公路收费处设有一个收费通道，汽车到达服

34、从泊松分布，高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为平均到达速率为150辆小时，收费时间服从负指数分布，平均辆小时，收费时间服从负指数分布，平均收费时间为收费时间为15秒辆。求秒辆。求/1/MMFCFS 单服务台排队系统模型之一：60(6)服务中的平均顾客数服务中的平均顾客数 Lf=0P0+1（P1+ P2+ P3+）=1-P0=1-（1-）= =/1ssqqffsqsqqLWLWLWWWLLLLittle公式公式: 7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMFCFS 单服务台排队系统模型之一：61(6)服务中的

35、平均顾客数服务中的平均顾客数 Lf=0P0+1（P1+ P2+ P3+）=1-P0=1-（1-）= =/1ssqqffsqsqqLWLWLWWWLLLLittle公式公式: 7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMFCFS 单服务台排队系统模型之一：【例例9.2】轻轨进站口售票处设有一个售票窗口，乘客到达服从轻轨进站口售票处设有一个售票窗口，乘客到达服从泊松分布，平均到达速率为泊松分布，平均到达速率为200人人/小时，售票时间服从负指数小时，售票时间服从负指数分布，平均售票时间为分布，平均售票时间为15秒秒/人。求人。求L、Lq、W和和W

36、q。【解解】根据题意，根据题意，=200人人/小时，小时，=240人人/小时，小时，=5/6。 )(7590)(90)(025. 02002401117. 4551165656565秒秒小时WWWLLLqq 如果系统的最大容量为如果系统的最大容量为N，对于单服务台的情形，排队等待，对于单服务台的情形，排队等待的顾客最多为的顾客最多为N-1-1，在某一时刻一顾客到达时，如系统中已有，在某一时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。系统状态转移如个顾客，那么这个顾客就被拒绝进入系统。系统状态转移如图图9-7 0 1 2N-1 NP0 P1 P2 图图97/1/MMNFC

37、FS单服务台排队系统模型之二：根据平衡方程，可递推得到各状态概率为：根据平衡方程，可递推得到各状态概率为： 系统状态概率系统状态概率Pn(t)的计算的计算状态状态概率012nN10PP201(1)PPP )00PP7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMNFCFS单服务台排队系统模型之二：11()nnnPPP1NNPP根据平衡方程，可递推得到各状态概率为：根据平衡方程，可递推得到各状态概率为： 系统状态概率系统状态概率Pn(t)的计算的计算状态状态概率012nN11(1) (1)NP212(1) (1)NP1(1) (1)NNNP7.47

38、.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）(1) 10(1) (1)NP1(1) (1)nNnP/1/MMNFCFS单服务台排队系统模型之二：根据平衡方程，可递推得到各状态概率为：根据平衡方程，可递推得到各状态概率为： u系统状态概率系统状态概率Pn(t)的计算的计算/1/MMFCFS 单服务台排队系统模型之一：状态状态概率012nN11 (1)PN21 (1)PN1 (1)NPN7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）(1)01 (1)PN1 (1)nPN100111211111(1)(1)111(1)11NN

39、kkNkkNNNNNLkPkNNu系统中的平均顾客数系统中的平均顾客数L7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMNFCFS单服务台排队系统模型之二：000011111111(1)(1)1111111()(1)111(1)(1)NNNqkkkkkkNNNNNNNNNNNNNLkPkPPLPLLLLLPLPLu队列中的平均顾客数队列中的平均顾客数Lq7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMNFCFS单服务台排队系统模型之二：u队列中的平均顾客数队列中的平均顾客数Lq7.47.4、排队论与

40、生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）在我们的有限容量模型中，每单位时间平均有名到达者到达，但是这些到达者中有PN的概率不能进入系统，因为此时系统已满，所以有 PN名到达者无法进入系统而离开。(1),eeNeP令e 称为有效到达率，即单位时间内到达并能进入队列的平均顾客称为有效到达率，即单位时间内到达并能进入队列的平均顾客数。数。e 称为有效服务强度称为有效服务强度 。对于有限容量系统，即使。对于有限容量系统，即使，系，系统的有限容量也会阻止系统中的人数爆炸，稳态存在。统的有限容量也会阻止系统中的人数爆炸，稳态存在。/1/MMNFCFS单服务台排队系统模型之二：)1

41、(NePLLWu顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间 11WLLLWeeeeqqu顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间W7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/1/MMNFCFS单服务台排队系统模型之二：咨询中心有一位咨询工作人员，每次只能咨询一人，另外有咨询中心有一位咨询工作人员，每次只能咨询一人，另外有4个个座位供前来咨询的人等候。某人到来发现没有座位，就不再等待座位供前来咨询的人等候。某人到来发现没有座位，就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速率为而离去。前来咨询者到达服从泊松流，到达的平均

42、速率为4人人/小小时，咨询人员的平均咨询时间为时，咨询人员的平均咨询时间为10分钟分钟/人。咨询时间服从负指人。咨询时间服从负指数分布。求：数分布。求：(1)咨询者到达不用等待就可咨询的概率咨询者到达不用等待就可咨询的概率(2)咨询中心的平均人数以及等待咨询的平均人数咨询中心的平均人数以及等待咨询的平均人数(3)咨询者来咨询中心一次平均花费的时间以及平均等待的时间咨询者来咨询中心一次平均花费的时间以及平均等待的时间(4)咨询者到达后因客满而离去的概率咨询者到达后因客满而离去的概率(5)增加一个座位可以减少的顾客损失率增加一个座位可以减少的顾客损失率7.47.4、排队论与生灭过程、排队论与生灭过

43、程-（生灭过程排队论）（生灭过程排队论）/1/MMNFCFS单服务台排队系统模型之二：【解解】N=4+1=5，=4人人/小时，小时，=6人人/小时，小时，=2/3 2307123110.36511NP 5203(1)(1)410.3653.808NeNPP咨询中心有一位咨询工作人员，每次只能咨询一人，另外有咨询中心有一位咨询工作人员，每次只能咨询一人，另外有4个个座位供前来咨询的人等候。某人到来发现没有座位，就不再等待座位供前来咨询的人等候。某人到来发现没有座位，就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速率为而离去。前来咨询者到达服从泊松流，到达的平均速率为4人人/小小时，咨询人

44、员的平均咨询时间为时，咨询人员的平均咨询时间为10分钟分钟/人。咨询时间服从负指人。咨询时间服从负指数分布。求：数分布。求：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）(1)咨询者到达不用等待就可咨询的概率咨询者到达不用等待就可咨询的概率/1/MMNFCFS单服务台排队系统模型之二：咨询中心有一位咨询工作人员，每次只能咨询一人，另外有咨询中心有一位咨询工作人员，每次只能咨询一人，另外有4个个座位供前来咨询的人等候。某人到来发现没有座位，就不再等待座位供前来咨询的人等候。某人到来发现没有座位，就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速率为而

45、离去。前来咨询者到达服从泊松流，到达的平均速率为4人人/小小时，咨询人员的平均咨询时间为时，咨询人员的平均咨询时间为10分钟分钟/人。咨询时间服从负指人。咨询时间服从负指数分布。求：数分布。求：/1/MMFCFS 单服务台排队系统模型之一：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论） 423. 1577. 021) 15(11) 1(1632632323211NNNL788. 06808. 3423. 1eqLL(2)咨询中心的平均人数以及等待咨询的平均人数咨询中心的平均人数以及等待咨询的平均人数咨询中心有一位咨询工作人员，每次只能咨询一人，另外有咨询

46、中心有一位咨询工作人员，每次只能咨询一人，另外有4个个座位供前来咨询的人等候。某人到来发现没有座位，就不再等待座位供前来咨询的人等候。某人到来发现没有座位，就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速率为而离去。前来咨询者到达服从泊松流，到达的平均速率为4人人/小小时，咨询人员的平均咨询时间为时，咨询人员的平均咨询时间为10分钟分钟/人。咨询时间服从负指人。咨询时间服从负指数分布。求：数分布。求：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）(3)咨询者来咨询中心一次平均花费的时间以及平均等待的时间咨询者来咨询中心一次平均花费的时间以及平均等

47、待的时间)(4 .22)(374. 0808. 3423. 1分小时 eLW0.7880.207()12.4()3.808qqeLW小时分/1/MMNFCFS单服务台排队系统模型之二： 5525030.3650.048PP咨询中心有一位咨询工作人员，每次只能咨询一人，另外有咨询中心有一位咨询工作人员，每次只能咨询一人，另外有4个个座位供前来咨询的人等候。某人到来发现没有座位，就不再等待座位供前来咨询的人等候。某人到来发现没有座位，就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速率为而离去。前来咨询者到达服从泊松流，到达的平均速率为4人人/小小时，咨询人员的平均咨询时间为时，咨询人员的平

48、均咨询时间为10分钟分钟/人。咨询时间服从负指人。咨询时间服从负指数分布。求：数分布。求：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）(4)咨询者到达后因客满而离去的概率咨询者到达后因客满而离去的概率/1/MMNFCFS单服务台排队系统模型之二： 当当N=6时时 2307123110.35411NP咨询中心有一位咨询工作人员，每次只能咨询一人，另外有咨询中心有一位咨询工作人员，每次只能咨询一人，另外有4个个座位供前来咨询的人等候。某人到来发现没有座位，就不再等待座位供前来咨询的人等候。某人到来发现没有座位，就不再等待而离去。前来咨询者到达服从泊松流，到

49、达的平均速率为而离去。前来咨询者到达服从泊松流，到达的平均速率为4人人/小小时，咨询人员的平均咨询时间为时，咨询人员的平均咨询时间为10分钟分钟/人。咨询时间服从负指人。咨询时间服从负指数分布。求：数分布。求：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）(5)增加一个座位可以减少的顾客损失率增加一个座位可以减少的顾客损失率 6626030.3650.032PP560.0480.0320.0161.6%PP即增加一个座位可以减少顾客损失率即增加一个座位可以减少顾客损失率1.6% /1/MMNFCFS单服务台排队系统模型之二：有限顾客源排队系统模型有限顾客

50、源排队系统模型 在无限源顾客系统中，顾客的平均到达速率在无限源顾客系统中，顾客的平均到达速率是整个顾客是整个顾客源的性质，与单独的顾客无关。源的性质，与单独的顾客无关。即使有顾客反复接受服务，即使有顾客反复接受服务，对于本来就是无穷大的顾客源影响不大。对于本来就是无穷大的顾客源影响不大。/1/MMm FCFS单服务台排队系统模型之三：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）在有限源系统中，由于一个顾客要反复接受服务，因此有在有限源系统中，由于一个顾客要反复接受服务，因此有必要假定每一个顾客在单位时间内需要接受服务的平均次必要假定每一个顾客在单位时间

51、内需要接受服务的平均次数是相同的，设为数是相同的，设为。这样，。这样，有限源系统顾客的平均到达有限源系统顾客的平均到达速率就与顾客源中的顾客数有关。速率就与顾客源中的顾客数有关。 设顾客总数为设顾客总数为m。当顾客需要服务时，就进入队列等待；。当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中，如此循环往复。由于顾服务完毕后，重新回到顾客源中，如此循环往复。由于顾客源的数量有限，因此队列的长度也是有限的，并且队列客源的数量有限，因此队列的长度也是有限的，并且队列的长度必定小于顾客源总数的长度必定小于顾客源总数 。 78 以机器维修问题为例，设机器总数为以机器维修问题为例，设机器总数

52、为m台，每台机器在单位台，每台机器在单位时间内发生故障的平均次数为时间内发生故障的平均次数为，已经发生故障正在等待修，已经发生故障正在等待修理及正在接受修理的机器数为理及正在接受修理的机器数为n。试想，。试想，由于机器需要反复由于机器需要反复修理，所以可以把单位时间内需要修理的机器总数看成是一修理，所以可以把单位时间内需要修理的机器总数看成是一共共m 台（一台只修理一次），其中有台（一台只修理一次），其中有n 台在系统中，所以台在系统中，所以单位时间内将要到达的机器数（剩余的）可以看成（单位时间内将要到达的机器数（剩余的）可以看成（m - n ）台。）台。)(nme 有限源系统顾客的平均到达速

53、率：有限源系统顾客的平均到达速率：为每个顾客在单位时为每个顾客在单位时间内到达的平均次数，间内到达的平均次数， n为在系统中的顾客数。为在系统中的顾客数。有限顾客源排队系统模型有限顾客源排队系统模型 /1/MMm FCFS单服务台排队系统模型之三：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）有限顾客源排队系统模型有限顾客源排队系统模型 /1/MMm FCFS单服务台排队系统模型之三：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论） 0 1 2n-1 nm(1)m(1)mnn+1m-1 m()mn图图9-8 有限顾客

54、源模型状态转移图有限顾客源模型状态转移图状态转移图如图状态转移图如图9-8 由图由图9-8得到系统稳态概率平衡方程组得到系统稳态概率平衡方程组 u系统状态概率的计算系统状态概率的计算10111(1)(), 11nnnmmPm PPmnPmnPnmPP/1/MMm FCFS单服务台排队系统模型之三：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）用递推方法解该方程组，得到用递推方法解该方程组，得到 miiimmP00)!(!10)!(!PnmmPnn不要求=/s时，因服务台有限，系统的服务速率达最大为s。规定各服务台工作相互独立且服务速率相同规定各服务台工作

55、相互独立且服务速率相同 12sn系统的平均服务速率为系统的平均服务速率为 ss令令 0 1 2s-1 s2ssss+1n-1 n(1)s图图9-9 基本模型状态转移图基本模型状态转移图系统的状态转移图系统的状态转移图9-9。/ /MMsm FCFS多服务台排队系统模型之一：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）稳态概率方程稳态概率方程 10PP120)(2PPPsssPsPsP)(11nnnPsPsP)(1111nnP由由解得：解得： 110011!1!ssnnnsnPsnPsssnPnPsnnnnnn00!1!7.47.4、排队论与生灭过程、排

56、队论与生灭过程-（生灭过程排队论）（生灭过程排队论）u系统状态概率的计算系统状态概率的计算/ /MMsm FCFS多服务台排队系统模型之一：u系统中的平均顾客数系统中的平均顾客数Lu队列中的平均顾客数队列中的平均顾客数Lqu顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间 u顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间W7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）20)1 ( !sPLssqqLLLW qqLW u顾客需要等待顾客需要等待 (系统已有系统已有s个顾客个顾客)的概率的概率00()()!(1)!(1)ssnn sPsP nsPP

57、ss/ /MMsm FCFS多服务台排队系统模型之一：银行办理个人储蓄业务有三个窗口，顾客到达服从泊松流，到达银行办理个人储蓄业务有三个窗口，顾客到达服从泊松流，到达速率为速率为0.9人分，办理业务时间服从负指数分布，每个窗口的人分，办理业务时间服从负指数分布，每个窗口的平均服务速率为平均服务速率为0.4人分。顾客到达后取得一个排队号，依次人分。顾客到达后取得一个排队号，依次由空闲窗口按号码顺序办理储蓄业务。求：由空闲窗口按号码顺序办理储蓄业务。求：(1)所有窗口都空闲的概率；所有窗口都空闲的概率；(2)平均队长；平均队长；(3)平均等待时间及逗留时间；平均等待时间及逗留时间；(4)顾客到达后

58、必须等待的概率。顾客到达后必须等待的概率。7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/ /MMsm FCFS多服务台排队系统模型之一：【解解】这是一个这是一个/ : 3/FCFSMM系统系统/2.25,/0.75s (1)所有窗口都空闲的概率；所有窗口都空闲的概率；即求即求P00748. 075. 011! 3)25. 2(! 2)25. 2(! 1)25. 2(! 0)25. 2(132100P7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/ /MMsm FCFS多服务台排队系统模型之一：银行办理个人储蓄业务

59、有三个窗口，顾客到达服从泊松流，到达银行办理个人储蓄业务有三个窗口，顾客到达服从泊松流，到达速率为速率为0.9人分，办理业务时间服从负指数分布，每个窗口的人分，办理业务时间服从负指数分布，每个窗口的平均服务速率为平均服务速率为0.4人分。顾客到达后取得一个排队号，依次人分。顾客到达后取得一个排队号，依次由空闲窗口按号码顺序办理储蓄业务。求：由空闲窗口按号码顺序办理储蓄业务。求：7.47.4、排队论与生灭过程、排队论与生灭过程-（生灭过程排队论）（生灭过程排队论）/ /MMsm FCFS多服务台排队系统模型之一：银行办理个人储蓄业务有三个窗口，顾客到达服从泊松流，到达银行办理个人储蓄业务有三个窗

60、口，顾客到达服从泊松流，到达速率为速率为0.9人分，办理业务时间服从负指数分布，每个窗口的人分，办理业务时间服从负指数分布，每个窗口的平均服务速率为平均服务速率为0.4人分。顾客到达后取得一个排队号，依次人分。顾客到达后取得一个排队号，依次由空闲窗口按号码顺序办理储蓄业务。求：由空闲窗口按号码顺序办理储蓄业务。求：(2)平均队长；平均队长；先求先求Lq ,再求再求L95. 325. 270. 170. 10748. 0)75. 01 (! 375. 0)25. 2(23qqLLL(3)平均等待时间和平均逗留时间，平均等待时间和平均逗留时间，即求即求Wq和和W的值的值 )(39. 44 . 01