第九章 排队论

1、第九章第九章 排队论排队论 Queuing Theory排队论(Queuing TheoryQueuing Theory)，又称随机服务系统理论（Random Service System Theory），是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。主要内容：1、排队论的基本概念 排队系统的3个部分、模型表示、数量指标2、单服务台排队模型（负指数分布） 标准的M/M/1或M/M/1/ 系统容量有限制的情形 M/M/1/N/ 顾客源为有限的情形 M/M/1/m 3、多服务台排队模型（负指数分布） 标准的 M

2、/M/c或M/M/c/ 重点、难点背景：日常生活中存在大量有形和无形的排队或拥挤现象，如旅客购票排队，市内电话占线等现象, 电话局的占线问题，车站、码头等交通枢纽的堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机性，可以说排队现象几乎是不可避免的。随着排队问题而产生的就是拥挤现象。- 造成整个社会效率的损失。 如何避免或减少排队时间？人们总是希望尽量设法减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。于是，顾客排队时间

3、的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。排队论提供了既保证一定的服务质量，又使服务设施费用经济合理的方法。排队论研究的问题排队论研究的问题排 队 论 是 1 9 0 9 年 由 丹 麦 工 程 师 爱 尔 朗(A.K.Erlang)在研究电话系统时创立的。几十年来排队论的应用领域越来越广泛，理论也日臻完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。排队论的创立和发展排队论的创立和发展9.1 排队论的基本概念9.1.1 排队系统的描述排队系统的例子顾客顾客要求的服务要求的服务服务机构服务机构1借书的学生借书的学生2打电话打电话

4、3提货者提货者4待降落的飞行器待降落的飞行器5储户储户6河水进入水库河水进入水库7购票旅客购票旅客8十字路口的汽车十字路口的汽车9.不能运转的机器不能运转的机器10.来到路口的汽车来到路口的汽车借书借书通话通话提货提货降落降落存款、取款存款、取款放水、调整水位放水、调整水位购票购票通过路口通过路口修理修理通过路口通过路口图书管理员图书管理员交换台交换台仓库管理员仓库管理员指挥塔台指挥塔台储蓄窗口、储蓄窗口、ATMD取款机取款机水库管理员水库管理员售票窗口售票窗口红绿灯或交警红绿灯或交警修理技工修理技工交通管理员或红绿灯交通管理员或红绿灯排队过程可表示为：根据服务台的数量及排队方式，排队系统可以

5、分为 (1)单服务台单队(2)多服务台单队图9-2单服务台单队系统 顾客到达进入队列服务台接受服务顾客离去顾客到达服务台顾客离去服务台服务台图9-3 多服务台单队系统银行银行、(3)多队多服务台(4)多服务台串联服务 图9-4 多服务台多队系统图9-5 多服务台串联系统顾客到达服务台顾客离去服务台服务台顾客到达服务台顾客离去服务台超市结账、学校餐厅就餐.医院体检.9.1.2 排队系统的基本组成排队系统由输入过程、排队规则和服务台三个部分组成 这是指要求服务的顾客按怎样的规律到达排队系统的过程，有时也称之为顾客流。（1）顾客总体数，又称顾客源、输入源。顾客源可以是有限的，也可以是无限的。（2）顾

6、客到达的形式。这是描述顾客是怎样来到系统的，是单个到达，还是成批到达。（3）顾客流的概率分布，或称顾客相继到达的时间间隔分布。这是首先需要确定的指标。（4）顾客的到达可以是相互独立的，1.输入过程(1)先到先服务（FCFS，First Come First Serve）；(2)后到先服务（LCFS，Last Come First Serve）；（仓库中叠放 的钢材）(3)有优先权的服务（PR，Priority）(4)随机服务（SIRO，Service in Random Order）2.排队规则(1)等待制 指顾客到达系统后，所有服务台都不空，顾客加入排队行列等待服务，一直等到服务完毕以后才离

7、去 ；（排队等候售票、故障设备等待维修）(2)损失制 指当顾客到达系统时，所有服务台都已被占用，顾客不愿等待而离开系统。（例如停车场） 服务台在选择顾客进行服务时，常有如下4种规则：(3)混合制 这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。大体有以下三种： 队长有限。当等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过时间T时，顾客将自动离去，并不再回来。 逗留时间（等待时间与服务时间之和）有限。(1) 服务台数量及构成形式 从数量上说

