Ch排队论PPT学习教案

1、会计学1 Ch排队论排队论PPT课件课件 9.1 排队论的基本概念 第1页/共87页 2021年7月25日星期日 9.1.1 排队系统的描述 排队系统的例子 9.1 排队论的基本概念 Basic Concepts of Queuing theory 顾客顾客要求的服务要求的服务服务机构服务机构 1借书的学生借书的学生 2打电话打电话 3提货者提货者 4待降落的飞行器待降落的飞行器 5储户储户 6河水进入水库河水进入水库 7购票旅客购票旅客 8十字路口的汽车十字路口的汽车 借书借书 通话通话 提货提货 降落降落 存款、取款存款、取款 放水、调整水位放水、调整水位 购票购票 通过路口通过路口 图书

2、管理员图书管理员 交换台交换台 仓库管理员仓库管理员 指挥塔台指挥塔台 储蓄窗口、储蓄窗口、ATMD 取款机取款机 水库管理员水库管理员 售票窗口售票窗口 红绿灯或交警红绿灯或交警 第2页/共87页 2021年7月25日星期日 顾客到达排队接受服务顾客离去 图9-1 排队系统 排队的过程可表示为： 9.1 排队论的基本概念 Basic Concepts of Queuing theory 第3页/共87页 2021年7月25日星期日 根据服务台的数量及排队方式，排队系统可以分为 (1)单服务台单队 (2)多服务台单队 图9-2单服务台单队系统 顾客到达 进入队列 服务台 接受服务 顾客离去 顾

3、客到达 服务台 顾客离去 服务台 服务台 图9-3 多服务台单队系统 9.1 排队论的基本概念 Basic Concepts of Queuing theory 第4页/共87页 2021年7月25日星期日 (3)多队多服务台 (4)多服务台串联服务 图9-4 多服务台多队系统 图9-5 多服务台串联系统 9.1 排队论的基本概念 Basic Concepts of Queuing theory 顾客到达 服务台 顾客离去 服务台 服务台 顾客到达 服务台 顾客离去 服务台 第5页/共87页 2021年7月25日星期日 9.1.2排队系统的基本组成 排队系统由输入过程、服务规则和服务台三个部分

4、组成 这是指要求服务的顾客按怎样的规律到达排队系统的过程，有时也称之为顾客流。 （1）顾客总体数，又称顾客源、输入源。顾客源可以是有限的，也可以是无限的。 （2）顾客到达的形式。这是描述顾客是怎样来到系统的，是单个到达，还是成批到达。 （3）顾客流的概率分布，或称顾客相继到达的时间间隔分布。这是首先需要确定的指标。 9.1 排队论的基本概念 Basic Concepts of Queuing theory 1.输入过程 第6页/共87页 2021年7月25日星期日 (1)先到先服务（FCFS，First Come First Serve）； (2)后到先服务（LCFS，Last Come Fi

5、rst Serve）； (3)有优先权的服务（PR，Priority） (4)随机服务（SIRO，Service in Random Order） 9.1 排队论的基本概念 Basic Concepts of Queuing theory 2.排队规则 (1)等待制 指顾客到达系统后，所有服务台都不空，顾客加入排队行列等待服务，一直等到服务完毕以后才离去 ； (2)损失制 指当顾客到达系统时，所有服务台都已被占用，顾客不愿等待而离开系统。 第7页/共87页 2021年7月25日星期日 (3)混合制 这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。大体有以下三

6、种： 队长有限。当等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过时间T时，顾客将自动离去，并不再回来。 逗留时间（等待时间与服务时间之和）有限。 9.1 排队论的基本概念 Basic Concepts of Queuing theory 第8页/共87页 2021年7月25日星期日 (1)服务台数量及构成形式 从数量上说，服务台有单台和多台之分。从构成形式上看，有单队单服务台式、单队多服务台并联式、多队多服务台并联式、单队多服务台串联式等等，如图9-2到9-5所示； (2

7、)服务方式 指在某一时刻接受服务的顾客数，有单个服务和成批服务两种； (3)服务时间的分布 在多数情况下，对某一个顾客的服务时间是一随机变量，与顾客到达的时间间隔分布一样，服务时间的分布有定长分布、负指数分布、爱尔朗分布等等。 3.服务台 9.1 排队论的基本概念 Basic Concepts of Queuing theory 服务台可以从以下三个方面来描述： 第9页/共87页 2021年7月25日星期日 9.1.3 排队系统的主要数量指标、记号和符号 9.1 排队论的基本概念 Basic Concepts of Queuing theory （1）队长和队列长(排队长) 队长是指系统中的顾

