数学建模排队论.ppt

1、1,排队论,2,排队论,1、排队的组成及基本概念 2、生灭过程 3、六个排队模型,排队论,排队是日常生活中经常遇到的现象，如顾客到商店去买东西，病人到医院去看病，当售货员、医生的数量满足不了顾客或病人及时服务的需要时，就出现了排队的现象。 出现这样的排队现象，使人感到厌烦，当然增加服务设施（如售货员、医生）能减少排队现象，但这样势必增加投资又因供大于求使设施常常空闲、导致浪费。 作为管理人员，就要研究排队问题，把排队时间控制在一定的限度内，在服务质量的提高和成本的降低之间取得平衡，找到适当的解。,如果顾客相继到达的时间间隔是确定的，如自动装配线上装配的各部件就必须按确定的时间间隔到达装配点；服

2、务每一个顾客的时间也是确定的，如自动冲洗汽车的装置对每辆汽车冲洗的时间是确定的。 对于这类服务系统的设计计算比较方便。 但在大多数的服务系统中，情况不是这样。顾客的到达经常是随机的，并且服务设施用于每个顾客身上的服务时间往往也是随机的。对于这样一类随机服务系统的计算就要复杂得多。,排队论(Queuing Theory)又称随机服务系统理论(Random Service System Theory)，是研究排队系统的数学理论和方法，是运筹学的一个重要分支。 一般来说，排队论所研究的排队系统中，顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的。 具体地说，它是在研究各种排队系统概率规律性

3、的基础上，解决相应排队系统的最优设计和最优控制的问题。,一、基本概念 一些排队系统的例子 排队系统 顾 客 服务台 服 务 电话系统 电话呼叫 电话总机 接通呼叫或取消呼叫 售票系统 购票旅客 售票窗口 收款、售票 设备维修 出故障的设备 修理工 排除设备故障 防空系统 进入阵地的敌机 高射炮 瞄准、射击，敌机被击落或离开 排队的过程可表示为：,排队,服务机构服务,服务后顾客离去,排队系统,顾客到达,1、排队过程的组成部分及相关概念,根据服务台的数量及排队方式，排队系统可以分为 (1)单服务台单队,(2)多服务台单队,图9-2单服务台单队系统,顾客到达,服务台,顾客离去,服务台,服务台,图9-

4、3 多服务台单队系统,(3)多队多服务台,(4)多服务台串联服务,图9-4 多服务台多队系统,图9-5 多服务台串联系统,顾客到达,服务台,顾客离去,服务台,服务台,顾客到达,顾客离去,排队过程的组成部分,实际中的排队系统各有不同，但概括起来都由三个基本部分组成：输入过程、排队及排队规则、服务机制. 1、输入过程 输入过程说明顾客按怎样的规律到达系统，需要从以下三个方面来刻画一个输入过程。 （1）顾客总体数，又称顾客源、输入源。顾客源可以是有限的，也可以是无限的。如到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。,（2）顾客到达的形式。单个到达，还是成批到达。如大

5、学生到图书馆借书是单个到达，而购买的材料入库则可以看成成批到达。 （3）顾客流的概率分布，即单位时间内到达的顾客数，也可用顾客相继到达的时间间隔描述。这是刻画输入过程的最重要的内容。排队论中常用到的分布： 定长分布(D)，这种分布顾客相继到达的时间间隔是确定的，如产品通过传送带进入包装箱就是定长分布的例子。,泊松流(M) ： 1）在一定时间区间内，恰好到达k个顾客的概率仅与区间长度有关，而与区间起始时刻无关。即在时间区间0，t或a，a+t内，恰好到达k个顾客的概率相等。 2）在不相交的时间区间内到达的顾客数是相互独立的。或者说在时间区间a，a+t内来到k个顾客的概率与时刻a之前来到多少个顾客无

6、关。 3）在足够小的时间区间内只能有一个顾客到达，不可能有两个以上顾客同时到达。单位时间里有x个顾客到达的概率为： 其中，为单位时间平均到达的顾客数，此时顾客相继到达的时间间隔是独立的，服从参数为的负指数分布。,2、排队规则 （1）排队系统 排队分为有限排队和无限排队两类。前者是指系统的空间是有限的，当系统被占满时，后面再来的顾客将不能进入系统；后者是指系统中的顾客数可以是无限的，队列可以排到无限长，顾客到达后均可进入系统排队或接受服务。具体又分为以下三种。 1）等待制。即无限排队。 2）损失制。这种系统是指排队空间为零的系统，实际上是不允许排队。当顾客到达系统时，如果所有服务台均被占用，则自

