Ch9排队论PPT参考课件.ppt

Queuing theory第九章第九章 排队论排队论运筹学运筹学Operations Research9.1 排队论的基本概念排队论的基本概念9.2 排队系统常用分布排队系统常用分布 9.3 单服务台模型单服务台模型M/M/19.4 多服务台模型多服务台模型M/M/s9.5 其它服务时间分布模型其它服务时间分布模型9.6 排队系统的优化排队系统的优化 07 十一月 20249.1 排队论的基本概念排队论的基本概念07 十一月 2024Ch9 排队论排队论 Queuing theory Page 3 9.1.1 排队系统的描述排队系统的描述排队系统的例子排队系统的例子9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 顾客顾客要求的服务要求的服务服务机构服务机构1借书的学生借书的学生2打电话打电话3提货者提货者4待降落的飞行器待降落的飞行器5储户储户6河水进入水库河水进入水库7购票旅客购票旅客8十字路口的汽车十字路口的汽车借书借书通话通话提货提货降落降落存款、取款存款、取款放水、调整水位放水、调整水位购票购票通过路口通过路口图书管理员图书管理员交换台交换台仓库管理员仓库管理员指挥塔台指挥塔台储蓄窗口、储蓄窗口、ATMD取款机取款机水库管理员水库管理员售票窗口售票窗口红绿灯或交警红绿灯或交警Ch9 排队论排队论 Queuing theory Page 4 顾客到达排队接受服务顾客离去图图9-1 排队系统排队系统排队的过程可表示为：排队的过程可表示为：9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory Ch9 排队论排队论 Queuing theory Page 5 根据服务台的数量及排队方式，排队系统可以分为根据服务台的数量及排队方式，排队系统可以分为(1)单服务台单队单服务台单队(2)多服务台单队多服务台单队图图9-2单服务台单队系统单服务台单队系统 顾客到达顾客到达进入队列进入队列服务台服务台接受服务接受服务顾客离去顾客离去顾客到达顾客到达服务台服务台顾客离去顾客离去服务台服务台服务台服务台图图9-3 多服务台单队系统多服务台单队系统9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory Ch9 排队论排队论 Queuing theory Page 6 (3)多队多服务台多队多服务台(4)多服务台串联服务多服务台串联服务 图图9-4 多服务台多队系统多服务台多队系统图图9-5 多服务台串联系统多服务台串联系统9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 顾客到达顾客到达服务台服务台顾客离去顾客离去服务台服务台服务台服务台顾客到达顾客到达服务台服务台顾客离去顾客离去服务台服务台Ch9 排队论排队论 Queuing theory Page 7 9.1.2排队系统的基本组成排队系统的基本组成排队系统由排队系统由输入过程输入过程、服务规则服务规则和和服务台服务台三个部分组成三个部分组成 这是指要求服务的顾客按怎样的规律到达排队系统的过程，这是指要求服务的顾客按怎样的规律到达排队系统的过程，有时也称之为顾客流。有时也称之为顾客流。（1）顾客总体数，又称顾客源、输入源。顾客源可以是有）顾客总体数，又称顾客源、输入源。顾客源可以是有限的，也可以是无限的。限的，也可以是无限的。（2）顾客到达的形式。这是描述顾客是怎样来到系统的，）顾客到达的形式。这是描述顾客是怎样来到系统的，是单个到达，还是成批到达。是单个到达，还是成批到达。（3）顾客流的概率分布，或称顾客相继到达的时间间隔分）顾客流的概率分布，或称顾客相继到达的时间间隔分布。这是首先需要确定的指标。布。这是首先需要确定的指标。9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 1.输入过程输入过程Ch9 排队论排队论 Queuing theory Page 8 (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 theory 2.排队规则排队规则(1)等待制等待制 指顾客到达系统后，所有服务台都不空，顾客加入排队行列指顾客到达系统后，所有服务台都不空，顾客加入排队行列等待服务，一直等到服务完毕以后才离去等待服务，一直等到服务完毕以后才离去；(2)损失制损失制 指当顾客到达系统时，所有服务台都已被占用，顾客不愿等指当顾客到达系统时，所有服务台都已被占用，顾客不愿等待而离开系统。待而离开系统。Ch9 排队论排队论 Queuing theory Page 9 (3)混合制混合制 这是等待制与损失制相结合的一种服务规则，一般是指允这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。大体有以下三种：许排队，但又不允许队列无限长下去。大体有以下三种：队长有限。当等待服务的顾客人数超过规定数量时，后来队长有限。当等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。的顾客就自动离去，另求服务，即系统的等待空间是有限的。等待时间有限。即顾客在系统中的等待时间不超过某一给等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度定的长度T，当等待时间超过时间，当等待时间超过时间T时，顾客将自动离去，并不时，顾客将自动离去，并不再回来。再回来。逗留时间（等待时间与服务时间之和）有限。逗留时间（等待时间与服务时间之和）有限。9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory Ch9 排队论排队论 Queuing theory Page 10 (1)服务台数量及构成形式服务台数量及构成形式 从数量上说，服务台有单台和多台之分。从构成形式上看，从数量上说，服务台有单台和多台之分。从构成形式上看，有单队单服务台式、单队多服务台并联式、多队多服务台并联有单队单服务台式、单队多服务台并联式、多队多服务台并联式、单队多服务台串联式等等，如图式、单队多服务台串联式等等，如图9-2到到9-5所示；所示；(2)服务方式服务方式 指在某一时刻接受服务的顾客数，有单个服务和成批服务指在某一时刻接受服务的顾客数，有单个服务和成批服务两种；两种；(3)服务时间的分布服务时间的分布在多数情况下，对某一个顾客的服务时间是一随机变量，与在多数情况下，对某一个顾客的服务时间是一随机变量，与顾客到达的时间间隔分布一样，服务时间的分布有定长分布、顾客到达的时间间隔分布一样，服务时间的分布有定长分布、负指数分布、爱尔朗分布等等。负指数分布、爱尔朗分布等等。3.服务台服务台9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 服务台可以从以下三个方面来描述：服务台可以从以下三个方面来描述：Ch9 排队论排队论 Queuing theory Page 11 9.1.3 排队系统的主要数量指标、记号和符号排队系统的主要数量指标、记号和符号 9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory（1）队长和队列长）队长和队列长(排队长排队长)队长是指系统中的顾客数（排队等待的顾客数与正在接受队长是指系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和）服务的顾客数之和）队列长是指系统中正在排队等待服务的顾客数。队长和队队列长是指系统中正在排队等待服务的顾客数。队长和队列长一般都是随机变量列长一般都是随机变量（2）等待时间和逗留时间）等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止这段时间称为等待从顾客到达时刻起到他开始接受服务止这段时间称为等待时间。从顾客到达时刻起到他接受服务完止这段时间称为逗留时间。从顾客到达时刻起到他接受服务完止这段时间称为逗留时间。两种时间都是随机变量时间。两种时间都是随机变量（3）忙期和闲期）忙期和闲期 忙期是指从顾客到达空闲着的服务机构起，到服务再次成忙期是指从顾客到达空闲着的服务机构起，到服务再次成为空闲止的这段时间，服务机构连续忙的时间。这是个随机变为空闲止的这段时间，服务机构连续忙的时间。这是个随机变量。与忙期相对的是闲期，即服务机构连续保持空闲的时间。量。与忙期相对的是闲期，即服务机构连续保持空闲的时间。1.主要数量指标主要数量指标Ch9 排队论排队论 Queuing theory Page 12 9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 2.记号记号时刻时刻 t 系统中的顾客数（又称为系统的状态），即队长；系统中的顾客数（又称为系统的状态），即队长；时刻时刻 t 系统中排队的顾客数，即列队长；系统中排队的顾客数，即列队长；时刻时刻 t 到达系统的顾客在系统中的逗留时间；到达系统的顾客在系统中的逗留时间；时刻时刻 t 到达系统的顾客在系统中的等待时间到达系统的顾客在系统中的等待时间 L：平均队长，即稳态系统任一时刻顾客数的期望值；：平均队长，即稳态系统任一时刻顾客数的期望值；Lq：平均等待队长，即稳态系统任一时刻等待服务的顾客数的：平均等待队长，即稳态系统任一时刻等待服务的顾客数的期望值；期望值；W：平均逗留时间，即在任一时刻进入稳态系统的顾客逗留时：平均逗留时间，即在任一时刻进入稳态系统的顾客逗留时间的期望值；间的期望值；Wq：平均等待时间，即在任一时刻进入稳态系统的顾客等待时：平均等待时间，即在任一时刻进入稳态系统的顾客等待时间的期望值；间的期望值；在平稳状态下在平稳状态下:Ch9 排队论排队论 Queuing theory Page 13 9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory：顾客到达的平均速率，即单位时间内平均到达的顾客数；：顾客到达的平均速率，即单位时间内平均到达的顾客数；1/：平均到达时间间隔；：平均到达时间间隔；：平均服务速率，即单位时间内服务完毕离去的顾客数；：平均服务速率，即单位时间内服务完毕离去的顾客数；1/：平均服务时间；：平均服务时间；s：系统中服务台的个数；：系统中服务台的个数；：服务强度，即每个服务台单位时间内的平均服务时间，一：服务强度，即每个服务台单位时间内的平均服务时间，一般有般有/(s)；N：稳态系统任一时刻的状态（即系统中所有顾客数）；：稳态系统任一时刻的状态（即系统中所有顾客数）；U：任一顾客在稳态系统中的逗留时间；：任一顾客在稳态系统中的逗留时间；Q：任一顾客在稳态系统中的等待时间；：任一顾客在稳态系统中的等待时间；PnPN=n：稳态系统任一时刻状态为：稳态系统任一时刻状态为n的概率；特别当的概率；特别当n=0时，时，PnP0，即稳态系统所有服务台全部空闲的概率；，即稳态系统所有服务台全部空闲的概率；e：有效平均到达率，即期望每单位时间内来到系统（包括未：有效平均到达率，即期望每单位时间内来到系统（包括未进入系统）的概率。进入系统）的概率。Ch9 排队论排队论 Queuing theory Page 14 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表示顾客到达的时间间隔是负指数分布，服务时间是负指数分表示顾客到达的时间间隔是负指数分布，服务时间是负指数分布，一个服务台，排队系统和顾客源的容量都是无限，实行先布，一个服务台，排队系统和顾客源的容量都是无限，实行先到先服务的一个服务系统。到先服务的一个服务系统。9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory Ch9 排队论排队论 Queuing theory Page 15 下一节：排队系统常用分布下一节：排队系统常用分布9.1 排队论的基本概念排队论的基本概念Basic Concepts of Queuing theory 9.2 排队系统常用分布排队系统常用分布07 十一月 2024Ch9 排队论排队论 Queuing theory Page 17 9.2.1 负指数分布负指数分布随机随机变变量量T服从负指数分布，其分布函数为服从负指数分布，其分布函数为 密度函数为密度函数为T的期望值为的期望值为T的方差为的方差为9.2 排队系统常用分布排队系统常用分布Ch9 排队论排队论 Queuing theory Page 18 负指数分布具有性质负指数分布具有性质(1)密度函数密度函数对时间对时间t严格递减严格递减(2)无记忆性或马尔柯夫性，即无记忆性或马尔柯夫性，即(3)当顾客到达过程是泊松流时，顾客相继到达的间隔时间当顾客到达过程是泊松流时，顾客相继到达的间隔时间T 必必服从负指数分布，这个性质将在定理服从负指数分布，这个性质将在定理9.1中予以证明。中予以证明。若随机变量若随机变量X的概率密度为的概率密度为9.2.2泊松分布泊松分布则称则称X服从参数为服从参数为的泊松的泊松(Poisson)分布，记为分布，记为XP()。其均值。其均值和方差分别为和方差分别为 9.2 排队系统常用分布排队系统常用分布Ch9 排队论排队论 Queuing theory Page 19 【定义定义9.1】对于随机过程对于随机过程 ,若满足若满足1.Poisson流的定义流的定义9.2 顾客到达和服务的时间分布顾客到达和服务的时间分布(1)独立增量性独立增量性(无后效性无后效性)即对任意即对任意n个参数个参数 增量增量 相互独立相互独立 或者说不相交的时间区间内到达的顾客数互相独立。或者说不相交的时间区间内到达的顾客数互相独立。(2)增量平稳性增量平稳性 即在长度为即在长度为 t 的时间区间内恰好到达的时间区间内恰好到达k个顾客个顾客的概率仅与区间长度的概率仅与区间长度t有关，而与区间起始点无关有关，而与区间起始点无关(3)普遍性普遍性 即当即当t充分小时，有充分小时，有称称 为为Poisson过程，过程，N(t)服从泊松分布服从泊松分布 Ch9 排队论排队论 Queuing theory Page 20 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个以个以上的顾客到达的概率极小，以致于可以忽略上的顾客到达的概率极小，以致于可以忽略 则认为顾客到达系统的过程是泊松过程，且则认为顾客到达系统的过程是泊松过程，且 Ch9 排队论排队论 Queuing theory Page 21 9.2 顾客到达和服务的时间分布顾客到达和服务的时间分布 如果一个随机变量，概率分布与时间如果一个随机变量，概率分布与时间t有关，则称这个随机变有关，则称这个随机变量为一随机过程，排队系统中顾客到达的个数就是一个随机过量为一随机过程，排队系统中顾客到达的个数就是一个随机过程。程。【定理定理9.1】在排队系统中，如果到达的顾客数服从以在排队系统中，如果到达的顾客数服从以t为参数为参数的泊松分布，则顾客相继到达的时间间隔服从以的泊松分布，则顾客相继到达的时间间隔服从以为参数的负指为参数的负指数分布数分布.证明参看教材。证明参看教材。由定理由定理9.1可以看出，可以看出，“到达的顾客数是一个以到达的顾客数是一个以为参数的泊松流为参数的泊松流”与与“顾客相继到达的时间间隔服从以为参数的负指数分布顾客相继到达的时间间隔服从以为参数的负指数分布”两个事实是等价的两个事实是等价的 Ch9 排队论排队论 Queuing theory Page 22 【定理定理9.2】设设X1,X2,，Xk,是是k个互相独立的，具有相同参数个互相独立的，具有相同参数的负指数分布随机变量，则随机变量的负指数分布随机变量，则随机变量服从服从k阶爱尔朗阶爱尔朗(Erlang)分布，分布，X的密度函数为的密度函数为记为记为或简记为或简记为随机变量随机变量X的均值和方差分别为：的均值和方差分别为：9.2 排队系统常用分布排队系统常用分布Ch9 排队论排队论 Queuing theory Page 23 为单位时间平均到达顾客数目，亦称平均到达率。顾客到达服为单位时间平均到达顾客数目，亦称平均到达率。顾客到达服从泊松分布，亦称顾客到达形成泊松流（最简单流）。从泊松分布，亦称顾客到达形成泊松流（最简单流）。例例1：一台仪表由：一台仪表由1000个元件组成，每个元件在一年工作时间个元件组成，每个元件在一年工作时间内发生故障的概率为内发生故障的概率为0.001，并且与其它元件的状况无关，求在，并且与其它元件的状况无关，求在一年内不少于一年内不少于2个元件发生故障的概率。个元件发生故障的概率。解：解：设设X=元件发生故障个数，由于元件发生故障个数，由于n=1000 P=0.001很小，可很小，可视发生故障服从泊松分布，其中视发生故障服从泊松分布，其中=nP=1 因此因此 9.2 顾客到达和服务的时间分布顾客到达和服务的时间分布Ch9 排队论排队论 Queuing theory Page 24 下一节：下一节：单服务台模型单服务台模型 9.2 顾客到达和服务的时间分布顾客到达和服务的时间分布9.3单服务台模型单服务台模型M/M/107 十一月 2024Ch9 排队论排队论 Queuing theory Page 26 9.3 单服务台模型单服务台模型 9.3.1基本模型基本模型设单位时间到达系统的顾客数为设单位时间到达系统的顾客数为，单位时间被服务完的顾客，单位时间被服务完的顾客数为数为。由于是单服务台，且顾客源无限，因此，在各种状态。由于是单服务台，且顾客源无限，因此，在各种状态的情况下，系统的的情况下，系统的“出生率出生率”为为，系统的，系统的“死亡率死亡率”为为。系统在稳态情况下的状态转移如图系统在稳态情况下的状态转移如图9-6所示所示 0 1 2n-1 nn+1P0 P1 P2 Pn-1 Pn Pn+1 图图9-6根据以上状态转移图，可以得出如下平衡方程根据以上状态转移图，可以得出如下平衡方程(91)(92)1 系统状态概率系统状态概率Pn(t)的计算的计算Ch9 排队论排队论 Queuing theory Page 27 9.3 单服务台模型单服务台模型 由由(91)和和(92)可以递推求解可以递推求解P1，P2，Pn，得到，得到(93)(94)表示平均到达率与平均服务率之比，称为服务强度表示平均到达率与平均服务率之比，称为服务强度 Ch9 排队论排队论 Queuing theory Page 28 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)系统中有系统中有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 排队论排队论 Queuing theory Page 29 2.系统的运行指标系统的运行指标(1)系统中的平均顾客数（系统中顾客数的期望值）系统中的平均顾客数（系统中顾客数的期望值）L 即队长为系统中顾客数的期望值（系统中各种状态的加权平均即队长为系统中顾客数的期望值（系统中各种状态的加权平均值）值）(2)队列中的平均顾客数队列中的平均顾客数9.3 单服务台模型单服务台模型 Ch9 排队论排队论 Queuing theory Page 30 9.3 单服务台模型单服务台模型(3)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间W(98)(4)顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间 Wq(99)(910)Little公式公式:Ch9 排队论排队论 Queuing theory Page 31 9.3 单服务台模型单服务台模型【例例9.2】轻轨进站口售票处设有一个售票窗口，乘客到达服从轻轨进站口售票处设有一个售票窗口，乘客到达服从泊松分布，平均到达速率为泊松分布，平均到达速率为200人人/小时，售票时间服从负指数小时，售票时间服从负指数分布，平均售票时间为分布，平均售票时间为15秒秒/人。求人。求L、Lq、W和和Wq。【解解】根据题意，根据题意，=200人人/小时，小时，=240人人/小时，小时，=5/6。Ch9 排队论排队论 Queuing theory Page 32 9.3 单服务台模型单服务台模型 9.3.2有限队列模型有限队列模型 如果系统的最大容量为如果系统的最大容量为N，对于单服务台的情形，排队等待，对于单服务台的情形，排队等待的顾客最多为的顾客最多为N-1-1，在某一时刻一顾客到达时，如系统中已有，在某一时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。系统状态转移如个顾客，那么这个顾客就被拒绝进入系统。系统状态转移如图图9-7 0 1 2N-1 NP0 P1 P2 图图971.系统状态概率的计算系统状态概率的计算Ch9 排队论排队论 Queuing theory Page 33 9.3 单服务台模型单服务台模型 由状态转移图由状态转移图9-7，建立系统概率平衡方程如下，建立系统概率平衡方程如下(911)(912)(913)Ch9 排队论排队论 Queuing theory Page 34 93 单服务台模型单服务台模型(914)(915)Ch9 排队论排队论 Queuing theory Page 35 9.3 单服务台模型单服务台模型 根据式根据式912和和913可以导出系统的各个指标，对于可以导出系统的各个指标，对于1，有，有(9-16)(1)系统中的平均顾客数系统中的平均顾客数LCh9 排队论排队论 Queuing theory Page 36 9.3 单服务台模型单服务台模型(917)(2)队列中的平均顾客数队列中的平均顾客数Lq(918)e 称为有效到达率，即单位时间内到达并能进入队列的平均顾称为有效到达率，即单位时间内到达并能进入队列的平均顾客数。客数。e 称为有效服务强度称为有效服务强度 Ch9 排队论排队论 Queuing theory Page 37 9.3 单服务台模型单服务台模型(3)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间W(9-19)(4)顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间(9-20)Ch9 排队论排队论 Queuing theory Page 38 9.3 单服务台模型单服务台模型【例例9.3】咨询中心有一位咨询工作人员，每次只能咨询一人，咨询中心有一位咨询工作人员，每次只能咨询一人，另外有另外有4个座位供前来咨询的人等候。某人到来发现没有座位，个座位供前来咨询的人等候。某人到来发现没有座位，就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速就不再等待而离去。前来咨询者到达服从泊松流，到达的平均速率为率为4人人/小时，咨询人员的平均咨询时间为小时，咨询人员的平均咨询时间为10分钟分钟/人。咨询时间人。咨询时间服从负指数分布。求：服从负指数分布。求：(1)咨询者到达不用等待就可咨询的概率咨询者到达不用等待就可咨询的概率(2)咨询中心的平均人数以及等待咨询的平均人数咨询中心的平均人数以及等待咨询的平均人数(3)咨询者来咨询中心一次平均花费的时间以及平均等待的时间咨询者来咨询中心一次平均花费的时间以及平均等待的时间(4)咨询者到达后因客满而离去的概率咨询者到达后因客满而离去的概率(5)增加一个咨询工作人员可以减少的顾客损失率增加一个咨询工作人员可以减少的顾客损失率【解解】N=4+1=5，=4人人/小时，小时，=6人人/小时，小时，=2/3(1)Ch9 排队论排队论 Queuing theory Page 39 9.3 单服务台模型单服务台模型(2)(3)(4)因客满而离去的概率为因客满而离去的概率为0.048(5)当当N=6时时Ch9 排队论排队论 Queuing theory Page 40 9.3 单服务台模型单服务台模型 即增加一个咨询工作人员可以减少顾客损失率即增加一个咨询工作人员可以减少顾客损失率1.6%9.3.3 有限顾客源模型有限顾客源模型 设顾客总数为设顾客总数为m。当顾客需要服务时，就进入队列等待；服。当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中，如此循环往复。由于顾客源的务完毕后，重新回到顾客源中，如此循环往复。由于顾客源的数量有限，因此队列的长度也是有限的，并且队列的长度必定数量有限，因此队列的长度也是有限的，并且队列的长度必定小于顾客源总数小于顾客源总数。有限源系统顾客的平均到达速率：有限源系统顾客的平均到达速率：Ch9 排队论排队论 Queuing theory Page 41 9.3 单服务台模型单服务台模型 0 1 2n-1 nn+1m-1 m图图9-8 有限顾客源模型状态转移图有限顾客源模型状态转移图状态转移图如图状态转移图如图9-8 由图由图9-8得到系统稳态概率平衡方程组得到系统稳态概率平衡方程组 1系统状态概率的计算系统状态概率的计算(921)Ch9 排队论排队论 Queuing theory Page 42 9.3 单服务台模型单服务台模型 用递推方法解该方程组，得到用递推方法解该方程组，得到(922)(923)2 有限源系统的运行指标有限源系统的运行指标 在求得系统中出现顾客数的概率后，即可求得系统的运行指标在求得系统中出现顾客数的概率后，即可求得系统的运行指标(推导过程略推导过程略)Ch9 排队论排队论 Queuing theory Page 43 9.3 单服务台模型单服务台模型(924)(925)(926)(927)在机器维修问题中，在机器维修问题中，L是待检修及正在检修的平均机器数，而是待检修及正在检修的平均机器数，而表示正常运行的平均机器数。表示正常运行的平均机器数。Ch9 排队论排队论 Queuing theory Page 44 9.3 单服务台模型单服务台模型【例例9.4】某车间有某车间有5台机器，每台机器的连续运转时间服从负指台机器，每台机器的连续运转时间服从负指数分布，一天（数分布，一天（8小时）平均连续运行时间小时）平均连续运行时间120分钟。有一个修理分钟。有一个修理工，每次修理时间服从负指数分布，平均每次工，每次修理时间服从负指数分布，平均每次96分钟。求：分钟。求：(1)修理工忙的概率修理工忙的概率(记为记为Pb)；(2)五台机器都出故障的概率；五台机器都出故障的概率；(3)出故障的平均台数；出故障的平均台数；(4)平均停工时间；平均停工时间；(5)平均等待修理时间；平均等待修理时间；(6)评价这个系统的运行情况评价这个系统的运行情况【解解】一天为一个单位时间。认为一天内来修理的机器数平均为一天为一个单位时间。认为一天内来修理的机器数平均为4台，修理工一天平均修理机器数为台，修理工一天平均修理机器数为5台。台。m=5，=4，=5，=0.8 Ch9 排队论排队论 Queuing theory Page 45 9.3 单服务台模型单服务台模型 由计算结果看出，系统的修理工几乎没有空闲时间，机器的停工由计算结果看出，系统的修理工几乎没有空闲时间，机器的停工时间是平均运行时间的三倍，系统的服务效率很低时间是平均运行时间的三倍，系统的服务效率很低 Ch9 排队论排队论 Queuing theory Page 46 9.3 单服务台模型单服务台模型 作业：教材作业：教材P216 T 1，2，3，4，5，6下一节：下一节：9.4多服务台模型多服务台模型9.4多服务台模型多服务台模型M/M/s07 十一月 2024Ch9 排队论排队论 Queuing theory Page 48 9.4多服务台模型多服务台模型9.4.1基本模型基本模型 规定各服务台工作相互独立且服务速率相同规定各服务台工作相互独立且服务速率相同 系统的平均服务速率为系统的平均服务速率为 s令令 0 1 2s-1 ss+1n-1 n图图9-9 基本模型状态转移图基本模型状态转移图系统的状态转移图系统的状态转移图9-9。Ch9 排队论排队论 Queuing theory Page 49 9.4多服务台模型多服务台模型稳态概率方程稳态概率方程(928)(929)(930)(931)由由解得：解得：(932)(933)Ch9 排队论排队论 Queuing theory Page 50 9.4多服务台模型多服务台模型顾客需要等待顾客需要等待(系统已有系统已有s个顾客个顾客)的概率的概率与单服务台系统的方法类似，有与单服务台系统的方法类似，有 Ch9 排队论排队论 Queuing theory Page 51 9.4多服务台模型多服务台模型【例例9.5】银行办理个人储蓄业务有三个窗口，顾客到达服从泊松银行办理个人储蓄业务有三个窗口，顾客到达服从泊松流，到达速率为流，到达速率为0.9人分，办理业务时间服从负指数分布，每个人分，办理业务时间服从负指数分布，每个窗口的平均服务速率为窗口的平均服务速率为0.4人分。顾客到达后取得一个排队号，人分。顾客到达后取得一个排队号，依次由空闲窗口按号码顺序办理储蓄业务。求：依次由空闲窗口按号码顺序办理储蓄业务。求：(1)所有窗口都空闲的概率；所有窗口都空闲的概率；(2)平均队长；平均队长；(3)平均等待时间及逗留时间；平均等待时间及逗留时间；(4)顾客到达后必须等待的概率。顾客到达后必须等待的概率。【解解】这是一个这是一个系统系统(1)所有窗口都空闲的概率，即求所有窗口都空闲的概率，即求P0Ch9 排队论排队论 Queuing theory Page 52 (2)平均队长，先求平均队长，先求Lq,再求再求L(3)平均等待时间和平均逗留时间，即求平均等待时间和平均逗留时间，即求Wq和和W的值的值(4)顾客到达后必须等待，即顾客到达后必须等待，即n3 9.4多服务台模型多服务台模型Ch9 排队论排队论 Queuing theory Page 53 9.4多服务台模型多服务台模型9.4.2有限队列模型有限队列模型 0 1 2s-1 ss+1N-1 N图图9-10 有限队列模型状态转移图有限队列模型状态转移图设系统容量为设系统容量为N(Ns)，当系统中的顾客数，当系统中的顾客数nN时，到达的顾客进时，到达的顾客进入系统；当入系统；当nN时，到达的顾客就被拒绝。设顾客到达的速率为时，到达的顾客就被拒绝。设顾客到达的速率为，每个服务台服务的速率为，每个服务台服务的速率为，系统的状态转移图见图系统的状态转移图见图9-10 Ch9 排队论排队论 Queuing theory Page 54 9.4多服务台模型多服务台模型稳定状态的状态概率转移方程为：稳定状态的状态概率转移方程为：(938)(939)(940)(941)(942)(943)得到系统稳态的状态概率得到系统稳态的状态概率 由由(944)Ch9 排队论排队论 Queuing theory Page 55 9.4多服务台模型多服务台模型(945)系统的运行指标系统的运行指标:(946)(947)(948)(949)Ch9 排队论排队论 Queuing theory Page 56 9.4多服务台模型多服务台模型【例例9.6】某旅馆有某旅馆有10个床位，旅客到达服从泊松流，平均速率为个床位，旅客到达服从泊松流，平均速率为6人天，旅客平均逗留时间为人天，旅客平均逗留时间为2天，求：天，求：(1)旅馆客满的概率；旅馆客满的概率；(2)每天客房平均占用数每天客房平均占用数.【解解】这是一个即时制的这是一个即时制的 系统，其中系统，其中 旅馆旅馆10个床位全满的概率为个床位全满的概率为0.3019平均占用平均占用8.377个床位。客房占用率为个床位。客房占用率为83.77%。Ch9 排队论排队论 Queuing theory Page 57 9.4多服务台模型多服务台模型9.4.3有限顾客源模型有限顾客源模型 设顾客源为有限数设顾客源为有限数m，服务台个数为，服务台个数为s，且，且ms。这个模型的典型。这个模型的典型例子是机器维修问题，机器数量为例子是机器维修问题，机器数量为m台，修理工数量为台，修理工数量为s人人 状态概率：状态概率：式中：式中：(951)(950)Ch9 排队论排队论 Queuing theory Page 58 9.4多服务台模型多服务台模型运行指标运行指标 为有效到达速率为有效到达速率 式中式中Ch9 排队论排队论 Queuing theory Page 59 9.4多服务台模型多服务台模型【例例9.7】车间有车间有5台机器，每台机器的故障率为台机器，每台机器的故障率为1次小时，有次小时，有2个修理工负责修理这个修理工负责修理这5台机器，工作效率相同，为台机器，工作效率相同，为4台小时。求：台小时。求：(1)等待修理的平均机器数；等待修理的平均机器数；(2)等待修理及正在修理的平均机器数；等待修理及正在修理的平均机器数；(3)每小时发生故障的平均机器数；每小时发生故障的平均机器数；(4)平均等待修理的时间；平均等待修理的时间；(5)平均停工时间。平均停工时间。【解解】这是一个这是一个 模型模型Ch9 排队论排队论 Queuing theory Page 60 9.4多服务台模型多服务台模型P1=0.394，P2=0.197,P3=0.074，P4=0.01