8、客数（排队等待的顾客数与正在接受服务的顾客数之和） 队列长是指系统中正在排队等待服务的顾客数。队长和队列长一般都是随机变量 （2）等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止这段时间称为等待时间。从顾客到达时刻起到他接受服务完止这段时间称为逗留时间。两种时间都是随机变量 （3）忙期和闲期 忙期是指从顾客到达空闲着的服务机构起，到服务再次成为空闲止的这段时间，服务机构连续忙的时间。这是个随机变量。与忙期相对的是闲期，即服务机构连续保持空闲的时间。 1. 主要数量指标 第10页/共87页 2021年7月25日星期日 9.1 排队论的基本概念 Basic Concepts of Queui

9、ng theory 2. 记号 时刻 t 系统中的顾客数（又称为系统的状态），即队长； 时刻 t 系统中排队的顾客数，即列队长； 时刻 t 到达系统的顾客在系统中的逗留时间； 时刻 t 到达系统的顾客在系统中的等待时间 ( ):N t ( ): q Nt ( ):T t ( ): q T t L：平均队长，即稳态系统任一时刻顾客数的期望值； Lq：平均等待队长，即稳态系统任一时刻等待服务的顾客数的期望值； W：平均逗留时间，即在任一时刻进入稳态系统的顾客逗留时间的期望值； Wq：平均等待时间，即在任一时刻进入稳态系统的顾客等待时间的期望值； 在平稳状态下: 第11页/共87页 2021年7月2

10、5日星期日 9.1 排队论的基本概念 Basic Concepts of Queuing theory ：顾客到达的平均速率，即单位时间内平均到达的顾客数； 1/：平均到达时间间隔； ：平均服务速率，即单位时间内服务完毕离去的顾客数； 1/：平均服务时间； s ：系统中服务台的个数； ：服务强度，即每个服务台单位时间内的平均服务时间，一般有/(s)； N：稳态系统任一时刻的状态（即系统中所有顾客数）； U：任一顾客在稳态系统中的逗留时间； Q：任一顾客在稳态系统中的等待时间； PnPN=n：稳态系统任一时刻状态为n的概率；特别当n=0时，PnP0，即稳态系统所有服务台全部空闲的概率； e：有效

11、平均到达率，即期望每单位时间内来到系统（包括未进入系统）的概率。 第12页/共87页 2021年7月25日星期日 3.排队系统的符号 一个排队系统的特征可以用六个参数表示，形式为： XYZ：ABC 或 X/Y/Z/A/B/C 其中 X 顾客到达的概率分布，可取M、D、Ek、G等； Y 服务时间的概率分布，可取M、D、Ek 、G等； Z 服务台个数，取正整数； A 排队系统的最大容量，可取正整数或； B 顾客源的最大容量，可取正整数或； C 排队规则，可取FCFS、LCFS等。 例如 M/M/1：/FCFS 表示顾客到达的时间间隔是负指数分布，服务时间是负指数分布，一个服务台，排队系统和顾客源的