8、，服务台有单台和多台之分。从构成形式上看，有单队单服务台式、单队多服务台并联式、多队多服务台并联式、单队多服务台串联式等等，如图9-2到9-5所示；(2) 服务方式 指在某一时刻接受服务的顾客数，有单个服务和成批服务两种；（我们只考虑单个服务）(3) 服务时间的分布在多数情况下，对某一个顾客的服务时间是一随机变量，与顾客到达的时间间隔分布一样，服务时间的分布有定长分布、负指数分布、爱尔朗分布等等。3.服务台服务台可以从以下三个方面来描述：1.排队系统的符号根据不同的 输入过程、排队规则和服务台数量，可以形成不同的排队模型。一个排队系统的特征可以用六个参数表示，形式为：XYZ：ABC 或 X/Y

9、/Z/A/B/C其中X 顾客到达的概率分布，可取M、D、Ek、G等；Y 服务时间的概率分布，可取M、D、Ek 、G等；Z 服务台个数，取正整数；A 排队系统的最大容量，可取正整数或；B 顾客源的最大容量，可取正整数或；C 排队（服务）规则，可取FCFS、LCFS等。例如M/M/1：/FCFS表示顾客到达的时间间隔是负指数分布，服务时间是负指数分布，一个服务台，排队系统和顾客源的容量都是无限，实行先到先服务的一个服务系统。9.1.3 排队模型的概述表示相继达到间隔时间和服务时间的各种分布的符号如下：M-负指数分布（Markov, 具有无记忆性）D- 确定型(deterministic)Ek- k

10、 阶爱尔朗(erlang)分布G- 一般(general)服务时间的分布：顾客到达的平均速率，即单位时间内平均到达的顾客数；1/：平均到达时间间隔；：平均服务速率，即单位时间内服务完毕离去的顾客数；1/：平均服务时间； s ：系统中服务台的个数；：服务强度，即每个服务台单位时间内的平均服务时间，一般有/(s)；N：稳态系统任一时刻的状态（即系统中所有顾客数）；U：任一顾客在稳态系统中的逗留时间；Q：任一顾客在稳态系统中的等待时间；PnPN=n：稳态系统任一时刻状态为n的概率；特别当n=0时，PnP0，即稳态系统所有服务台全部空闲的概率；e：有效平均到达率，即单位时间内到达并能进入队列的平均顾客

11、数。 2. 一些常用记号（1）队长和队列长(排队长)队长 是指系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和）队列长 是指系统中正在排队等待服务的顾客数。队长和队列长一般都是随机变量（2）等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止这段时间称为等待时间。从顾客到达时刻起到他接受服务完止这段时间称为逗留时间。两种时间都是随机变量（3）忙期和闲期 忙期是指从顾客到达空闲着的服务机构起，到服务再次成为空闲止的这段时间，服务机构连续忙的时间。这是个随机变量。与忙期相对的是闲期，即服务机构连续保持空闲的时间。3. 排队系统的主要数量指标研究评价和优化随机服务系统需要通过一定的数量指

12、标来反映。（4）顾客损失率在损失制或系统容量有限的情况下，由于顾客被拒绝而使系统受到损失的顾客比率称为顾客损失率。（5）服务强度为反映服务效率和服务台的利用率，引入服务强度，常用 来表示，它是衡量系统性能的指标，其值为平均达到率 和平均服务率 s 之比。即 = / (s)，s 表示服务台数。排队论研究的首要问题是排队系统主要数量指标的概率规律，及研究系统的整体性质，然后进一步研究系统的优化问题。对系统进行调整和控制，使系统处于最优运行状态。上面给出的这些数量指标一般都是和系统运行的时间有关的随机变量，求这些随机变量的瞬时分布一般是很困难的。相当一部分排队系统在运行了一定时间后，都会趋于一个平稳