7、动离去，并不再回来，这部分顾客就被损失掉了。 3）混合制。该系统是等待制和损失制系统的结合，一般是指允许排队，但又不允许队列无限长下去。,（2）排队规则 先来先服务(FCFS) 后来先服务(LCFS)，在许多库存系统中会出现这种情形，如钢板存入仓库后，需要时总是从最上面的取出；又如在情报系统中，后来到达的信息往往更加重要，应首先加以分析和利用。 具有优先权的服务(PS)，如病危的患者应优先治疗，加急的电报电话应优先处理等。 随机服务(SIRO),（3）服务机制 1）服务员的数量及构成形式。从数量上说，服务台有单台和多台之分。从构成形式上看，有单队单服务台式、单队多服务台并联式、多队多服务台并联

8、式、单队多服务台串联式等。 2）服务方式。指在某一时刻接受服务的顾客数，有单个服务和成批服务两种。 3）服务时间的分布。 定长分布(D)，指每个顾客接受服务的时间是一个确定的常数。,负指数分布(M)。服务时间是指顾客从开始接受服务到服务完成所花费的时间。由于每位顾客要办的业务都不一样，又存在很多影响服务机构服务时间的随机因素，因此服务时间也是一个随机变量。一般说，负指数概率分布能较好地描述一些排队系统里服务时间的概率分布情况。在负指数分布里，服务时间小于或等于时间长度t的概率： F（t）=P（服务时间t）=1-e-t 这里的为单位时间里被服务完的平均顾客数。,在排队系统中，在时间间隔长度t中到

9、达的顾客数Nt服从以t为参数的泊松分布，则顾客相继到达的时间间隔T服从以为参数的负指数分布。 如果我们把Nt定义为任一时间间隔长度t中的到达者数量，泊松分布： （n=0,1,2,3,） E（ Nt ）=var Nt = t。在时间间隔长度t中平均有t名到达者。 为单位时间到达者的平均数量或者到达率。 负指数分布：FT(t)=PTt=1-,K阶爱尔朗分布 设X1，X2，Xk是k个互相独立的，具有相同参数的负指数分布随机变量，则随机变量：X=X1+X2+X3+Xk 服从k阶爱尔朗分布，X的密度函数为： 随机变量X的均值和方差分别为： E(X)=1/，Var(X)=1/k2 如果顾客连续接受串联的k

10、个服务台的服务，各服务台的服务时间相互独立，且均服从参数为的负指数分布，则顾客接受k个服务台总共所需的时间就服从k阶爱尔朗分布。,平稳状态 当一个排队服务系统开始运转时，系统状态很大程度上取决于系统的初始状态和运转经历的时间，但过了一段时间后，系统的状态将独立于初始状态及经历的时间，这时称系统处于平稳状态。由于对系统的瞬时状态研究分析起来很困难，所以排队论中主要研究系统处于平稳状态的工作情况。,排队系统的符号表示,X/Y/Z/A/B/C 这里的X记顾客相继到达的时间间隔的分布，M表示服从泊松分布或负指数分布，D表示定长分布，Ek表示爱尔朗分布，G表示一般相互独立任意分布； Y记服务时间的分布，

11、类型同X； Z记服务台数目，取正整数； A记系统的容量，表示系统中顾客容量限额，若系统中有k个等待位子(0k)，当k=0时，说明系统不允许等待，即为损失制。 k=为等待制系统。k为有限整数时，则为混合制 ； B记顾客源的数目，可取正整数或 ，即有限与无限； C记排队服务规则，FCFS先到先服务，LCFS后到先服务，SIRO随机服务，PR有优先权的服务。,排队系统的主要数量指标,研究排队系统的目的是通过了解系统运行的状况，对系统进行调整和控制，使系统处于最优运行状态。因此，首先需要弄清系统的运行状况。描述一个排队系统运行状况的主要数量指标有： Pn：系统中恰好有n个顾客的概率，这n个顾客包括排队