12、容量都是无限，实行先到先服务的一个服务系统。 9.1 排队论的基本概念 Basic Concepts of Queuing theory 第13页/共87页 2021年7月25日星期日 下一节：排队系统常用分布 9.1 排队论的基本概念 Basic Concepts of Queuing theory 第14页/共87页 9.2 排队系统常用分布 第15页/共87页 2021年7月25日星期日 9.2.1 负指数分布 随机变量T服从负指数分布，其分布函数为 t T etF 1)( 0, 0t 密度函数为 t T etf )( T的期望值为 00 1 )()( dtetdtttfTE t T T

13、的方差为 2 1 )( TVar 9.2 排队系统常用分布 第16页/共87页 2021年7月25日星期日 负指数分布具有性质 (1)密度函数 )(tfT 对时间t严格递减 tTPsTstTP (2)无记忆性或马尔柯夫性，即 (3)当顾客到达过程是泊松流时，顾客相继到达的间隔时间T 必服从负指数分布，这个性质将在定理9.1中予以证明。 若随机变量X的概率密度为 9.2.2泊松分布 (0,0,1,2,) ! ne P Xnn n 则称X服从参数为的泊松(Poisson)分布，记为XP()。其均值和方差分别为 )(XE)(XVar 9.2 排队系统常用分布 第17页/共87页 2021年7月25日

14、星期日 【定义9.1】对于随机过程 ,若满足 1.Poisson流的定义 9.2 顾客到达和服务的时间分布 0),(ttN (1)独立增量性(无后效性) 即对任意n个参数 增量 相互独立 或者说不相交的时间区间内到达的顾客数互相独立。 0 121 tttt nnn )()(,),()(),()( 12312 nn tNtNtNtNtNtN (2)增量平稳性 即在长度为 t 的时间区间内恰好到达k个顾客的概率仅与区间长度t有关，而与区间起始点无关 (3)普遍性 即当t充分小时，有 ( )2( )P N to t 称 为Poisson过程，N(t)服从泊松分布 ( ),0N tt 第18页/共87

15、页 2021年7月25日星期日 2排队系统与泊松过程 9.2 顾客到达和服务的时间分布 若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个以上的顾客到达的概率极小，以致于可以忽略 则认为顾客到达系统的过程是泊松过程，且 () ( ) ! k t t P N tke k 0,1,2,;0kt ( )E N t

16、t ( )Var N tt 第19页/共87页 2021年7月25日星期日 9.2 顾客到达和服务的时间分布 如果一个随机变量，概率分布与时间t有关，则称这个随机变量为一随机过程，排队系统中顾客到达的个数就是一个随机过程。 【定理9.1】在排队系统中，如果到达的顾客数服从以t为参数的泊松分布，则顾客相继到达的时间间隔服从以为参数的负指数分布. 证明参看教材。 由定理9.1可以看出，“到达的顾客数是一个以为参数的泊松流”与“顾客相继到达的时间间隔服从以为参数的负指数分布”两个事实是等价的 第20页/共87页 2021年7月25日星期日 【定理9.2】设X1,X2,，Xk ,是k个互相独立的，具有

17、相同参数的负指数分布随机变量，则随机变量 k XXXX 21 服从k阶爱尔朗(Erlang)分布，X的密度函数为 1 () ( )0 (1)! k k t kk t f tet k 记为 ( ) k XE 或简记为 k XE 随机变量X的均值和方差分别为： ()1/E X 2 ()1/Var Xk 9.2 排队系统常用分布 第21页/共87页 2021年7月25日星期日 为单位时间平均到达顾客数目，亦称平均到达率。顾客到达服从泊松分布，亦称顾客到达形成泊松流（最简单流）。 例1：一台仪表由1000个元件组成，每个元件在一年工作时间内发生故障的概率为0.001，并且与其它元件的状况无关，求在一年

18、内不少于2个元件发生故障的概率。 解： 设X=元件发生故障个数，由于n=1000 P=0.001很小，可视发生故障服从泊松分布，其中=nP=1 因此 264. 0 ! 1 1 ! 0 1 1101 1 1 1 0 eexPxP 9.2 顾客到达和服务的时间分布 000111 2 (2)1 n kkn knn nnn k p xC p qC p qC p q 第22页/共87页 2021年7月25日星期日 下一节： 单服务台模型 9.2 顾客到达和服务的时间分布 第23页/共87页 9.3单服务台模型M/M/1 第24页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 9.

19、3.1基本模型 / : 1/FCFSMM 设单位时间到达系统的顾客数为 ，单位时间被服务完的顾客数为。由于是单服务台，且顾客源无限，因此，在各种状态的情况下，系统的“出生率”为，系统的“死亡率”为。系统在稳态情况下的状态转移如图9-6所示 0 1 2 n- 1 n n+ 1 P0 P1 P2 Pn-1 Pn Pn+1 图9-6 根据以上状态转移图，可以得出如下平衡方程 0 01 PP 0)( 11 nnn PPP), 2 , 1(n (91) (92) 1 系统状态概率Pn(t)的计算 第25页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 由(91)和(92)可以递推

20、求解P1，P2，Pn，得到 01 PP 0 2 102 )1 (PPPP 0 PP n n ), 2 , 1(n 1 设 2 10200 , n n PP PPPP 1 0 P n n P)1 ( 1n 0 1 n n P 由，有 (93) (94) 表示平均到达率与平均服务率之比，称为服务强度 第26页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 【例9.1】高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为150辆小时，收费时间服从负指数分布，平均收费时间为15秒辆。求 (1)收费处空闲的概率； (2)收费处忙的概率； (3)系统中分别有1，2，

21、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)系统中有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 第27页/共87页 2021年7月25日星期日 2. 系统的运行指标 (1)系统中的平均顾客数（系统中