13、状态。在平稳状态下，队长的分布、等待时间的分布和忙期的分布都和系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平稳性质。4. 平稳状态Ls：平均队长，即稳态系统任一时刻顾客数的期望值；Lq：平均等待队长，即稳态系统任一时刻等待服务的顾客数的期望值；Ws：平均逗留时间，即在任一时刻进入稳态系统的顾客逗留时间的期望值；Wq：平均等待时间，即在任一时刻进入稳态系统的顾客等待时间的期望值；在平稳状态下: 5. 排队系统常用分布 负指数分布随机变量T服从负指数分布，其分布函数为 1,0( )0,0tTetFtt密度分布函数为tTetf)(

14、T的期望值为001)()(dtetdtttfTEtTT的方差为21)(TVar若随机变量X的概率密度为(0,0,1,2,)!neP Xnnn则称X服从参数为的泊松(Poisson)分布，记为XP()。其均值和方差分别为 )(XE)(XVar泊松分布9.2 单服务台负指数分布排队系统的分析9.2.1 标准的 M/M/1或M/M/1/ 图9-6设顾客到达的时间间隔服从参数为 的负指数分布 ，服务台的服务时间服从参数为 的负指数分布。单服务台，且顾客源无限，先到先服务。系统在稳态情况下的状态转移如图9-6所示 0 1 2n-1 nn+1P0 P1 P2 Pn-1 Pn Pn+1 1 系统状态概率Pn

15、(t)的计算根据以上状态转移图，可以得出如下平衡方程 001 PP0)(11nnnPPP), 2 , 1(n(91)(92)Pn(t) 指在任意时刻 t 的状态（系统中有n个顾客）的概率，它决定了系统运行的特征。（求 Pn(t) 的瞬时分布一般是很困难的，P263）我们只考虑稳态的情况，此时Pn(t)与时刻t 无关，直接记为 Pn 表示系统中有n个顾客，服务台忙，有n-1个顾客排队时的概率。当系统运行相当时间而达到平稳状态后，对任一状态 n来说，单位时间内进入该状态和离开该状态的平均次数应相等。这就是系统在统计平衡下的“流入=流出”原理。设系统达到平稳状态时系统中的顾客数为N（是一个随机变量）

16、，此时系统状态分布已不依赖于时间 t。推导过程省略P262-263由(91)和(92)可以递推求解P1，P2，Pn，得到 01PP02102)1 (PPPP0PPnn), 2 , 1(n1设210200,nnPP PPPP10PnnP)1 ( 1n01nnP由，有(93) (94) 表示平均到达率与平均服务率之比，称为服务强度 注：9-3和9-4只有当 1时成立【例（补）】高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为150辆小时，收费时间服从负指数分布，平均收费时间为15秒辆。求(1)收费处空闲的概率；(2)收费处忙的概率；(3)系统中分别有1，2，3辆车的概率。【解】

17、根据题意, =150辆/小时, 1/=15秒=1/240（小时/辆）,即240（辆/小时）。/=150/240=5/8，则有(1)系统空闲的概率为：P0=1=1(5/8)=3/8=0.375(2)系统忙的概率为：1-P0=5/8=0.625(3)系统中有1辆车的概率为：P1=(1)= 0.6250.375=0.234系统中有2辆车的概率为：P2= 2(1)= 0.2340.625=0.146系统中有3辆车的概率为：P3=3(1)= 0.1460.625=0.0912. 系统的运行指标(1)系统中的平均顾客数（系统中顾客数的期望值）Ls 0002(1)(1)(1)(1)1kkskkkkLkPkk

18、即平均队长为系统中顾客数的期望值（系统中各种状态的加权平均值） (2)队列中的平均顾客数 （排队顾客一定比总顾客少1个）qL111222(1)(1)(1)(1)(1)(1)(1)1kkqkskkkLkPLkk(3) 顾客在队列中的平均逗留时间 Wq （平均等待时间），当顾客进入系统时，如果系统中已有n个顾客，则他排队等待的时间就是n个顾客的平均服务时间之和。(95) 111()sqWW (96) (4) 顾客在系统中的平均逗留时间Ws为平均等待时间与平均服务时间之和 101111()qkkskkWkPkPL 注：在M/M/1情形下，可以证明逗留时间W 服从参数为-的负指数分布。Ws =EW=1

19、/(-), Wq = Ws 1/ =/(-)1ssqqsqsqqLWLWWWLLL李特尔(John D. C. Little)公式： 它们之间的相互关系如下：(98) (97) 归纳如下1sqsqLLWW M / M / 1 / / 模型 总结单位时间顾客平均到达数 ，单位平均服务顾客数 (3 0123313110.07480.16830.18930.1420.4256P nP nPPPP作业： P283,1 P284, 4补充：某银行有3个出纳员，顾客以平均速度为4人/分钟的泊松流到达，所有顾客排成一队，出纳员与顾客的交易时间服从平均数为1/2分钟的负指数分布，试求：（1）银行内空闲的概率；

20、（1/9）（2）平均队列长；(8/9)（3）银行内的顾客平均数；(26/9)（4）在银行内的平均逗留时间；(13/18)（5）等待服务的平均时间。(2/9)P283.5 在第1题中，若顾客平均到达率增加到每小时12人，服务时间不变，这时增加一个工人。试求 （1） （2）（3）（4）/ :/MMcNFCFS 0 1 2c-1c2cccc+1N-1 N(1)c图9-10 有限队列模型状态转移图设系统容量为N(Nc)，当系统中的顾客数nN时，到达的顾客进入系统；当nN时，到达的顾客就被拒绝。设顾客到达的速率为，每个服务台服务的速率为， / c系统的状态转移图见图9-10 9.3.2 系统容量有限制的

21、情形稳定状态的状态概率转移方程为： 10PP120)(2PPP(938) (939) 21(1) cccPc PcP(940) 11()cccPc PcP21()cccPc PcP (941) (942) 1NNPc P (943) 01NnnP得到系统稳态的状态概率 由100()()1!1kccNckccPkc (944) 11001(1)1!kcckcPNckc00()(0)!()!nncncPncnPcPcnNc (945) 系统的运行指标: 02()1()(1)!(1)cNcNqcLNccPc(1)qNLLcP)1 (NqqPLW1qWW(946) (947) (948) (949)

22、【例9.6】某旅馆有10个床位，旅客到达服从泊松流，平均速率为6人天，旅客平均逗留时间为2天，求：(1)旅馆客满的概率；(2) 每天客房平均占用数. 【解】这是一个即时制的 /2:10/M MFCFS系统，其中 1610,6,0.5,2,120.5Ncc()01sN 10123100(12)(12)(12)(12)(12)0.00180!1!2!3!10!P10100()(12)(1)0.00180.3019!10!NcPPN旅馆10个床位全满的概率为0.3019(2)(1)12(10.3019)8.3772cLcP平均占用8.377个床位。客房占用率为83.77%。9.3.3顾客源为有限的情

23、形 / :/MMcm FCFS设顾客源为有限数m，服务台个数为c，且mc。这个模型的典型例子是机器维修问题，机器数量为m台，修理工数量为c人 状态概率： 00111!11!()!()!kkccmkk cPmcckmkmcmkm mc00!0()! !1()! !nnnn cmPncmn nPmPcnmmn c c 式中： (951) (950) 运行指标 mnnnPL11()mqnn cLnc P )(LmLLLqeqeLW/eqqLW/)(Lme为有效到达速率 式中【例9.7】车间有5台机器，每台机器的故障率为1次小时，有2个修理工负责修理这5台机器，工作效率相同，为4台小时。求：(1)等待

24、修理的平均机器数；(2)等待修理及正在修理的平均机器数；(3)每小时发生故障的平均机器数；(4)平均等待修理的时间；(5)平均停工时间。 【解】这是一个 模型/2:/5/M MFCFS115,1,4,2,48mcmscmm001101234522211!11!()!()!11111112112112110.31495!0!5! 41!4! 42!3! 42! 2! 82! 1! 82! 0! 8kkccmkk cPmcckmkmcmkm P1=0.394， P2=0.197 ,P3=0.074， P4=0.018， P5=0.0023451(1)()230.118mqnn cLns PPPP

25、092. 15432)2(543211PPPPPnPLmnn908. 3)092. 15(1)()3(Lme)(8 . 1)(03. 0908. 3118. 0)4(分小时 eqqLW)(8 .16)(28. 0908. 3902. 1)5(分小时 eLW由式(951)可以计算得到 【定义9.1】对于随机过程 ,若满足Poisson流的定义0),(ttN(1)独立增量性(无后效性) 即对任意n个参数 增量 相互独立 或者说不相交的时间区间内到达的顾客数互相独立。0121ttttnnn)()(,),()(),()(12312nntNtNtNtNtNtN(2)增量平稳性 即在长度为 t 的时间区间

26、内恰好到达k个顾客的概率仅与区间长度t有关，而与区间起始点无关 (3)普遍性 即当t充分小时，有( )2( )P N to t称 为Poisson过程，N(t)服从泊松分布 ( ),0N tt 排队系统与泊松过程 若N(t)为时间区间0,t）(t0)内到达系统的顾客数，则N(t)是一个随机变量，且 N(t)|t(0,T)为一个随机过程。若该随机过程满足 （1）在不相重叠的区间内，顾客的到达数是相互独立的；（2）在时间区间t,t+t）内有顾客的到达数只与区间长度t有关，而与区间起始点t无关；（3）对于充分小的t，在时间区间t,t+t）内有2个或2个以上的顾客到达的概率极小，以致于可以忽略 则认为

27、顾客到达系统的过程是泊松过程，且 ()( )!kttP N tkek0,1,2,;0kt( )E N tt( )Var N tt【定理9.1】在排队系统中，如果到达的顾客数服从以t为参数的泊松分布，则顾客相继到达的时间间隔服从以为参数的负指数分布. pn=PN=n：稳态系统状态为n的概率。特别当n=0时，p0即稳态系统所有服务台全部空闲（系统中顾客数为0）的概率。 稳态系统任一时刻状态稳态系统任一时刻状态设N(t), t 0为一个随机过程，若N(t)的概率分布具有以下性质：（1）假设N(t)=n，则从时刻t起到下一个顾客到达止的时间服从参数为n的负指数分布，n=0,1,2,。（2）假设N(t)=n，则从时刻t起到下一个顾客离去止的时间服从参数为n的负指数分布，n=1,2,3,。（3）同