12、和正在被服务的顾客；在系统里没有顾客的概率，即所有服务设施空闲的概率，记为P0。 Pw顾客到达系统时，得不到及时服务，必须排队等待服务的概率。,Ls在系统里的平均顾客数，包括排队的顾客数和正在被服务的顾客数。 Lq排队的平均长度，即排队的平均顾客数。 Wq平均一位顾客花在排队上的时间。 Ws平均一位顾客在系统里的平均逗留时间，它包括排队时间和被服务的时间。 Little公式，L=W。为单位时间内到达的顾客数。,2、生灭过程及生灭过程排队系统,1. 生灭过程 生灭过程是一类非常简单具有广泛应用的一类随机过程，很多排队 模型中都假设其状态过程为生灭过程；这样的排队子系统如：M/M/C和 M/M/C

13、/R，我们也可称之为生灭过程的排队系统。在这样的排队系统中， 一个新顾客的到达看作“生”，一个顾客服务完之后离开系统看作是 “死”，设N(t)为任意时刻t排队系统的状态（即排队子系统中的总顾客 数），则对M/M/C/K系统N(t)具有有限个状态0，1，,k,对M/M/C来说 N(t)具有可列个状态0，1，2。 一般来说，随机过程 满足以下条件，称为生灭过程： 1) 假设N(t)=n，则从时刻t起到下一个顾客到达时刻为止的时间服 从参数为 的负指数分布，n=0,1,2, 2) 假设N(t)=n，则从时刻t起到下一个顾客离去时刻为止的时间服 从参数为 的负指数分布，n=0,1,2, 3) 同一时刻

14、时只有一个顾客到达或离去。即只在相邻状态间转换。,一般来说，得到N(t)的分布Pn(t)=PN(t)=n,n=0,1,2,是比较困难的，因此通常是求当系统运行一段时间达到平稳状态后的状态分布，记为Pn。 当系统运行长时间达到平稳状态后，对于任一个状态n，单位时间内进入该状态的平均次数和单位时间离开该状态的平均次数应该相等，这就是系统的统计平衡下的“流入=流出”原理。,2. 生灭过程稳态方程,输入（出）率=某一稳态概率平均转换率,2、生灭过程及生灭过程排队系统,2. 生灭过程稳态方程,方程为：,由此可求得生灭过程的平稳状态分布：,由于,即有,即有,即有,2、生灭过程及生灭过程排队系统,即当,时，

15、此生灭过程存在平稳状态分布：,27,3、六个模型,M/M/1/FCFS M/M/1/N/FCFS M/M/1/m/FCFS M/M/s/FCFS M/M/s/N/FCFS M/M/s/m/FCFS 到达过程/服务时间/服务台/系统容量/顾客源/排队规则,单服务台基本模型,设单位时间到达系统的顾客数为 ，单位时间被服务完的顾客数为。由于是单服务台，且顾客源无限，因此，在各种状态的情况下，系统的“出生率”为，系统的“死亡率”为。系统在稳态情况下的状态转移如图9-6所示,图9-6,根据以上状态转移图，可以得出如下平衡方程,(91),(92),1 系统状态概率Pn(t)的计算,由(91)和(92)可以

16、递推求解P1，P2，Pn，得到,表示平均到达率与平均服务率之比，称为服务强度,9.3 单服务台模型,【例9.1】高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为150辆小时，收费时间服从负指数分布，平均收费时间为15秒辆。求 (1)收费处空闲的概率； (2)收费处忙的概率； (3)系统中分别有1，2，3辆车的概率。,【解】根据题意, =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)系统

17、中有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.091,2. 系统的运行指标,(1)系统中的平均顾客数（系统中顾客数的期望值）Ls,即队长为系统中顾客数的期望值（系统中各种状态的加权平均值）,32,2. 系统的运行指标,(2)队列中的平均顾客数（等待）,34,(3)服务中的平均顾客数 Lf=0P0+1（P1+ P2+ P3+）=1-P0=1-（1-）= =/,Little公式:,(3)顾客在系统中的平均逗留时间W,(98),(4)顾