22、顾客数的期望值）L 1)1 ( )1 ( )1 ()1 ( 2 000k k kk k k kkkPL 即队长为系统中顾客数的期望值（系统中各种状态的加权平均值） (2)队列中的平均顾客数 q L 1)1 ( )1 ( ) 1()1 ()1 () 1() 1( 2 2 2 111k k kk k kq kkPkL LLq 9.3 单服务台模型 /1MM 第28页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM (3)顾客在系统中的平均逗留时间W 1 ()WE X (98) (4)顾客在队列中的平均逗留时间 Wq W WWq )( )( )(111 (99) 1 qq q

23、qq LW LW WW LLL (910) Little公式: 第29页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 【例9.2】轻轨进站口售票处设有一个售票窗口，乘客到达服从泊松分布，平均到达速率为200人/小时，售票时间服从负指数分布，平均售票时间为15秒/人。求L、Lq、W和Wq。 【解】根据题意，=200人/小时，=240人/小时，=5/6。 )(7590 )(90)(025. 0 200240 11 17. 45 5 11 6 5 6 5 6 5 6 5 秒 秒小时 WW W LL L q q 第30页/共87页 2021年7月25日星期日 9.3 单服务台

24、模型 /1MM 9.3.2有限队列模型 / : 1/FCFSNMM 如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某一时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。系统状态转移如图9-7 0 1 2 N- 1 N P0 P1 P2 图97 1.系统状态概率的计算 第31页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 由状态转移图9-7，建立系统概率平衡方程如下 10 11 1 (),1 kkk NN PP PPPkN PP (911) / 令 0 1 1 1 1 N P 1 1 1 k k N PkN 0 0 1 N

25、 k k P 100 PPP 2 210 PPP 10 k kk PPP 01 1 N PPP由有 (912) (913) 第32页/共87页 2021年7月25日星期日 93 单服务台模型 /1MM 1 1,2, 1 k PkN N ， 00 PPP k k N k k N 0 1 1当时 0 0 (1) N k k P 1 11 0 0 N P N k k 10 () k kk PPP (914) (915) 第33页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 根据式912和913可以导出系统的各个指标，对于1，有 (9-16) (1)系统中的平均顾客数L 1

26、00 11 12 1 1 1 1 1(1)(1) 111 (1) 11 NN k k N kk NN N N N LkPk N N 第34页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM (917) (2)队列中的平均顾客数Lq 0 000 1 111 11 11 (1)(1) 11 1 111 1()(1) 1 11 (1) (1) NNN qkkk kkk NN NNN NNNN NN N N LkPkPPLP LLL LL P LPL (1), e eNe P 令 qe LL (918) e 称为有效到达率，即单位时间内到达并能进入队列的平均顾客数。e 称为有效服

27、务强度 第35页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM (3)顾客在系统中的平均逗留时间W )1 ( Ne P LL W (9-19) (4)顾客在队列中的平均逗留时间 11 W LL L W ee e e q q (9-20) 第36页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 【例9.3】咨询中心有一位咨询工作人员，每次只能咨询一人，另外有4个座位供前来咨询的人等候。某人到来发现没有座位，就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速率为4人/小时，咨询人员的平均咨询时间为10分钟/人。咨询时间服从负指数分布。求： (1

28、)咨询者到达不用等待就可咨询的概率 (2)咨询中心的平均人数以及等待咨询的平均人数 (3)咨询者来咨询中心一次平均花费的时间以及平均等待的时间 (4)咨询者到达后因客满而离去的概率 (5)增加一个咨询工作人员可以减少的顾客损失率 【解】N=4+1=5，=4人/小时，=6人/小时，=2/3 2 3 06 1 2 3 11 0.365 1 1 N P 5 2 03 (1)(1)410.3653.808 N eN PP (1) 第37页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 423. 1577. 02 1 ) 15( 11 ) 1( 1 6 3 2 6 3 2 3 2

29、 3 2 1 1 N N N L 788. 0 6 808. 3 423. 1 e q LL (2) (3) )(4 .22)(374. 0 808. 3 423. 1 分小时 e L W )(4 .12)(207. 0 808. 3 788. 0 分小时 e q L W (4) 5 5 2 503 0.3650.048PP 因客满而离去的概率为0.048 (5) 当N=6时 2 3 06 1 2 3 11 0.365 1 1 N P 第38页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 6 6 2 603 0.3650.032PP 56 0.480.0320.016

30、1.6%PP 即增加一个咨询工作人员可以减少顾客损失率1.6% 9.3.3 有限顾客源模型 / : 1/FCFSmMM 设顾客总数为m。当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中，如此循环往复。由于顾客源的数量有限，因此队列的长度也是有限的，并且队列的长度必定小于顾客源总数 。 有限源系统顾客的平均到达速率： )(nm e 第39页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 0 1 2 n- 1 n m (1)m (1)mn n+1 m-1 m ()mn 图9-8 有限顾客源模型状态转移图 状态转移图如图9-8 由图9-8得到系统稳态概率平衡方程

31、组 1系统状态概率的计算 10 11 1 (1)(), 11 nnn mm Pm P PmnPmnPnm PP (921) 第40页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 用递推方法解该方程组，得到 m i i im m P 0 0 )!( ! 1 (922) 0 )!( ! P nm m P n n (923) 2 有限源系统的运行指标 在求得系统中出现顾客数的概率后，即可求得系统的运行指标(推导过程略) 第41页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM )1 ( 0 PmL )1 ()1)(1 ( 00 PLPmLq 1 )1

32、( 0 P m W 1 WWq (924) (925) (926) (927) 在机器维修问题中，L是待检修及正在检修的平均机器数，而 )1 ( 0 PLm 表示正常运行的平均机器数。 第42页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 【例9.4】某车间有5台机器，每台机器的连续运转时间服从负指数分布，一天（8小时）平均连续运行时间120分钟。有一个修理工，每次修理时间服从负指数分布，平均每次96分钟。求： (1)修理工忙的概率(记为Pb)； (2)五台机器都出故障的概率； (3)出故障的平均台数； (4)平均停工时间； (5)平均等待修理时间； (6)评价这个系

33、统的运行情况 【解】一天为一个单位时间。认为一天内来修理的机器数平均为4台，修理工一天平均修理机器数为5台。m=5，=4，=5，=0.8 1 012345 0 5!5!5!5!5!5! (1)(0.8)(0.8)(0.8)(0.8)(0.8)(0.8) 5!4!3!2!1!0! 1 0.0073 136.8 P 第43页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 0 11 0.00730.9927 b PP 5 50 5! (2)(0.8)0.287 0! PP 0 11 (3)(1)5(1 0.0073)3.76 0.8 LmP 0 (4)(1)3.76(1 0.

34、0073)2.77 q LLP 0 151 (5)0.7427()356 5 (1 0.0073) (1)4 m W P 天 （分钟） 11 (6)0.74270.5427()260 5 q WW 天 （分） 由计算结果看出，系统的修理工几乎没有空闲时间，机器的停工时间是平均运行时间的三倍，系统的服务效率很低 第44页/共87页 2021年7月25日星期日 9.3 单服务台模型 /1MM 作业：教材P216 T 1，2，3，4，5，6 下一节： 9.4多服务台模型 第45页/共87页 9.4多服务台模型M/M/s 第46页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs 9

35、.4.1基本模型 / :/M M sFCFS 规定各服务台工作相互独立且服务速率相同 s 21 系统的平均服务速率为 s s 令 0 1 2 s-1 s 2 sss s+1 n-1 n (1)s 图9-9 基本模型状态转移图 系统的状态转移图9-9。 第47页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs 稳态概率方程 10 PP (928) 120 )(2PPP (929) sss PsPsP)( 11 (930) nnn PsPsP)( 11 (931) 1 1 n n P 由 解得： 1 1 0 0 1 1 ! 1 ! s s n n n sn P snP ss s

36、nP n P snn n n n n 0 0 ! 1 ! (932) (933) 第48页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs 2 0 )1 ( ! s P L s s q q LL L W q q L W 顾客需要等待 (系统已有s个顾客)的概率 0 0 () () !(1)!(1) s s n n s Ps P nsPP ss 与单服务台系统的方法类似，有 第49页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs 【例9.5】银行办理个人储蓄业务有三个窗口，顾客到达服从泊松流，到达速率为0.9人分，办理业务时间服从负指数分布，每个窗口的平

37、均服务速率为0.4人分。顾客到达后取得一个排队号，依次由空闲窗口按号码顺序办理储蓄业务。求： (1)所有窗口都空闲的概率； (2)平均队长； (3)平均等待时间及逗留时间； (4)顾客到达后必须等待的概率。 【解】这是一个 / : 3/FCFSMM 系统 /2.25,/0.75s (1)所有窗口都空闲的概率，即求P0 0748. 0 75. 01 1 ! 3 )25. 2( ! 2 )25. 2( ! 1 )25. 2( ! 0 )25. 2( 1 3210 0 P 第50页/共87页 2021年7月25日星期日 (2)平均队长，先求Lq ,再求L 95. 325. 270. 1 70. 10

38、748. 0 )75. 01 (! 3 75. 0)25. 2( 2 3 q q LL L (3)平均等待时间和平均逗留时间，即求Wq和W的值 )(39. 4 4 . 0 1 89. 1 1 )(89. 1 9 . 0 70. 1 分 分 q q q WW L W (4)顾客到达后必须等待，即n3 57. 00748. 0 )75. 01 ( ! 3 )25. 2( 3 3 nP 9.4多服务台模型 /MMs 第51页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs 9.4.2有限队列模型 / :/MMsNFCFS 0 1 2 s-1 s 2 sss s+1 N-1 N (

39、1)s 图9-10 有限队列模型状态转移图 设系统容量为N(Ns)，当系统中的顾客数nN时，到达的顾客进入系统；当nN时，到达的顾客就被拒绝。设顾客到达的速率为，每个服务台服务的速率为， s/ 系统的状态转移图见图9-10 第52页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs 稳定状态的状态概率转移方程为： 10 PP 120 )(2PPP (938) (939) 21 (1) sss Ps PsP (940) sss PsPsP)( 11 12 )( sss PsPsP (941) (942) NN PsP 1 (943) 0 1 N n n P 得到系统稳态的状态概

40、率 由 1 1 )( ! )( 1 0 0 s k Nssk s s k s P (944) 1 1 0 0 1 (1)1 ! k s s k s PNs ks 第53页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs )( ! )0( ! )( 0 0 NnsP s s snP n s P ns n n (945) 系统的运行指标: 0 2 )1 ()(1 )1 ( ! )( PssN s s L NsN s q )1 ( Nq PsLL )1 ( N q q P L W 1 q WW (946) (947) (948) (949) 第54页/共87页 2021年7月25

41、日星期日 9.4多服务台模型 /MMs 【例9.6】某旅馆有10个床位，旅客到达服从泊松流，平均速率为6人天，旅客平均逗留时间为2天，求： (1)旅馆客满的概率； (2) 每天客房平均占用数. 【解】这是一个即时制的 /2:10/M MFCFS 系统，其中 16 10,6,0.5,2,12 0.5 Nss () 0 1 sN 1 012310 0 (12)(12)(12)(12)(12) 0.0018 0!1!2!3!10! P 10 100 ()(12) (1)0.00180.3019 !10! N s PP N 旅馆10个床位全满的概率为0.3019 (2)(1)12 (1 0.3019)

42、8.3772 s LsP 平均占用8.377个床位。客房占用率为83.77%。 第55页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs 9.4.3有限顾客源模型 / :/M M sm FCFS 设顾客源为有限数m，服务台个数为s，且ms。这个模型的典型例子是机器维修问题，机器数量为m台，修理工数量为s人 状态概率： s k m sk k s k mkms s m s kmk m P 01 0 )!( 1 !)!( ! 1 1 ! 1 s m mnsP ssnm m snP nnm m P n sn n n 1 !)!( ! 0 !)!( ! 0 0 式中： (951) (

43、950) 第56页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs 运行指标 m n n nPL 1 m sn nq PsnL 1 )( )(LmLLL q e q e LW/ eqq LW/ )(Lm e 为有效到达速率 式中 第57页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs 【例9.7】车间有5台机器，每台机器的故障率为1次小时，有2个修理工负责修理这5台机器，工作效率相同，为4台小时。求： (1)等待修理的平均机器数； (2)等待修理及正在修理的平均机器数； (3)每小时发生故障的平均机器数； (4)平均等待修理的时间； (5)平均停工时间

44、。 【解】这是一个 模型 /2:/5/M MFCFS 8 1 , 4 1 , 2, 4, 1, 5 mm s s m sm 0 01 1 012345 222 11 ! 11 !()!()! 111111121121 1211 0.3149 5!0!5! 41!4! 42!3! 42! 2! 82! 1! 82! 0! 8 kk ssm kk s P m ss k mkmsmkm 第58页/共87页 2021年7月25日星期日 9.4多服务台模型 /MMs P1=0.394， P2=0.197 ,P3=0.074， P4=0.018， P5=0.002 345 1 (1)()230.118 m

45、 qn n c Lns PPPP 092. 15432)2( 54321 1 PPPPPnPL m n n 908. 3)092. 15(1)() 3(Lm e )(8 . 1)(03. 0 908. 3 118. 0 )4(分小时 e q q L W )(8 .16)(28. 0 908. 3 902. 1 )5(分小时 e L W 由式(951)可以计算得到 第59页/共87页 2021年7月25日星期日 作业：教材P216 T 7，8 下一节：其它服务时间分布模型 9.4多服务台模型 /MMs 第60页/共87页 9.5其它服务时间分布模型 第61页/共87页 2021年7月25日星期日

46、 9.5 其它服务时间分布模型 9.5.1一般分布模型 /1:/M GFCFS G表示服务时间T的分布为任意的概率分布，但已知期望值E(T)和方差Var(T)。 该模型被称为“单服务台泊松到达、任意服务时间的排队模型” 在稳态情况下，当 时，可以证明下列PK (PollaczekKhint chine)公式成立： 1)(TE 12 )( 22 TVar L 1 0 P 12 )( 22 TVar Lq q q L W 1 q WW 其他指标为（推导过程略）： (957) (958) 第62页/共87页 2021年7月25日星期日 9.5 其它服务时间分布模型 【例9.8】某维修站有一技工修理出

47、故障机器。现已知机器按泊松流发生故障，平均故障率为每小时5台，机器排队有两种类型，一种修理时间为9分钟，另一种是12分钟，资料统计知，1/3故障需要修理12分钟。试求此维修站的运行指标。 【解】服务时间可以看成是二项分布 )/(6),(10 3 1 12 3 2 9 1 )(小时台分钟 TE )(210 3 1 12 3 2 9)( 2222 分TVar 利用PK公式求得 6 1 6 5 11 0 P 22 ( )51 (5( ) 2 163 Var T LVar T 2 2 51 5 5630 3.35() 56 2 1 6 台 第63页/共87页 2021年7月25日星期日 9.5 其它服

48、务时间分布模型 22 ( ) =0.5 5=2.5() 2 1 q Var T L 台 2.5 0.5() 5 q q L W 小时 1 =0.67() q WW 小时 9.5.2定长分布模型 /1:/M DFCFS 模型符号中的D表示服务时间为固定长度，即为常数.该模型被称为单服务台泊松到达、定长服务时间的排队模型. 因此，只需将模型中 的方差改为0，即可得到定长排队模型的各个指标。 /1:/M GFCFS 第64页/共87页 2021年7月25日星期日 9.5 其它服务时间分布模型 【解】服务时间定长，该服务系统是一个 / : 1/FCFSDM 排队系统，其中： =6辆/小时60/610辆

49、/小时 代入式(958)计算得 【例9.9】某汽车冲洗站有一套自动冲洗设备，冲洗每辆汽车所需时间为6分钟，到此冲洗站来冲洗汽车的到达过程服从泊松分布，每小时平均到达6辆，求该排队系统的有关运行指标。 4 . 0 10 6 11 0 P 22 (0.6) 0.45() 2 12(1 0.6) q L 辆 2 1.05() 2 1 q LL 辆 0.45 0.075() 6 q q L W 小时 11 0.0750.175() 10 q WW 小时 第65页/共87页 2021年7月25日星期日 9.5 其它服务时间分布模型 9.5.3爱尔朗分布模型 /1:/ k M EFCFS 在此模型中，每一

50、个顾客必须依次经过k个服务站，接受k次服务后才构成一个完整的服务过程。该模型假设每个服务站的服务时间Ti服务相同的负指数分布（参数为k）。则总的服务时间 k i i TT 1 服从k阶爱尔朗（Erlang）分布。其他条件与标准的M/M/1模型相同。 此模型的如下数量指标 1 0 P 11 2 12 q KK W KK 2 1 21 qq K LW K (959) (960) (961) 第66页/共87页 2021年7月25日星期日 9.5 其它服务时间分布模型 12 1 2 K K LL q (962) 1 q WW L W 或 (963) 在M/EK/1/FCFS排队系统中 ,而当K时，m

51、/EK/1/排队系统可认为为m/D/1排队系统。在m/D/1排队系统中 1212 1 lim K K W K q 1212 1 lim 22 K K L K q 1 12 1 12 1 lim 2 K K W K 11lim 0 K P 第67页/共87页 2021年7月25日星期日 9.8.2 M/D/1: / /FCFS 在m/D/1排队系统中 1212 1 lim K K W K q 1212 1 lim K K W K q 1212 1 lim 22 K K L K q 1 12 1 12 1 lim 2 K K W K 11lim 0 K P 第68页/共87页 2021年7月25日

52、星期日 9.5 其它服务时间分布模型 【例9.10】一个质量检查员平均每小时收到2件送来检验的样品，每件样品要依次完成5项检验才能判定是否合格。据统计，每项检验所需时间的期望值都是4分钟，每项检验的时间和送检产品的到达时间间隔都为负指数分布。求检验过程的各项指标。 【解】该检验系统是一个 排队系统，且 / : 1/ 5 FCFSEM 3 2 21 / 6030 （件 分钟） 1 20 （分钟/件） 22 () 15 q LL件 24( q q L W 分钟) 1 44() q WW 分钟 第69页/共87页 2021年7月25日星期日 作业：教材P216 T9，10，11 下一节：排队系统的优

53、化 9.5 其它服务时间分布模型 第70页/共87页 9.6排队系统的优 化 第71页/共87页 2021年7月25日星期日 9.6排队系统的优化 排队系统的费用包含以下两个方面：一个是服务费用，它是服务水平的递增函数；另一个是顾客等待的机会损失（费用），它是服务水平的递减函数。两者的总和呈一条U形曲线，如图9-11。 服务水平 费用 等待费用 服务费用 总费用 如图9-11 9.6.1排队系统经济分析 第72页/共87页 2021年7月25日星期日 9.6排队系统的优化 排队系统的优化问题常常分为两类：一类称之为系统的静态最优设计，目的在于使设备达到最大效益，或者说，在保证一定服务质量指标的

54、前提下，要求机构最为经济；另一类叫做系统动态最优运营，是指一个给定排队系统，如何运营可使某个目标函数得到最优。归纳起来，排队系统常见的优化问题有： （1）确定最优服务率 （2）确定最佳服务台数量 （3）选择最为合适的服务规则 （4）或是确定上述几个量的最佳组合 * * s 第73页/共87页 2021年7月25日星期日 式中：Cs 为 =1 时单位时间内的服务费用； Cw为每个顾客在系统中逗留单位时间的费用 稳态下取目标函数z为单位时间服务成本与顾客在系统逗留费用之和的期望值最小： min swsw ZCC LCC 2 * 1 0 () sw w s dZ CC d C C M/M/1/:/F

55、CFS 9.6排队系统的优化 9.6.2最优服务水平 * 的确定 1.基本模型 （965） (966) 第74页/共87页 2021年7月25日星期日 9.6排队系统的优化 【例9.11】某地欲兴建一座港口码头，但只有一个装卸船只的位置，现要求设计装卸能力，装卸能力用每天装卸的船只数表示。已知单位装卸能力每天平均生产成本为2000元，船只到港后若不能及时装卸，停留一天损失运输费1500元。预计船只的平均到达率为3只/天。设船只到达的时间间隔和装卸时间都服从负指数分布。问港口装卸能力为多大时，每天的总支出最少？ 【解】 Cs=2000元/天；Cw=1500元/天； =3只/天。由式(9.66)有

56、 * 1500 3 34.5() 2000 只/天 即最优装卸能力为4.5只/天。 第75页/共87页 2021年7月25日星期日 2.有限队列模型的最优服务率M/M/1/:N/FCFS 单位时间内达到系统的平均顾客数： (1) eN P 设服务一个顾客服务机构的收入为G，单位时间收入的期望值是 令0 dz d 1 1 12 (1) (1) N Ns N CNN G 给定N及Cs/G 求出* ,或给定Cs/G 及求N* 。 PN为被拒绝的概率，1-PN为能接受服务的概率. GPN)1 ( 1 11 1 max(1) 1 N Nss N NN s NN zP GcGc Gc 取纯利润最大: 9.6排队系统的优化 (968) 第76页/共87页 2021年7月25日星期日 9.6排队系统的优化 【例9.12】考虑一个具有=10人/小时，=30人/小时，N=2的 系统。 管理者想改进服务机构。方案一是增加等待空间N=3；方案二是提高平均服务率到=40人/小时，设服务每个顾客的平均收益不变，问哪个方案将获得更大的收益？当增加到每小时30人，又将是什么结果。 / : 1/FCFSNMM