1、Queuing theory第九章第九章 排队论排队论运筹学运筹学Operations Research9.1 排队论的基本概念排队论的基本概念9.2 排队系统常用分布排队系统常用分布 9.3 单服务台模型单服务台模型M/M/19.4 多服务台模型多服务台模型M/M/s9.5 其它服务时间分布模型其它服务时间分布模型9.6 排队系统的优化排队系统的优化 9.1 排队论的基本概念排队论的基本概念Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 3 2023年3月1日星期三9.1.1 排队系统的描述排队系统的描述排队系统的例子排队系统的例子9.1
2、 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 顾客顾客要求的服务要求的服务服务机构服务机构1借书的学生借书的学生2打电话打电话3提货者提货者4待降落的飞行器待降落的飞行器5储户储户6河水进入水库河水进入水库7购票旅客购票旅客8十字路口的汽车十字路口的汽车借书借书通话通话提货提货降落降落存款、取款存款、取款放水、调整水位放水、调整水位购票购票通过路口通过路口图书管理员图书管理员交换台交换台仓库管理员仓库管理员指挥塔台指挥塔台储蓄窗口、储蓄窗口、ATMD取款机取款机水库管理员水库管理员售票窗口售票窗口红绿灯或交警红绿灯或交警Ch9 排队论排队论
3、 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 4 2023年3月1日星期三顾客到达排队接受服务顾客离去图图9-1 排队系统排队系统排队的过程可表示为：排队的过程可表示为：9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 5 2023年3月1日星期三根据服务台的数量及排队方式，排队系统可以分为根据服务台的数量及排队方式，排队系统可以分为(1)单服务台单队单服务台单队(2)多服务台单队多服务台单队图图9-2
4、单服务台单队系统单服务台单队系统 顾客到达顾客到达进入队列进入队列服务台服务台接受服务接受服务顾客离去顾客离去顾客到达顾客到达服务台服务台顾客离去顾客离去服务台服务台服务台服务台图图9-3 多服务台单队系统多服务台单队系统9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 6 2023年3月1日星期三(3)多队多服务台多队多服务台(4)多服务台串联服务多服务台串联服务 图图9-4 多服务台多队系统多服务台多队系统图图9-5 多服务台串联系统
5、多服务台串联系统9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 顾客到达顾客到达服务台服务台顾客离去顾客离去服务台服务台服务台服务台顾客到达顾客到达服务台服务台顾客离去顾客离去服务台服务台Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 7 2023年3月1日星期三9.1.2排队系统的基本组成排队系统的基本组成排队系统由排队系统由输入过程输入过程、服务规则服务规则和和服务台服务台三个部分组成三个部分组成 这是指要求服务的顾客按怎样的规律到达排队系统的过程，这是指要求服务的顾客按怎样的规
6、律到达排队系统的过程，有时也称之为顾客流。有时也称之为顾客流。（1）顾客总体数，又称顾客源、输入源。顾客源可以是有）顾客总体数，又称顾客源、输入源。顾客源可以是有限的，也可以是无限的。限的，也可以是无限的。（2）顾客到达的形式。这是描述顾客是怎样来到系统的，）顾客到达的形式。这是描述顾客是怎样来到系统的，是单个到达，还是成批到达。是单个到达，还是成批到达。（3）顾客流的概率分布，或称顾客相继到达的时间间隔分）顾客流的概率分布，或称顾客相继到达的时间间隔分布。这是首先需要确定的指标。布。这是首先需要确定的指标。9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queui
7、ng theory 1.输入过程输入过程Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 8 2023年3月1日星期三(1)先到先服务（先到先服务（FCFS，First Come First Serve）；）；(2)后到先服务（后到先服务（LCFS，Last Come First Serve）；）；(3)有优先权的服务（有优先权的服务（PR，Priority）(4)随机服务（随机服务（SIRO，Service in Random Order）9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theor
8、y 2.排队规则排队规则(1)等待制等待制 指顾客到达系统后，所有服务台都不空，顾客加入排队行列指顾客到达系统后，所有服务台都不空，顾客加入排队行列等待服务，一直等到服务完毕以后才离去等待服务，一直等到服务完毕以后才离去；(2)损失制损失制 指当顾客到达系统时，所有服务台都已被占用，顾客不愿等指当顾客到达系统时，所有服务台都已被占用，顾客不愿等待而离开系统。待而离开系统。Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 9 2023年3月1日星期三(3)混合制混合制 这是等待制与损失制相结合的一种服务规则，一般是指允这是等待制与损失制相结合的
9、一种服务规则，一般是指允许排队，但又不允许队列无限长下去。大体有以下三种：许排队，但又不允许队列无限长下去。大体有以下三种：队长有限。当等待服务的顾客人数超过规定数量时，后来队长有限。当等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。的顾客就自动离去，另求服务，即系统的等待空间是有限的。等待时间有限。即顾客在系统中的等待时间不超过某一给等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度定的长度T，当等待时间超过时间，当等待时间超过时间T时，顾客将自动离去，并不时，顾客将自动离去，并不再回来。再回来。逗留时间（等待时间与服务时间之和）有限。逗留
10、时间（等待时间与服务时间之和）有限。9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 10 2023年3月1日星期三(1)服务台数量及构成形式服务台数量及构成形式 从数量上说，服务台有单台和多台之分。从构成形式上看，从数量上说，服务台有单台和多台之分。从构成形式上看，有单队单服务台式、单队多服务台并联式、多队多服务台并联有单队单服务台式、单队多服务台并联式、多队多服务台并联式、单队多服务台串联式等等，如图式、单队多服务台串联式等等，如图9
11、-2到到9-5所示；所示；(2)服务方式服务方式 指在某一时刻接受服务的顾客数，有单个服务和成批服务指在某一时刻接受服务的顾客数，有单个服务和成批服务两种；两种；(3)服务时间的分布服务时间的分布在多数情况下，对某一个顾客的服务时间是一随机变量，与在多数情况下，对某一个顾客的服务时间是一随机变量，与顾客到达的时间间隔分布一样，服务时间的分布有定长分布、顾客到达的时间间隔分布一样，服务时间的分布有定长分布、负指数分布、爱尔朗分布等等。负指数分布、爱尔朗分布等等。3.服务台服务台9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 服务台可以从以
12、下三个方面来描述：服务台可以从以下三个方面来描述：Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 11 2023年3月1日星期三9.1.3 排队系统的主要数量指标、记号和符号排队系统的主要数量指标、记号和符号 9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory（1）队长和队列长）队长和队列长(排队长排队长)队长是指系统中的顾客数（排队等待的顾客数与正在接受队长是指系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和）服务的顾客数之和）队列长是指系统中正在排队等待服务的顾客数。队长和
13、队队列长是指系统中正在排队等待服务的顾客数。队长和队列长一般都是随机变量列长一般都是随机变量（2）等待时间和逗留时间）等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止这段时间称为等待从顾客到达时刻起到他开始接受服务止这段时间称为等待时间。从顾客到达时刻起到他接受服务完止这段时间称为逗留时间。从顾客到达时刻起到他接受服务完止这段时间称为逗留时间。两种时间都是随机变量时间。两种时间都是随机变量（3）忙期和闲期）忙期和闲期 忙期是指从顾客到达空闲着的服务机构起，到服务再次成忙期是指从顾客到达空闲着的服务机构起，到服务再次成为空闲止的这段时间，服务机构连续忙的时间。这是个随机变为空闲止的这段时间
14、，服务机构连续忙的时间。这是个随机变量。与忙期相对的是闲期，即服务机构连续保持空闲的时间。量。与忙期相对的是闲期，即服务机构连续保持空闲的时间。1.主要数量指标主要数量指标Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 12 2023年3月1日星期三9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 2.记号记号时刻时刻 t 系统中的顾客数（又称为系统的状态），即队长；系统中的顾客数（又称为系统的状态），即队长；时刻时刻 t 系统中排队的顾客数，即列队长；系统中排队的顾客数，即列队长；时
15、刻时刻 t 到达系统的顾客在系统中的逗留时间；到达系统的顾客在系统中的逗留时间；时刻时刻 t 到达系统的顾客在系统中的等待时间到达系统的顾客在系统中的等待时间():N t():qNt():T t():qT tL：平均队长，即稳态系统任一时刻顾客数的期望值；：平均队长，即稳态系统任一时刻顾客数的期望值；Lq：平均等待队长，即稳态系统任一时刻等待服务的顾客数的：平均等待队长，即稳态系统任一时刻等待服务的顾客数的期望值；期望值；W：平均逗留时间，即在任一时刻进入稳态系统的顾客逗留时：平均逗留时间，即在任一时刻进入稳态系统的顾客逗留时间的期望值；间的期望值；Wq：平均等待时间，即在任一时刻进入稳态系统
16、的顾客等待时：平均等待时间，即在任一时刻进入稳态系统的顾客等待时间的期望值；间的期望值；在平稳状态下在平稳状态下:Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 13 2023年3月1日星期三9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory：顾客到达的平均速率，即单位时间内平均到达的顾客数；：顾客到达的平均速率，即单位时间内平均到达的顾客数；1/：平均到达时间间隔；：平均到达时间间隔；：平均服务速率，即单位时间内服务完毕离去的顾客数；：平均服务速率，即单位时间内服务完毕离去的顾客数；1
17、/：平均服务时间；：平均服务时间；s：系统中服务台的个数；：系统中服务台的个数；：服务强度，即每个服务台单位时间内的平均服务时间，一：服务强度，即每个服务台单位时间内的平均服务时间，一般有般有/(s)；N：稳态系统任一时刻的状态（即系统中所有顾客数）；：稳态系统任一时刻的状态（即系统中所有顾客数）；U：任一顾客在稳态系统中的逗留时间；：任一顾客在稳态系统中的逗留时间；Q：任一顾客在稳态系统中的等待时间；：任一顾客在稳态系统中的等待时间；PnPN=n：稳态系统任一时刻状态为：稳态系统任一时刻状态为n的概率；特别当的概率；特别当n=0时，时，PnP0，即稳态系统所有服务台全部空闲的概率；，即稳态系
18、统所有服务台全部空闲的概率；e：有效平均到达率，即期望每单位时间内来到系统（包括未：有效平均到达率，即期望每单位时间内来到系统（包括未进入系统）的概率。进入系统）的概率。Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 14 2023年3月1日星期三 3.排队系统的符号排队系统的符号一个排队系统的特征可以用六个参数表示，形式为：一个排队系统的特征可以用六个参数表示，形式为：XYZ：ABC 或或 X/Y/Z/A/B/C其中其中X 顾客到达的概率分布，可取顾客到达的概率分布，可取M、D、Ek、G等；等；Y 服务时间的概率分布，可取服务时间的概率分
19、布，可取M、D、Ek、G等；等；Z 服务台个数，取正整数；服务台个数，取正整数；A 排队系统的最大容量，可取正整数或排队系统的最大容量，可取正整数或；B 顾客源的最大容量，可取正整数或顾客源的最大容量，可取正整数或；C 排队规则，可取排队规则，可取FCFS、LCFS等。等。例如例如M/M/1：/FCFS表示顾客到达的时间间隔是负指数分布，服务时间是负指数分表示顾客到达的时间间隔是负指数分布，服务时间是负指数分布，一个服务台，排队系统和顾客源的容量都是无限，实行先布，一个服务台，排队系统和顾客源的容量都是无限，实行先到先服务的一个服务系统。到先服务的一个服务系统。9.1 排队论的基本概念排队论的
20、基本概念Basic Concepts of Queuing theory Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 15 2023年3月1日星期三下一节：排队系统常用分布下一节：排队系统常用分布9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 9.2 排队系统常用分布排队系统常用分布Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 17 2023年3月1日星期三9.2.1 负指数分布负指数分布随机变量随机变量T服从负指数分布，其
21、分布函数为服从负指数分布，其分布函数为 tTetF1)(0,0t密度函数为密度函数为tTetf)(T的期望值为的期望值为001)()(dtetdtttfTEtTT的方差为的方差为21)(TVar9.2 排队系统常用分布排队系统常用分布Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 18 2023年3月1日星期三负指数分布具有性质负指数分布具有性质(1)密度函数密度函数)(tfT对时间对时间t严格递减严格递减tTPsTstTP(2)无记忆性或马尔柯夫性，即无记忆性或马尔柯夫性，即(3)当顾客到达过程是泊松流时，顾客相继到达的间隔时间当顾客到达
22、过程是泊松流时，顾客相继到达的间隔时间T 必必服从负指数分布，这个性质将在定理服从负指数分布，这个性质将在定理9.1中予以证明。中予以证明。若随机变量若随机变量X的概率密度为的概率密度为9.2.2泊松分布泊松分布(0,0,1,2,)!neP Xnnn则称则称X服从参数为服从参数为的泊松的泊松(Poisson)分布，记为分布，记为XP()。其均值。其均值和方差分别为和方差分别为)(XE)(XVar9.2 排队系统常用分布排队系统常用分布Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 19 2023年3月1日星期三【定义【定义9.1】对于随机过
23、程对于随机过程 ,若满足若满足1.Poisson流的定义流的定义9.2 顾客到达和服务的时间分布顾客到达和服务的时间分布0),(ttN(1)独立增量性独立增量性(无后效性无后效性)即对任意即对任意n个参数个参数 增量增量 相互独立相互独立 或者说不相交的时间区间内到达的顾客数互相独立。或者说不相交的时间区间内到达的顾客数互相独立。0121ttttnnn)()(,),()(),()(12312nntNtNtNtNtNtN(2)增量平稳性增量平稳性 即在长度为即在长度为 t 的时间区间内恰好到达的时间区间内恰好到达k个顾客个顾客的概率仅与区间长度的概率仅与区间长度t有关，而与区间起始点无关有关，而
24、与区间起始点无关(3)普遍性普遍性 即当即当t充分小时，有充分小时，有()2()P N to t称称 为为Poisson过程，过程，N(t)服从泊松分布服从泊松分布(),0N tt Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 20 2023年3月1日星期三2排队系统与泊松过程排队系统与泊松过程 9.2 顾客到达和服务的时间分布顾客到达和服务的时间分布若若N(t)为时间区间为时间区间0,t）(t0)内到达系统的顾客数，则内到达系统的顾客数，则N(t)是一个是一个随机变量，且随机变量，且 N(t)|t(0,T)为一个随机过程。若该随机过程满
25、为一个随机过程。若该随机过程满足足（1）在不相重叠的区间内，顾客的到达数是相互独立的；）在不相重叠的区间内，顾客的到达数是相互独立的；（2）在时间区间）在时间区间t,t+t）内有顾客的到达数只与区间长度）内有顾客的到达数只与区间长度t有关，而与区间起始点有关，而与区间起始点t无关；无关；（3）对于充分小的）对于充分小的t，在时间区间，在时间区间t,t+t）内有）内有2个或个或2个以个以上的顾客到达的概率极小，以致于可以忽略上的顾客到达的概率极小，以致于可以忽略 则认为顾客到达系统的过程是泊松过程，且则认为顾客到达系统的过程是泊松过程，且()()!kttP N tkek0,1,2,;0kt()E
26、 N tt()Var N ttCh9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 21 2023年3月1日星期三9.2 顾客到达和服务的时间分布顾客到达和服务的时间分布 如果一个随机变量，概率分布与时间如果一个随机变量，概率分布与时间t有关，则称这个随机变有关，则称这个随机变量为一随机过程，排队系统中顾客到达的个数就是一个随机过量为一随机过程，排队系统中顾客到达的个数就是一个随机过程。程。【定理【定理9.1】在排队系统中，如果到达的顾客数服从以在排队系统中，如果到达的顾客数服从以t为参数为参数的泊松分布，则顾客相继到达的时间间隔服从以的泊松分布
27、，则顾客相继到达的时间间隔服从以为参数的负指为参数的负指数分布数分布.证明参看教材。证明参看教材。由定理由定理9.1可以看出，可以看出，“到达的顾客数是一个以到达的顾客数是一个以为参数的泊松为参数的泊松流流”与与“顾客相继到达的时间间隔服从以为参数的负指数分布顾客相继到达的时间间隔服从以为参数的负指数分布”两个事实是等价的两个事实是等价的 Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 22 2023年3月1日星期三【定理【定理9.2】设设X1,X2,，Xk,是是k个互相独立的，具有相同参数个互相独立的，具有相同参数的负指数分布随机变量，则
28、随机变量的负指数分布随机变量，则随机变量kXXXX21服从服从k阶爱尔朗阶爱尔朗(Erlang)分布，分布，X的密度函数为的密度函数为1()()0(1)!kk tkk tf tetk记为记为()kXE或简记为或简记为kXE随机变量随机变量X的均值和方差分别为：的均值和方差分别为：()1/E X2()1/Var Xk9.2 排队系统常用分布排队系统常用分布Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 23 2023年3月1日星期三为单位时间平均到达顾客数目，亦称平均到达率。顾客到达服为单位时间平均到达顾客数目，亦称平均到达率。顾客到达服从泊
29、松分布，亦称顾客到达形成泊松流（最简单流）。从泊松分布，亦称顾客到达形成泊松流（最简单流）。例例1：一台仪表由：一台仪表由1000个元件组成，每个元件在一年工作时间个元件组成，每个元件在一年工作时间内发生故障的概率为内发生故障的概率为0.001，并且与其它元件的状况无关，求在，并且与其它元件的状况无关，求在一年内不少于一年内不少于2个元件发生故障的概率。个元件发生故障的概率。解：解：设设X=元件发生故障个数，由于元件发生故障个数，由于n=1000 P=0.001很小，可很小，可视发生故障服从泊松分布，其中视发生故障服从泊松分布，其中=nP=1 因此因此 264.0!11!0111011110e
30、exPxP9.2 顾客到达和服务的时间分布顾客到达和服务的时间分布0001112(2)1nkkn knnnnnkp xC p qC p qC p q Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 24 2023年3月1日星期三下一节：下一节：单服务台模型单服务台模型 9.2 顾客到达和服务的时间分布顾客到达和服务的时间分布9.3单服务台模型单服务台模型M/M/1Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 26 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM9.3.
31、1基本模型基本模型M/M/1:/FCFS 设单位时间到达系统的顾客数为设单位时间到达系统的顾客数为，单位时间被服务完的顾客，单位时间被服务完的顾客数为数为。由于是单服务台，且顾客源无限，因此，在各种状态。由于是单服务台，且顾客源无限，因此，在各种状态的情况下，系统的的情况下，系统的“出生率出生率”为为，系统的，系统的“死亡率死亡率”为为。系统在稳态情况下的状态转移如图系统在稳态情况下的状态转移如图9-6所示所示 0 1 2n-1 nn+1P0 P1 P2 Pn-1 Pn Pn+1 图图9-6根据以上状态转移图，可以得出如下平衡方程根据以上状态转移图，可以得出如下平衡方程 001 PP0)(11
32、nnnPPP),2,1(n(91)1 系统状态概率系统状态概率Pn(t)的计算的计算021()0PPPCh9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 27 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM由由(91)可以递推求解可以递推求解P1，P2，Pn，得到，得到 01PP02102)1(PPPP0PPnn),2,1(n1设210200,nnPP PPPP10PnnP)1(1n01nnP由，有(92)(93)表示平均到达率与平均服务率之比，称为服务强度表示平均到达率与平均服务率之比，称为服务强度 Ch9 排队论排队论 Q
33、ueuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 28 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM【例【例91】高速公路收费处设有一个收费通道，汽车到达服从】高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为泊松分布，平均到达速率为150辆小时，收费时间服从负指数辆小时，收费时间服从负指数分布，平均收费时间为分布，平均收费时间为15秒辆。求秒辆。求(1)收费处空闲的概率；收费处空闲的概率；(2)收费处忙的概率；收费处忙的概率；(3)系统中分别有系统中分别有1，2，3辆车的概率。辆车的概率。【解】根据题意【解】根据题意,=150
34、辆辆/小时小时,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.091Ch9 排队论排队论 Q
35、ueuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 29 2023年3月1日星期三2.系统的运行指标系统的运行指标(1)系统中的平均顾客数（系统中顾客数的期望值）系统中的平均顾客数（系统中顾客数的期望值）L 1)1()1()1()1(2000kkkkkkkkkPL即队长为系统中顾客数的期望值（系统中各种状态的加权平均即队长为系统中顾客数的期望值（系统中各种状态的加权平均值）值）(2)队列中的平均顾客数队列中的平均顾客数qL111222(1)(1)(1)(1)(1)(1)(1)1kkqkkkkLkPkkLLLq9.3 单服务台模型单服务台模型/1MM(94)(95)Ch
36、9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 30 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM(3)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间W1()WE X(97)(4)顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间 WqWWWq)()()(111(98)1qqqqqLWLWWWLLL(99)Little公式公式:Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 31 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM【例【例92】轻轨进
37、站口售票处设有一个售票窗口，乘客到达服】轻轨进站口售票处设有一个售票窗口，乘客到达服从泊松分布，平均到达速率为从泊松分布，平均到达速率为200人人/小时，售票时间服从负指小时，售票时间服从负指数分布，平均售票时间为数分布，平均售票时间为15秒秒/人。求人。求L、Lq、W和和Wq。【解】根据题意，【解】根据题意，=200人人/小时，小时，=240人人/小时，小时，=5/6。)(7590)(90)(025.02002401117.4551165656565秒秒小时WWWLLLqqCh9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 32 2023年3
38、月1日星期三9.3 单服务台模型单服务台模型/1MM9.3.2有限队列模型有限队列模型/:1/FCFSNMM 如果系统的最大容量为如果系统的最大容量为N，对于单服务台的情形，排队等待，对于单服务台的情形，排队等待的顾客最多为的顾客最多为N-1-1，在某一时刻一顾客到达时，如系统中已有，在某一时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。系统状态转移如个顾客，那么这个顾客就被拒绝进入系统。系统状态转移如图图9-7 0 1 2N-1 NP0 P1 P2 图图971.系统状态概率的计算系统状态概率的计算Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大
39、学管理学院 熊伟 Page 33 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM由状态转移图由状态转移图9-7，建立系统概率平衡方程如下，建立系统概率平衡方程如下 10111(),1kkkNNPPPPPkNPP(910)/令01111NP111kkNPkN001NkkP100PPP2210PPP10kkkPPP011NPPP由有(911)(912)Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 34 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM111,2,11kkPkNNN，00PPPkkNkkN011
40、当时00(1)NkkP11100NPNkk10()kkkPPP(913)(914)Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 35 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM根据式根据式911和和912可以导出系统的各个指标，对于可以导出系统的各个指标，对于1，有，有(9-15)(1)系统中的平均顾客数系统中的平均顾客数L100111211111(1)(1)111(1)11NNkkNkkNNNNNLkPkNNCh9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 36
41、2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM(916)(2)队列中的平均顾客数队列中的平均顾客数Lq 000011111111(1)(1)1111111()(1)111(1)(1)NNNqkkkkkkNNNNNNNNNNNNNLkPkPPLPLLLLLPLPL(1),eeNeP令qeLL(917)e 称为有效到达率，即单位时间内到达并能进入队列的平均顾称为有效到达率，即单位时间内到达并能进入队列的平均顾客数。客数。e 称为有效服务强度称为有效服务强度 Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 37 2023年3月1
42、日星期三9.3 单服务台模型单服务台模型/1MM(3)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间W)1(NePLLW(9-18)(4)顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间 11WLLLWeeeeqq(9-19)Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 38 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM【例【例93】咨询中心有一位咨询工作人员，每次只能咨询一人，】咨询中心有一位咨询工作人员，每次只能咨询一人，另外有另外有4个座位供前来咨询的人等候。某人到来发现没有座位，个座位供前来咨询的人等
43、候。某人到来发现没有座位，就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速率为率为4人人/小时，咨询人员的平均咨询时间为小时，咨询人员的平均咨询时间为10分钟分钟/人。咨询时间人。咨询时间服从负指数分布。求：服从负指数分布。求：(1)咨询者到达不用等待就可咨询的概率咨询者到达不用等待就可咨询的概率(2)咨询中心的平均人数以及等待咨询的平均人数咨询中心的平均人数以及等待咨询的平均人数(3)咨询者来咨询中心一次平均花费的时间以及平均等待的时间咨询者来咨询中心一次平均花费的时间以及平均等待的时间(4)咨询者到达后因客满而离去的概率咨询者
44、到达后因客满而离去的概率(5)增加一个座位可以减少的顾客损失率增加一个座位可以减少的顾客损失率【解【解】N=4+1=5，=4人人/小时，小时，=6人人/小时，小时，=2/3 2306123110.36511NP 5203(1)(1)410.3653.808NeNPP(1)Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 39 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM 423.1577.021)15(11)1(1632632323211NNNL788.06808.3423.1eqLL(2)(3)(4.22)(374.08
45、08.3423.1分小时 eLW0.7880.207()12.4()3.808qqeLW小时分(4)5525030.3650.048PP因客满而离去的概率为因客满而离去的概率为0.048(5)当当N=6时时 2307123110.35411NPCh9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 40 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM 6626030.3650.0311PP560.0480.03110.01691.69%PP即增加一个座位可以减少顾客损失率即增加一个座位可以减少顾客损失率1.6%9.3.3 有限顾客
46、源模型有限顾客源模型/:1/FCFSmMM 设顾客总数为设顾客总数为m。当顾客需要服务时，就进入队列等待；服。当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中，如此循环往复。由于顾客源的务完毕后，重新回到顾客源中，如此循环往复。由于顾客源的数量有限，因此队列的长度也是有限的，并且队列的长度必定数量有限，因此队列的长度也是有限的，并且队列的长度必定小于顾客源总数小于顾客源总数。有限源系统顾客的平均到达速率：有限源系统顾客的平均到达速率：)(nmeCh9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 41 2023年3月1日星期三9.3
47、 单服务台模型单服务台模型/1MM 0 1 2n-1 nm(1)m(1)mnn+1m-1 m()mn图图9-8 有限顾客源模型状态转移图有限顾客源模型状态转移图状态转移图如图状态转移图如图9-8 由图由图9-8得到系统稳态概率平衡方程组得到系统稳态概率平衡方程组 1系统状态概率的计算系统状态概率的计算10111(1)(),11nnnmmPm PPmnPmnPnmPP(920)Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 42 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM用递推方法解该方程组，得到用递推方法解该方程组，得
48、到 miiimmP00)!(!1(921)0)!(!PnmmPnn(922)2 有限源系统的运行指标有限源系统的运行指标 在求得系统中出现顾客数的概率后，即可求得系统的运行指标在求得系统中出现顾客数的概率后，即可求得系统的运行指标(推导过程略推导过程略)Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 43 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM)1(0PmL)1()1)(1(00PLPmLq1)1(0PmW1WWq(923)(924)(925)(926)在机器维修问题中，在机器维修问题中，L是待检修及正在检修的平均
49、机器数，而是待检修及正在检修的平均机器数，而)1(0PLm表示正常运行的平均机器数。表示正常运行的平均机器数。Ch9 排队论排队论 Queuing theory 制作与教学 武汉理工大学管理学院 熊伟 Page 44 2023年3月1日星期三9.3 单服务台模型单服务台模型/1MM【例【例9-4】某车间有】某车间有5台机器，每台机器的连续运转时间服从负指台机器，每台机器的连续运转时间服从负指数分布，一天（数分布，一天（8小时）平均连续运行时间小时）平均连续运行时间120分钟。有一个修理分钟。有一个修理工，每次修理时间服从负指数分布，平均每次工，每次修理时间服从负指数分布，平均每次96分钟。求：
50、分钟。求：(1)修理工忙的概率修理工忙的概率(记为记为Pb)；(2)五台机器都出故障的概率；五台机器都出故障的概率；(3)出故障的平均台数；出故障的平均台数；(4)平均停工时间；平均停工时间；(5)平均等待修理时间；平均等待修理时间；(6)评价这个系统的运行情况评价这个系统的运行情况【解】一天为一个单位时间。认为一天内来修理的机器数平均为【解】一天为一个单位时间。认为一天内来修理的机器数平均为4台，修理工一天平均修理机器数为台，修理工一天平均修理机器数为5台。台。m=5，=4，=5，=0.8 101234505!5!5!5!5!5!(1)(0.8)(0.8)(0.8)(0.8)(0.8)(0.