18、客在队列中的平均逗留时间 Wq,(99),【例9.2】轻轨进站口售票处设有一个售票窗口，乘客到达服从泊松分布，平均到达速率为200人/小时，售票时间服从负指数分布，平均售票时间为15秒/人。求Ls、Lq、Ws和Wq。 【解】根据题意，=200人/小时，=240人/小时，=5/6。,37,作业,某汽车修理店只有一个修理工，汽车按泊松分布到达，平均每小时到达36辆，修理工完成每辆汽车修理的时间服从负指数分布，汽车到达修理店不需排队的概率为0.4。计算如下问题： 修理工的平均修理速度（辆/小时） 修理店内的平均总汽车数（辆）； 一辆汽车在修理店内的平均排队时间（分钟） 修理店内有2辆及以上汽车的概率

19、,有限队列模型,如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某一时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。系统状态转移如图9-7,图97,1.系统状态概率的计算,由状态转移图9-7，建立系统概率平衡方程如下,(911),(912),(913),(914),(915),根据式912和913可以导出系统的各个指标，对于1，有,(9-16),(1)系统中的平均顾客数Ls,9.3 单服务台模型,(917),(2)队列中的平均顾客数Lq,(918),e 称为有效到达率，即单位时间内到达并能进入队列的平均顾客数。e 称为有效服务强度,(3)顾客在系

20、统中的平均逗留时间,(9-19),(4)顾客在队列中的平均逗留时间,(9-20),在我们的有限容量模型中，每单位时间平均有名到达者到达，但是这些到达者中有PN的概率不能进入系统，因为此时系统已满，所以有 PN名到达者无法进入系统而离开。,e 称为有效到达率，即单位时间内到达并能进入队列的平均顾客数。e 称为有效服务强度 。对于有限容量系统，即使，系统的有限容量也会阻止系统中的人数爆炸，稳态存在。,【例9.3】咨询中心有一位咨询工作人员，每次只能咨询一人，另外有4个座位供前来咨询的人等候。某人到来发现没有座位，就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速率为4人/小时，咨询人员的平均

21、咨询时间为10分钟/人。咨询时间服从负指数分布。求： (1)咨询者到达不用等待就可咨询的概率 (2)咨询中心的平均人数以及等待咨询的平均人数 (3)咨询者来咨询中心一次平均花费的时间以及平均等待的时间 (4)咨询者到达后因客满而离去的概率 (5)增加一个座位可以减少的顾客损失率,【解】N=4+1=5，=4人/小时，=6人/小时，=2/3,(1),9.3 单服务台模型,(2),(3),(4),因客满而离去的概率为0.048,(5) 当N=6时,9.3 单服务台模型,即增加一个座位可以减少顾客损失率1.6%,9.3.3 有限顾客源模型,设顾客总数为m。当顾客需要服务时，就进入队列等待；服务完毕后，

22、重新回到顾客源中，如此循环往复。由于顾客源的数量有限，因此队列的长度也是有限的，并且队列的长度必定小于顾客源总数 。 在无限源顾客系统中，顾客的平均到达速率是整个顾客源的性质，与单独的顾客无关。即使有顾客反复接受服务，对于本来就是无穷大的顾客源影响不大。,47,在有限源系统中，由于一个顾客要反复接受服务，因此有必要假定每一个顾客在单位时间内需要接受服务的平均次数是相同的，设为。这样，有限源系统顾客的平均到达速率就与顾客源中的顾客数有关。 以机器维修问题为例，设机器总数为m台，每台机器在单位时间内发生故障的平均次数为，已经发生故障正在等待修理及正在接受修理的机器数为n。试想，由于机器需要反复修理

23、，所以可以把单位时间内需要修理的机器总数看成是一共m 台（一台只修理一次），其中有n 台在系统中，所以单位时间内将要到达的机器数（剩余的）可以看成（m n) 台。 有限源系统顾客的平均到达速率：为每个顾客在单位时间内到达的平均次数， n为在系统中的顾客数。,0,1,2,n-1,n,n+1,m-1,m,图9-8 有限顾客源模型状态转移图,状态转移图如图9-8,由图9-8得到系统稳态概率平衡方程组,1系统状态概率的计算,(921),用递推方法解该方程组，得到,(922),(923),2 有限源系统的运行指标,在求得系统中出现顾客数的概率后，即可求得系统的运行指标(推导过程略),不要求=/1,9.3

24、 单服务台模型,(924),(925),(926),(927),在机器维修问题中，Ls是待检修及正在检修的平均机器数，而,表示正常运行的平均机器数。,9.3 单服务台模型,【例9.4】某车间有5台机器，每台机器的连续运转时间服从负指数分布，一天（8小时）平均连续运行时间120分钟。有一个修理工，每次修理时间服从负指数分布，平均每次96分钟。求： (1)修理工忙的概率(记为Pb)； (2)五台机器都出故障的概率； (3)出故障的平均台数； (4)平均停工时间； (5)平均等待修理时间； (6)评价这个系统的运行情况,【解】一天为一个单位时间。认为一天内来修理的机器数平均为4台，修理工一天平均修理

25、机器数为5台。m=5，=4，=5，=0.8,9.3 单服务台模型,(6)由计算结果看出，系统的修理工几乎没有空闲时间，机器的停工时间是平均运行时间的三倍，系统的服务效率很低,多服务台模型,多服务台基本模型,规定各服务台工作相互独立且服务速率相同,系统的平均服务速率为 s,令,0,1,2,s-1,s,s+1,n-1,n,图9-9 基本模型状态转移图,系统的状态转移图9-9。,这个系统的特点是，系统的服务速率与系统中的顾客数有关。当系统中的顾客数k不大于服务台个数，即1ks时，系统中的顾客全部在服务台中，这时系统的服务速率为k。当系统中的顾客数ks时，因服务台有限，系统的服务速率达最大为s。,9.

26、4多服务台模型,稳态概率方程,(928),(929),(930),(931),(932),(933),9.4多服务台模型,顾客需要等待 (系统已有s个顾客)的概率,与单服务台系统的方法类似，有,9.4多服务台模型,【例9.5】银行办理个人储蓄业务有三个窗口，顾客到达服从泊松流，到达速率为0.9人分，办理业务时间服从负指数分布，每个窗口的平均服务速率为0.4人分。顾客到达后取得一个排队号，依次由空闲窗口按号码顺序办理储蓄业务。求： (1)所有窗口都空闲的概率； (2)平均队长； (3)平均等待时间及逗留时间； (4)顾客到达后必须等待的概率。,(1)所有窗口都空闲的概率，即求P0,(2)平均队长

27、，先求Lq ,再求Ls,(3)平均等待时间和平均逗留时间，即求Wq和Ws的值,(4)顾客到达后必须等待，即n3,9.4多服务台模型,9.4多服务台模型,9.4.2有限队列模型,0,1,2,s-1,s,s+1,N-1,N,图9-10 有限队列模型状态转移图,设系统容量为N(Ns)，当系统中的顾客数nN时，到达的顾客进入系统；当nN时，到达的顾客就被拒绝。设顾客到达的速率为，每个服务台服务的速率为，,系统的状态转移图见图9-10,9.4多服务台模型,稳定状态的状态概率转移方程为：,(938),(939),(940),(941),(942),(943),(944),9.4多服务台模型,(945),系

28、统的运行指标:,(946),(947),(948),(949),9.4多服务台模型,【例9.6】某旅馆有10个床位，旅客到达服从泊松流，平均速率为6人天，旅客平均逗留时间为2天，求： (1)旅馆客满的概率； (2) 每天客房平均占用数.,旅馆10个床位全满的概率为0.3019,平均占用8.377个床位。客房占用率为83.77%。,9.4多服务台模型,9.4.3有限顾客源模型,设顾客源为有限数m，服务台个数为s，且ms。这个模型的典型例子是机器维修问题，机器数量为m台，修理工数量为s人,状态概率：,式中：,(951),(950),9.4多服务台模型,运行指标,9.4多服务台模型,【例9.7】车间

29、有5台机器，每台机器的故障率为1次小时，有2个修理工负责修理这5台机器，工作效率相同，为4台小时。求： (1)等待修理的平均机器数； (2)等待修理及正在修理的平均机器数； (3)每小时发生故障的平均机器数； (4)平均等待修理的时间； (5)平均停工时间。,【解】这是一个 模型,9.4多服务台模型,P1=0.394， P2=0.197 ,P3=0.074， P4=0.018， P5=0.002,由式(951)可以计算得到,考虑要点： 1、服务台（或通道）数目：单服务台（单通道）、多服务台（多通道）。 2、顾客到达过程：本教材主要考虑顾客的泊松到达情况。 满足以下三个条件的输入流称为泊松流（泊

30、松过程）。 *平稳性：在时间区间 t, t+t) 内到达k个顾客的概率与t无关，只与 t 有关，记为 pk(t）； *无后效性：不相交的时间区间内到达的顾客数互相独立； *普通性：在足够短的时间内到达多于一个顾客的概率可以忽略； 泊松分布 为单位时间平均到达的顾客数 P (x) = x e- / x! (x = 0, 1, 2,),1排队过程的组成部分,1排队过程的组成部分,3、服务时间分布： 服从负指数分布， 为平均服务率，即单位时间服务的顾客数， P（服务时间 t ) = 1- e- t 。 4、排队规则分类 (1) 等待制： 顾客到达后，一直等到服务完毕以后才离去， 先到先服务，后到先服

31、务，随机服务，有优先权的服务； (2) 损失制： 到达的顾客有一部分未接受服务就离去。 5、平稳状态： 业务活动与时间无关。,排队系统的符号表示: 一个排队系统的特征可以用五个参数表示，形式为： ABCDE 其中 A 顾客到达的概率分布，可取M、 D、G 、Ek等； B 服务时间的概率分布，可取M、D、 G 、 Ek等； C 服务台个数，取正整数； D 排队系统的最大容量，可取正整数或； E 顾客源的最大容量，可取正整数或。 例如 M / M / 1 / / 表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。,1排队过程的组成部分,M / M

32、 / 1 / / 单位时间顾客平均到达数 ，单位平均服务顾客数 ( ) 数量指标公式: 1. 系统中无顾客的概率 P0 =1 / 2. 平均排队的顾客数 Lq =2/( ) 3. 系统中的平均顾客数 Ls = Lq + / 4. 顾客花在排队上的平均等待时间 Wq = Lq / 5. 顾客在系统中的平均逗留时间 Ws = Wq+ 1/ 6. 顾客得不到及时服务必须排队等待的概率 Pw = / 7. 系统中恰好有 n 个顾客的概率 Pn =( /)n P0,1 排队过程的组成部分,2单服务台泊松到达、负指数服务时间的排队模型,2单服务台泊松到达、负指数服务时间的排队模型,在上面的公式中，我们都认

33、定 ,即到达率小于服务率，如果没有这个条件，则排队的长度将无限制地增加，服务机构根本没有能力处理所有到达的顾客， 也就是 / 1,我们称 / 为服务强度。 例 某储蓄所只有一个服务窗口。根据统计分析，顾客的到达过程服从泊松分布，平均每小时到达顾客36人；储蓄所的服务时间服从负指数分布，平均每小时能处理48位顾客的业务。试求这个排队系统的数量指标。 解 平均到达率 = 36/60 = 0.6， 平均服务率 = 48/60 = 0.8。 P0 =1 / = 10.6/0.8 = 0.25, Lq =2/( ) = (0.6)2 / 0.8(0.8 0.6) =2.25 (个顾客),Ls = Lq

34、+ / = 2.25+ 0.6/0.8 =3 (个顾客), Wq = Lq / = 2.25/0.6 = 3.75（分钟）, Ws = Wq+ 1/ = 3.75+1/0.8 =5 （分钟）, Pw = / = 0.6/0.8 = 0.75, Pn =( /)n P0 = (0.75)n 0.25, n=1, 2, 。 通过计算，可知储蓄所的排队系统里有n个顾客的概率，见表14-1。,2单服务台泊松到达、负指数服务时间的排队模型,表14-1,2单服务台泊松到达、负指数服务时间的排队模型,通过计算数据与表中数据，可知储蓄所的排队系统并不尽如人意，到达储蓄所有75%的概率要排队等待，排队的长度平均

35、为2.25个人，排队的平均时间为3.75分钟，是1.25分钟的3倍。而要提高服务水平，减少顾客的平均排队时间和平均服务时间，一般可采用两种措施：第一，减少服务时间，提高服务率；第二，增加服务台即增加服务窗口。 如采取第一种方法，不增加服务窗口，而增加新型点钞机，建立储户管理信息系统，可以缩短储蓄所每笔业务的服务时间，使每小时平均服务的顾客数目从原来的48人提高到60人，即每分钟平均服务的顾客数从0.8人提高到1人，这时 仍然为0.6， 为1，通过计算得到的结果如表14-2所示：,2单服务台泊松到达、负指数服务时间的排队模型,从上表我们可以看出由于把服务率从0.8提高到1，其排队系统有了很大的改

36、进，顾客平均排队时间由3.75分钟减少到1.5分钟，顾客平均逗留时间从5分钟减少到2.5分钟. 如果采用第二种方法，再设一个服务窗口，排队的规则为每个窗口排一个队，先到先服务，并假设顾客一旦排了一个队，就不能再换到另一个队上去（譬如，当把这个服务台设在另一个地点，上述假设就成立了）。这种处理方法就是把顾客分流，把一个排队系统分成两个排队系,表14-2,2单服务台泊松到达、负指数服务时间的排队模型,统，每个排队系统中有一个服务台，每个系统的服务率仍然为0.8，但到达率由于分流，只有原来的一半了， =0.3，这时我们可求得每一个排队系统的数量指标如表14-3所示：,表14-3,我们比较表14-1和

37、14-3，知道采用第二个方法的服务水平也使得原来的服务水平有了很大的提高，采用第二种方法顾客平均排队时间减少到了0.75分钟，顾客平均逗留时间减少到了2分钟，第二种排队系统为两个M/M/1排队系统。如果在第二种方法中把排队的规则变一下，在储蓄所里只排一个队，这样的排队系统就变成了 M/M/2排队系统。,M / M / C / / 单位时间顾客平均到达数 ，单位平均服务顾客数 。 1. 系统中无顾客的概率 2. 平均排队的顾客数 3. 系统中的平均顾客数 Ls = Lq + / , 4. 顾客花在排队上的平均等待时间 Wq = Lq / ,3多服务台泊松到达、负指数服务时间的排队模型,5. 顾客

38、在系统中的平均逗留时间 Ws = Wq+ 1/ , 6. 系统中顾客必须排队等待的概率 7. 系统中恰好有 n 个顾客的概率,当nc时,当nc时,3多服务台泊松到达、负指数服务时间的排队模型,例 在前例的储蓄所里多设一个服务窗口，即储蓄所开设两个服务窗口。顾客的到达过程仍服从泊松分布，平均每小时到达顾客仍是36人；储蓄所的服务时间仍服从负指数分布，平均每小时仍能处理48位顾客的业务，其排队规则为只排一个队，先到先服务。试求这个排队系统的数量指标。 解 C = 2， 平均到达率 = 36/60 = 0.6， 平均服务率 = 48/60 = 0.8。 P0 =0.4545, Lq = 0.1227

39、 (个顾客), Ls = Lq + / = 0.8727 (个顾客), Wq = Lq / = 0.2045（分钟）, Ws = Wq+ 1/ = 1.4545 （分钟）, Pw = 0.2045, P1 = 0.3409, P2 = 0.1278, P3 = 0.0479, P4 = 0.0180, P5 = 0.0067。 系统里有6个人的概率或多于6个人的概率为0.0040。,3多服务台泊松到达、负指数服务时间的排队模型,在储蓄所里使用M / M / 2模型与使用两个M / M / 1模型，它们的服务台数都是2，服务率和顾客到达率都一样，只是在M / M / 2中只排一队，在2个M /

40、M / 1中排两个队，结果却不一 样。 M / M / 2使得服务水平有了很大的提高，每个顾客的平均排队时间从0.75分钟减少到0.2045分钟，每个顾客在系统里逗留时间从2分钟减少到1.4545分钟，平均排队的人数也从0.2250人减少到0.1227人，系统里平均顾客数也从0.6*2=1.2人减少到0.8727人。如果把M / M / 2与原先一个M / M / 1比较，那么服务水平之间的差别就更大了。 我们在第二节与第三节发现公式有三个公式是完全相同的，实际上这三个公式表示了任一个排队模型（不仅仅是M/M/1或M/M/2）中，Ls,Lq,Ws,Wq之间的关系，也就是说：,3多服务台泊松到达

41、、负指数服务时间的排队模型,3多服务台泊松到达、负指数服务时间的排队模型,对任一个排队模型成立，这里Ls,Lq,Ws,的定义如上所述，而 应为实际进入系统平均到达率，对于排队长度有限制的模型，我们设因排队长度的限制顾客被拒绝的概率为PN，则实际进入系统平均到达率应为 这时，原来公式中的 应改为 。,M / G / 1 / / 单位时间顾客平均到达数 ，单位平均服务顾客数 ， 一个顾客的平均服务时间 1 / ，服务时间的均方差。 数量指标公式: 1. 系统中无顾客的概率 P0=1 / 2. 平均排队的顾客数 3. 系统中的平均顾客数 Ls = Lq + / 4. 顾客花在排队上的平均等待时间 W

42、q = Lq / 5. 在系统中顾客的平均逗留时间 Ws = Wq+ 1/ 6. 系统中顾客必须排队等待的概率 Pw = / 7. 系统中恰好有 n 个顾客的概率 Pn,5单服务台泊松到达、任意服务时间的排队模型,例1 某杂货店只有一名售货员，已知顾客的到达过程服从泊松分布，平均到达率为每小时20人；不清楚这个系统的服务时间服从什么分布，但从统计分析知道售货员平均服务一名顾客的时间为2分钟，服务时间的均方差为1.5分钟。试求这个排队系统的数量指标。 解：这是一个 M / G / 1 的排队系统，其中 = 20/60 = 0.3333 人/分钟，1/ = 2分钟， = =0.5 人/分钟， =1

43、.5。 P0 =1 / = 0.33334, Lq =1.0412 (人), Ls = Lq + / = 1. 7078 (人), Wq = Lq / = 2.25/0.6 = 3.1241（分钟）, Ws = Wq+ 1/ =5.1241（分钟）, Pw = / = 0.6666。,5单服务台泊松到达、任意服务时间的排队模型,6单服务台泊松到达、定长服务时间的排队模型,M / D / 1 / / 注：它是 M / G / 1 / / 的特殊情况 = 0。 1. 系统中无顾客的概率 P0=1 / 2. 平均排队的顾客数 3. 系统中的平均顾客数 Ls = Lq + / 4. 顾客花在排队上的平

44、均等待时间 Wq = Lq / 5. 在系统中顾客的平均逗留时间 Ws = Wq+ 1/ 6. 系统中顾客必须排队等待的概率 Pw = / 7. 系统中恰好有 n 个顾客的概率 Pn,例2 某汽车冲洗服务营业部，有一套自动冲洗设备，冲洗每辆车需要6分钟，到此营业部来冲洗的汽车到达过程服从泊松分布，每小时平均到达6辆，试求这个排队系统的数量指标。 解：这是一个 M / D / 1 排队模型，其中 = 6辆/小时， = 60/6 =10辆/小时，得 P0 =1 / = 0.4, Lq =0.45, Ls = Lq + / = 1.05, Wq = Lq / = 0.0750， Ws = Wq+ 1

45、/ =0.1750, Pw = / = 0.6。,6单服务台泊松到达、定长服务时间的排队模型,M / G / C / C / 注：不存在平均排队的顾客数 Lq 和顾客平均的排队等待时间 Wq。数量指标公式: 系统中的平均顾客数 Ls = / (1 Pc ) 其中Pc 是系统中恰好有 c 个顾客的概率，也就是系统里c 个服务台都被顾客占满的概率。 系统中恰好有 n 个顾客的概率,7多服务台泊松到达、任意的服务时间、损失制排队模型,例3. 某电视商场专营店开展了电话订货业务，到达过程服从泊松分布，平均到达率为每小时16个，而一个接话员处理订货事宜的时间是随着订货的产品、规格、数量及顾客的不同而变化

46、的，但平均每个人每小时可以处理8个订货电话，在此电视商场专营店里安装了一台电话自动交换台，它接到电话后可以接到任一个空闲的接话员的电话上，试问该公司应安装多少台接话员的电话，使得订货电话因电话占线而损失的概率不超过10%。 解：这是一个 M / G / C / C / 模型。当c=3时，即正好有3位顾客的情况，,7多服务台泊松到达、任意的服务时间、损失制排队模型,0.21050.1,所以不符合要求。 当c=4时， 因此，设置四个电话很合适。,7多服务台泊松到达、任意的服务时间、损失制排队模型,M / M / 1 / / m 条件：单位时间顾客平均到达数 单位平均服务顾客数 关心的项目: 1. 系统中无顾客的概率 P0 2. 系统中平均排队的顾客数 Lq 3. 系统中的平均顾客数 Ls 4. 系统中顾客平均的排队等待时间 Wq 5. 系统中顾客的平均逗