排队论(随机服务系统).ppt

《排队论(随机服务系统).ppt》由会员分享，可在线阅读，更多相关《排队论(随机服务系统).ppt（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排队论排队论排队论排队论(Queueing Theory)(Queueing Theory)(Queueing Theory)(Queueing Theory)（随机服务系统）（随机服务系统）（随机服务系统）（随机服务系统）第一节 第二节 第三节1大纲要求：掌握排队论的基本概念、常见的到达时间间隔分布和服务时间分布特性，生灭过程及稳态概率。单服务台负指数分布排队模型；多服务台负指数排队模型；排队系统设计的最优化重点：掌握M/M/1模型及其应用难点：到达流的稳态概率和系统状态转移概率及其优化服务设计自学：M/G/1模型2 排排队队论论（Queueing Theory)，也也称称随随机机服服务务系

2、系统统理论，是运筹学的一个重要分支之一。理论，是运筹学的一个重要分支之一。1909年年，丹丹麦麦哥哥本本哈哈根根电电子子公公司司电电话话工工程程师师A.K.Erlang的的开开创创性性论论文文“概概率率论论和和电电话话通通讯讯理理论论”标标志志此此理理论论的的诞诞生生。排排队队论论的的发发展展最最早早是是与与电电话话，通通信信中中的的问问题题相相联联系系的的，这这些些问问题题到到现现在在仍仍是是排排队队论论传传统统的的应用领域。应用领域。近近年年来来在在计计算算机机通通讯讯、网网络络系系统统、交交通通运运输输、医医疗疗卫卫生生系系统统、库库存存管管理理、作作战战指指挥挥等等各各领领域域中中均均

3、得得到到了广泛的应用。了广泛的应用。各种排队问题：各种排队问题：3 机械坏了 修理 修理工人 修理工人 领取配件 管理员 病人 就诊 医生 打电话 通话 交换台 文件 打印 打印机 飞机降落 降落 跑道指挥机构 顾客 就餐 服务员 汽车 路口 红绿灯4 1.1 1.1 排队系统的组成与特征排队系统的组成与特征 首先看一下一般排队系统的组成示意图，不难发首先看一下一般排队系统的组成示意图，不难发现排队系统一般有三个基本组成部分：现排队系统一般有三个基本组成部分：1.1.输入过程；输入过程；2.2.排队规则；排队规则；3.3.服务机构。现分别说明：服务机构。现分别说明：1 1 排队系统的基本概念排

4、队系统的基本概念5 输入即为顾客的到达，可有下列情况：输入即为顾客的到达，可有下列情况：1）顾客源可能是有限的，也可能是无限的。顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单个到达。顾客是成批到达或是单个到达。3）顾客到达的间隔时间可能是随机的或确定的。顾客到达的间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立的或关联的。所谓顾客到达可能是相互独立的或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。独立就是以前顾客的到达对以后顾客的到达无影响。5）输入过程可以是输入过程可以是平稳的平稳的（stationarystationary），），也也可以是可以是非平稳的非

5、平稳的。输入过程是平稳的是指顾客相继。输入过程是平稳的是指顾客相继到达的间隔时间分布和参数（均值、方差）与时间到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比无关；非平稳的则是与时间相关，非平稳的处理比较困难。较困难。1.1.输入过程输入过程6 2.排队规则排队规则 1）顾客到达后接受服务，服务分为顾客到达后接受服务，服务分为即时制即时制（损（损失制）和失制）和等待制等待制。即时制不允许排队，不形成队列；。即时制不允许排队，不形成队列；而对于等待制将会形成队列，顾客可以按下规则接而对于等待制将会形成队列，顾客可以按下规则接收服务：收服务：(1)(1)先到

6、先服务先到先服务 FCFS;(2)FCFS;(2)后到先服务后到先服务 LCFS LCFS(3)(3)随机服务随机服务RAND;RAND;（4 4）有优先权服务有优先权服务 PSPS。2）从队列的空间可分为有容量限制和无容量限从队列的空间可分为有容量限制和无容量限制。也可分为有形的和抽象的。制。也可分为有形的和抽象的。3 3）从队列数可分为单列和多列。（多列时包括）从队列数可分为单列和多列。（多列时包括各列间可以相互转移、各列间可以相互转移、不能相互转移不能相互转移；中途可退出、；中途可退出、中途不能退出中途不能退出等。）等。）73 3.服务机构服务机构 1 1）服服务务机机构构分分为为单单服

7、服务务台台和和多多服服务务台台。不不同同的的输输入入形形式式与与排排队队规规则则和和服服务务机机构构联联合合后后形形成成不不同的排队服务机构，如：同的排队服务机构，如：8 2)2)服务方式分为单个顾客服务和成批顾客服务。服务方式分为单个顾客服务和成批顾客服务。3)3)服务时间分为确定型服务时间分为确定型(定常时间）和随机型。定常时间）和随机型。4)4)服务时间的分布在这里我们假定是平稳的。服务时间的分布在这里我们假定是平稳的。我们研究的问题是：输入是服从某种分布，我们研究的问题是：输入是服从某种分布，顾客的到达是相互独立到达的平稳过程；各列顾客的到达是相互独立到达的平稳过程；各列间不能相互转移

8、、中途不能退出；单个单个地间不能相互转移、中途不能退出；单个单个地服务方式，服务服从某种分布，服务方式，服务服从某种分布，FCFS FCFS。9最主要的、影响最大的是：最主要的、影响最大的是：顾客相继到达的间隔时间分布顾客相继到达的间隔时间分布服务时间的分布服务时间的分布服务台数服务台数，19531953提出了分类法，称为提出了分类法，称为KendallKendall记号记号(适用于并适用于并列服务台列服务台),1971),1971又扩展成为：又扩展成为：X/Y/Z/A/B/CX/Y/Z/A/B/C11.2.2 排队系统的模型分类排队系统的模型分类10 式中：式中：X 或或Y 表表示示顾顾客客

9、相相继继到到达达时时间间间间隔隔分分布布和和服服务时间分布的各种分布符号：务时间分布的各种分布符号：M负指数分布（负指数分布具有无记忆性，即Markov性）；D确定型（Deterministic）分布；EkK阶爱尔朗分布Erlang；GI 一 般 相 互 独 立 随 机 分 布(General Independent)；G 一般随机分布。11Z填写并列的服务台数填写并列的服务台数A排队系统的最大容量排队系统的最大容量NB顾客源数量顾客源数量m C排队规则（排队规则（FCFS、LCFS等。本章仅研究等。本章仅研究FCFS的排队规则）的排队规则）如如 M/M/1/M/M/1/FCFS/FCFS/F

10、CFS/FCFS即为顾客到达时间间隔即为顾客到达时间间隔为负指数分布，服务时间为负指数分布，单台，为负指数分布，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。无限容量，无限源，先到先服务的排队系统模型。12 11.3.3 排队论研究的基本问题排队论研究的基本问题 1.1.排队系统的统计推断排队系统的统计推断:即通过对排队系统主即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。据排队理论进行研究。2.2.系统性态问题

11、系统性态问题:即研究各种排队系统的概率即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标期分布等统计指标,包括了瞬态和稳态两种情形。包括了瞬态和稳态两种情形。3.3.最优化问题：即包括最优设计最优化问题：即包括最优设计(静态优化静态优化)，最优运营（动态优化）。最优运营（动态优化）。13 统计推断 最优设计 性态问题 排队系统研究问题阶段示意图排队系统研究问题阶段示意图141.4 1.4 排队问题求解排队问题求解(主要指性态问题主要指性态问题)求求解解一一般般排排队队系系统统问问题题的的目目的的主主要要是是通通过过研研究

12、究排排队队系系统统运运行行的的效效率率指指标标，估估计计服服务务质质量量，确确定定系系统统的的合合理理结结构构和和系系统统参参数数的的合合理理值值，以以便便实实现现对对现现有有系统合理改进和对新建系统的最优设计等。系统合理改进和对新建系统的最优设计等。认识系统：系统分析；改造系统：设计系统。认识系统：系统分析；改造系统：设计系统。排队问题的求解：排队问题的求解：1 1、确确定定或或拟拟合合排排队队系系统统顾顾客客到到达达时时间间间间隔隔的的时时间间分布和服务时间分布分布和服务时间分布(可实测可实测)。15 2 2、根据排队系统对应的理论模型、根据排队系统对应的理论模型求出用以求出用以判断系统运

13、行优劣的基本数量指标的概率分布或判断系统运行优劣的基本数量指标的概率分布或特征数。特征数。数量指标主要包括数量指标主要包括:(1)(1)队长：队长：系统中的顾客数，它的数学期望记为系统中的顾客数，它的数学期望记为L Ls s 。队列长：队列长：系统中排队等待服务的顾客数，它系统中排队等待服务的顾客数，它的数学期望记为的数学期望记为L Lq q 。系统中顾客数系统中顾客数L Ls s=系统中排队等待服务的顾系统中排队等待服务的顾客数客数L Lq q+正被服务的顾客数正被服务的顾客数(2)(2)逗留时间逗留时间：指一个顾客在系统中的停留时间，指一个顾客在系统中的停留时间，它的数学期望记为它的数学期

14、望记为WsWs。16 等待时间：等待时间：指一个顾客在系统中排队等待的指一个顾客在系统中排队等待的时间，它的数学期望记为时间，它的数学期望记为Wq Wq。逗留时间逗留时间=等待时间等待时间+服务时间服务时间(3)(3)忙期：忙期：指从顾客到达空闲服务机构起到服务指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）的指标，忙期关系到工作强度）为了计算上述的数量指标，必须首先计算系为了计算上述的数量指标，必须首先计算系统状态

15、的概率统状态的概率 系统状态系统状态：系统状态是指系统中顾客数。：系统状态是指系统中顾客数。17 状态概率状态概率：用：用P Pn n(t)(t)表示表示,即在即在t t时刻系统中有时刻系统中有n n个个顾客的概率，也称瞬态概率。它是表述系统的各种性顾客的概率，也称瞬态概率。它是表述系统的各种性能指标的基础。能指标的基础。状态的可能值：状态的可能值：队长没有限制时：队长没有限制时：n=0，1，2，队长有限制时：队长有限制时：n=0，1，2，3，N 即时制：服务台个数是即时制：服务台个数是c时，时，n=0，1，c 求解状态概率求解状态概率P Pn n(t)(t)方法：是建立含方法：是建立含P P

16、n n(t)(t)的微的微分差分方程，通过求解微分差分方程得到系统瞬分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的便求得一般也很难使用。因此我们常常使用它的极限极限(如果存在的话如果存在的话)：18 稳态的物理意义见右图，稳态的物理意义见右图，系统的稳态一般很快都系统的稳态一般很快都能达到，但实际中达不能达到，但实际中达不到稳态的现象也存在。到稳态的现象也存在。值得注意的是求稳态概值得注意的是求稳态概率率P Pn n并不一定求并不一定求t的的极限极限,而只需求而只需求P P

17、n n(t)=0(t)=0 即可。即可。过渡状态 稳定状态 pn t 图3 排队系统状态变化示意图 称为稳态称为稳态(steady state)steady state)解，解，或称统计平衡状态或称统计平衡状态 (Statistical Equilibrium State)Statistical Equilibrium State)的解。的解。1911.5.5 排队论主要知识点排队论主要知识点排队系统的组成与特征排队系统的组成与特征排队系统的模型分类排队系统的模型分类顾客到达间隔时间和服务时间的经验分布与顾客到达间隔时间和服务时间的经验分布与理论分布理论分布稳态概率稳态概率P Pn n的计算的

18、计算标准的标准的M/M/1M/M/1模型模型(M/M/1/FCFS)/FCFS)系统容量有限制的系统容量有限制的模型模型M/M/1/N/FCFS/FCFS顾客源有限模型顾客源有限模型M/M/1/M/M/FCFSFCFS标准的标准的M/M/CM/M/C模型模型M/M/C/FCFS/FCFS 20M/M/C型系统和型系统和C个个M/M/1型系统型系统系统容量有限制的多服务台模型系统容量有限制的多服务台模型(M/M/C/N/)顾客源为有限的顾客源为有限的多服务台模型多服务台模型(M/M/C/M)(M/M/C/M)一般服务时间的（一般服务时间的（M/G/1M/G/1）模型）模型Pollaczek-Kh

19、intchine(P-K)公式公式定长服务时间定长服务时间 M/D/1 M/D/1模型模型爱尔朗服务时间爱尔朗服务时间M/Ek/1模型模型排队系统优化排队系统优化M/M/1 模型中的最优服务率模型中的最优服务率 标准的标准的M/M/1 Model系统容量为系统容量为N的情形的情形M/M/C模型中最优服务台数模型中最优服务台数C212 2 到达间隔时间分布和服务时间到达间隔时间分布和服务时间的分布的分布 要要解解决决排排队队问问题题，首首先先要要确确定定排排队队系系统统的的到到达达间间隔隔时时间间分分布布与与服服务务时时间间分分布布。要要研研究究到到达达间间隔隔时时间间分分布布与与服服务务时时间

20、间分分布布需需要要首首先先根根据据现现有有系系统统原原始始资资料料统统计计出出它它们们的的经经验验分分布布（见见P315319P315319），然然后后与与理理论论分分布布拟拟合合，若若能能对对应应，我我们们就就可以得出上述的分布情况。可以得出上述的分布情况。222.1 2.1 经验分布经验分布 经验分布是对排队系统的某些时间参数根据经验分布是对排队系统的某些时间参数根据经验数据进行的统计分析，并依据统计分析结果经验数据进行的统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数法进行检验，当通

21、过检验时，我们认为时间参数的经验数据服从该假设分布。的经验数据服从该假设分布。分布的拟合检验一般采用分布的拟合检验一般采用2检验。具体参见有检验。具体参见有关的概率统计教材内容。关的概率统计教材内容。23随机变量：数随机变量：数 随着实验的结果的不同而变化随着实验的结果的不同而变化 离散型：离散型：的所有可能只有限或至多可列个的所有可能只有限或至多可列个 连续型：连续型：（）取值于某个区间（）取值于某个区间（a a，b b）分布函数（连续）分布函数（连续）:的概率分布的概率分布(离散):i=1,2,32.2 2.2 概率论复习知识概率论复习知识24 数学期望数学期望:(离散)E()=(连续)E

22、()=方差方差:=条件概率条件概率:密度函数密度函数:(连续),252.3 2.3 理论分布理论分布式中式中为常数为常数(0)0)，称，称X X服从参数为服从参数为的泊松分布。的泊松分布。若在上式中引入时间参数若在上式中引入时间参数t t，即令，即令tt代替代替，则有：，则有：1.泊松分布泊松分布 在概率论中，我们曾学过泊松分布，设随机变在概率论中，我们曾学过泊松分布，设随机变量为量为X，则有：则有：n=0,1,2,（1）t0，n=0,1,2,（2）26 (2)(2)式式所所表表示示的的是是与与时时间间有有关关的的随随机机变变量量的的概概率率，这这已已不不是是简简单单的的概概率率论论的的知知识

23、识了了，而而是是一一个个随随机机过过程，即泊松过程。程，即泊松过程。下下面面我我们们在在一一定定的的假假设设条条件件下下，推推出出顾顾客客的的到到达达过程就是一个泊松过程。过程就是一个泊松过程。若若设设N(t)N(t)表表示示在在时时间间区区间间0,t)0,t)内内到到达达的的顾顾客客数数(t0)(t0)，P Pn n(t(t1 1,t,t2 2)表表示示在在时时间间区区间间tt1 1,t,t2 2)(t)(t2 2tt1 1)内内有有n(0)n(0)个顾客到达的概率。即：个顾客到达的概率。即：（t2t1，n0）27 无无后后效效性性（独独立立性性）：各各区区间间内内的的顾顾客客到到达达数数相

24、相互独立，即互独立，即MarkovMarkov性。性。平稳性：平稳性：即对于足够小的即对于足够小的tt，在时间区间在时间区间tt，t+t+t)t)内内有有1 1个顾客到达的概率为个顾客到达的概率为 当当P Pn n(t(t1 1,t,t2 2)符合于下述三个条件时，我们说顾客到符合于下述三个条件时，我们说顾客到达过程就是泊松过程或者说顾客到达形成普阿松流。达过程就是泊松过程或者说顾客到达形成普阿松流。普阿松流的三个特性：普阿松流的三个特性：设表示单位时间内有 一个顾客到达的概率28 普普 通通 性性：对对 充充 分分 小小 的的 t,t,在在 时时 间间 区区 间间 t,t+tt）内内有有2

25、2个个或或2 2个个以以上上顾顾客客到到达达的的概概率率是是tt一高阶无穷小一高阶无穷小.令令t1 1=0,t=0,t2 2=t,=t,则则P Pn n(t(t1 1,t,t2 2)=P)=Pn n(0,t)=P(0,t)=Pn n(t)(t)也就是在也就是在t,t+tt,t+t内有一个顾客到达的概率与内有一个顾客到达的概率与t t无关无关,而与而与tt成正比。成正比。0 0 是常数，是常数，称为概率强度称为概率强度 即即 由此知，在由此知，在(t，t+t)t)区间内没有顾客到达的概率为区间内没有顾客到达的概率为:区间长度为t时有 n个顾客的概率29 为了求为了求Pn(t)，即即Pn(0,t)

26、，需要研究它在时刻，需要研究它在时刻t到到t+tt时刻的改变量时刻的改变量，也就是要建立，也就是要建立P Pn n(t)(t)的微分方的微分方程。程。对于区间对于区间00，t+t)+t)可以分成可以分成00，t)t)和和tt，t+t)t+t)，其到达总数是，其到达总数是n n，不外有下列三种情况：所，不外有下列三种情况：所以有：以有：30A n pn(t)0 1-t+pn(t)(1-t+(t)(t)B n-1 pn-1(t)1t pn-1(t)t(t)(t)n-2 Pn-2(t)2 C n-3 Pn-3(t)3 0 P0(t)n31 令令t0t0取极限（并注意初始条件）得：取极限（并注意初始条

27、件）得：当当n=0时，没有时，没有B，C两种情况，则：两种情况，则：(4)(4)n0 (3)(3)32 代初始条件代初始条件(t=0)t=0)有有：C C =0=0（3 3）式两端乘）式两端乘 e et t 并移项得：并移项得：(5)（没有顾客到达的概率）由上式得：由上式得：两边积分得：两边积分得：一阶台劳展一阶台劳展开为开为1-1-tt33 将将n=1,2,3代入（代入（6）得：）得：积分得：积分得：(6)(6)(注意利用注意利用(5)式式)34 如此继续递推下去得：如此继续递推下去得：（2 2个顾客到达的概率）个顾客到达的概率）（n n个顾客到达的概率）个顾客到达的概率）即随机变量即随机变

28、量N(t)=n服从泊松分布。它的数学期望服从泊松分布。它的数学期望和方差为：和方差为：（1 1个顾客到达的概率）个顾客到达的概率）35 由高等数学知，若设由高等数学知，若设 即：即：令令k=n-1，则：则：36 即：即：同理方差为：同理方差为：37 其概率密度函数为：其概率密度函数为：t0t0 t0t0 没有顾客到达的概率没有顾客到达的概率为：为：(由（由（5）式而来）式而来)2.2.负指数分布负指数分布 当输入过程是当输入过程是泊泊松流时，我们研究两顾客相继松流时，我们研究两顾客相继到达的时间间隔的概率分布。到达的时间间隔的概率分布。设设T T为时间间隔，分布函数为为时间间隔，分布函数为F

29、FT T（t t），），即：即：F FT T（t t）=PTt=PTt 此概率等价于在此概率等价于在00，t t）区间内至少有区间内至少有1 1个顾客个顾客到达的概率到达的概率.38 由由前前知知，表表示示单单位位时时间间内内顾顾客客平平均均到到达达数数，这这里里1/表示顾客到达的平均间隔时间表示顾客到达的平均间隔时间，两者是吻合的。，两者是吻合的。可可以以证证明明，间间隔隔时时间间T T独独立立且且服服从从负负指指数数分分布布与与顾顾客到达形成泊松流是等价的。客到达形成泊松流是等价的。下面我们再谈一下服务时间的分布：下面我们再谈一下服务时间的分布：对对顾顾客客的的服服务务时时间间，实实际际是

30、是系系统统处处于于忙忙期期时时两两顾顾客客相相继继离离开开系系统统的的时时间间间间隔隔，一一般般地地也也服服从从负负指指数分布，即：数分布，即：即即T服从负指数分布，由概率论知它的期望及方差为：服从负指数分布，由概率论知它的期望及方差为：39其中：其中：表示单位时间内能被服务完成的顾客数表示单位时间内能被服务完成的顾客数，即，即平均服务率。平均服务率。1/1/表示一个顾客的平均服务时间表示一个顾客的平均服务时间。3.3.爱尔朗爱尔朗(Erlang)(Erlang)分布分布 设设v v1 1,v v2 2，,v vk k是是k k个个独独立立的的随随机机变变量量，服服从从相相同同参数参数k k

31、的负指数分布，那么：的负指数分布，那么：，则，则令令 ，则，则称为称为服务强度服务强度。40 串列的串列的k k个服务台，每台服务时间相互独立，服个服务台，每台服务时间相互独立，服从相同的负指数分布（参数从相同的负指数分布（参数k k），），那么一顾客走完那么一顾客走完k k个服务台总共所需要服务时间就服从上述的个服务台总共所需要服务时间就服从上述的k k阶阶ErlangErlang分布。分布。则称则称T服从服从k阶阶爱尔朗分布，其特征值为爱尔朗分布，其特征值为:,的概率密度是的概率密度是(可以证明可以证明)当当k=1k=1时，时，ErlangErlang分布即为负指数分布；分布即为负指数分布

32、；当当k k增加时，增加时，ErlangErlang分布逐渐变为对称的；分布逐渐变为对称的；当当k k 3030时，时，ErlangErlang分布近似于正态分布；分布近似于正态分布；每一个服从每一个服从k k，因此因此E(TE(Ti i)=1/)=1/k k，且，且T Ti i之间相互独立之间相互独立 b bk k(t(t)t t k=1k=1 k=2k=2 1/1/ErlangErlang分布曲线分布曲线 k=3k=341 例例:有有易易碎碎物物品品500500件件,由由甲甲地地运运往往乙乙地地,根根据据以以往往统统计计资资料料,在在运运输输过过程程中中易易碎碎物物品品按按普普阿阿松松流流

33、发发生生破破碎碎,其其概概率率为为0.002,0.002,现现求求:1.:1.破破碎碎3 3件件物物品品的的概概率率;2.;2.破破碎碎少少于于3 3件件的的概概率率和和多多于于3 3件件的的概概率率;3.;3.至至少有一件破损的概率少有一件破损的概率.解解:1.:1.求破碎求破碎3 3件物品的概率件物品的概率:=0.002500=1 则则 P(k=3)=(P(k=3)=(3 3/3/3！)e)e-=(1=(13 3/3/3！)e)e-1-1=0.0613=0.0613 即物品破碎即物品破碎3 3件的概率为件的概率为6.136.13 2.2.破碎物品少于破碎物品少于3 3件的概率件的概率:42

34、 破碎物品少于破碎物品少于3 3件的概率为件的概率为91.9791.97 破碎物品多于破碎物品多于3 3件的概率为件的概率为:3.3.至少有一件破碎的概率为至少有一件破碎的概率为 PkPk 1=1-(11=1-(1k k/k!)e/k!)e-=1-(1=1-(10 0/0!)e/0!)e-1-1=0.632=0.63243 3.3.单服务台负指数分布排队系统单服务台负指数分布排队系统的分析的分析 研究对象为单队、单服务台（服务台数为研究对象为单队、单服务台（服务台数为1 1），），包括：包括：（1 1）标准）标准M/M/1M/M/1模型（模型（M/M/1/M/M/1/）；）；（2 2）系统容量

35、有限制（系统容量有限制（M/M/1/N/M/M/1/N/）（3 3）有限顾客源（有限顾客源（M/M/1/mM/M/1/m）44 以以后后各各节节将将介介绍绍几几个个常常见见的的排排队队模模型型。对对排排队队模模型型，在在给给定定输输入入和和服服务务条条件件下下，主主要要研研究究系系统统的的下下述运行指标：述运行指标：(1)(1)系系统统的的平平均均队队长长Ls(Ls(期期望望值值)和和平平均均队队列列长长LqLq期望值；期望值；(2)(2)系系统统中中顾顾客客平平均均逗逗留留时时间间WsWs与与队队列列中中平平均均等等待时间待时间WqWq；本节只研究本节只研究M/M/1M/M/1模型，下面分三

36、种情况讨论：模型，下面分三种情况讨论：453.1 3.1 标准的标准的M/M/1M/M/1模型模型 1.1.1.1.稳态概率稳态概率稳态概率稳态概率P P P Pn n n n的计算的计算的计算的计算 为分析模型，首先要确定在任意时刻为分析模型，首先要确定在任意时刻t t，状态为状态为n n（系统中有系统中有n n个顾客个顾客）的概率的概率P Pn n(t(t)()(瞬态概率瞬态概率)，它，它决定了系统的运行特征。决定了系统的运行特征。已知顾客到达服从参数为已知顾客到达服从参数为的普阿松过程，服的普阿松过程，服务时间服从参数为务时间服从参数为的负指数分布。现仍然通过研的负指数分布。现仍然通过研

37、究区间究区间 t，t+tt）的变化来求解。在间刻的变化来求解。在间刻t+tt，系系统中有统中有n n个顾客不外乎有下列四种情况（到达或离去个顾客不外乎有下列四种情况（到达或离去2 2个以上的没列入，是高阶无穷小）。个以上的没列入，是高阶无穷小）。1、输入过程：顾客源无限，顾客单个到达，相互独立，服从普阿松分布，平稳；2、排队规则：单队，队长无限制，FCFS。3、服务机构：单服务台，各顾客服务时间相互独立，服从负指数分布。此外：假设到达时间间隔和服务时间是相互独立的。标准的标准的M/M/1M/M/1模型即为模型即为M/M/1/FCFS/FCFS模型模型4647 由于这四种情况是互不相容的，所以由

38、于这四种情况是互不相容的，所以Pn(t+t)t)应应是这四项之和，将所有的高阶无穷小合并，则有：是这四项之和，将所有的高阶无穷小合并，则有：48 令令t0t0，得关于得关于P Pn n(t)(t)的微分差分方程：的微分差分方程：(1)当当n=0时，只有表中的（时，只有表中的（A）、（）、（B）两种情况，两种情况，因为在较小的因为在较小的tt内不可能发生（内不可能发生（D D）（）（到达后即离到达后即离去），若发生可将去），若发生可将tt取小即可。取小即可。49 (2)对于方程(1)、(2)求解很麻烦，即便求得解也是瞬态解，无法应用。为此,我们只要求得稳态解即可。稳态时，Pn(t)与时间无关，可

39、以写成Pn，它对时间的导数为0，所以由(1)、(2)两式得：在时刻t系统处于无顾客状态，而在t+t时刻内又没有顾客来到系统（必然没有离去事件）在时刻t系统有一个顾客接受服务，在t+t时刻内服务完毕离去，且在t+t时刻内又没有顾客来到系统(3)(3)(4)(4)50 上式即为关于上式即为关于Pn的差分方程。由此可得该排队的差分方程。由此可得该排队系统的状态转移图：系统的状态转移图：由（由（4）得：）得：其中其中服务强度服务强度 将其代入（将其代入（3）式并令）式并令n=1,2,(也可从状态转移也可从状态转移图中看出状态平衡方程图中看出状态平衡方程)得：得：这种系统状态(n)随时间变化的过程就是生

40、灭过程（Birth and Death Process），它可以描述细菌的生灭过程。51 n=1 n=2 52 以此类推以此类推，当，当n=n时，时，(5)(5)(否则排队无限远，无法服务完否则排队无限远，无法服务完)以及概率性质知：以及概率性质知：(数列的极限为 )(6)(6)当=1时，似乎好象来一个顾客服务一个顾客，但这是在均衡条件下和所有的顾客的服务时间都相等时，才会出现不存在排队现象的这种理想的现象。在随机的情况下，这是不可能的。53 上上式式就就是是系系统统稳稳态态概概率率，以以它它为为基基础础可可以以 算算出出系系统的运行指标。统的运行指标。2.系统的运行指标计算系统的运行指标计算

41、 (1)系统中的平均顾客数（队长期望值系统中的平均顾客数（队长期望值Ls）(01)54 即:(7)(7)(8)(8)(3)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间Ws 顾顾客客在在系系统统中中的的逗逗留留时时间间是是随随机机变变量量，可可以以证证明，它服从参数为明，它服从参数为-的负指数分布，分布函数的负指数分布，分布函数(2)队列中等待的平均顾客数队列中等待的平均顾客数Lq（队列长期望值）队列长期望值）55 和密度函数为：和密度函数为：（w00）(4)(4)顾客在队列中的等待时间的期望值顾客在队列中的等待时间的期望值W Wq q 顾客在队列中的等待时间应为顾客在队列中的等待时间应

42、为W Ws s减去平均服务减去平均服务时间。时间。56 四个指标的关系为四个指标的关系为(Little Little 公式公式)：3.系统的忙期与闲期系统的忙期与闲期 系统处于空闲状态的概率：系统处于空闲状态的概率：系统处于繁忙状态的概率：系统处于繁忙状态的概率：下标s表示系统 下标q表示队列573.2 3.2 系统容量有限制的系统容量有限制的系统容量有限制的系统容量有限制的模型模型模型模型 M/M/1/NM/M/1/N/FCFS/FCFS/FCFS/FCFS 当当系系统统容容量量最最大大为为N N时时，排排队队系系统统中中多多于于N N个个的的顾顾客客将将被被拒拒绝绝。当当N=1N=1时时，

43、即即为为瞬瞬时时制制；NN时时，即即为容量无限制的情况。为容量无限制的情况。58 现在研究系统中有现在研究系统中有n n个顾客的概率个顾客的概率P Pn n(t(t).).对于对于P P0 0(t)(t)，前面的（前面的（2 2）式仍然成立）式仍然成立(2)(2)对于对于(1)(1)式，当式，当n=1,2,N-1n=1,2,N-1时，也仍能成立。时，也仍能成立。(1)(1)(n=1,2,N-1)(n=1,2,N-1)但当但当n=Nn=N时，有下面两种情况：时，有下面两种情况：59 (8)(8)其状态转移图为其状态转移图为:60 在稳态情况下有：在稳态情况下有：(9)(9)解（解（9）式得：）式

44、得：而等比数列而等比数列61(1,(1,nN)(10)nN)(10)注：当注：当=1=1时，试讨论其概率时，试讨论其概率P Pn n下面计算其运行指标：下面计算其运行指标：(1)平均平均队长队长Ls：(1)试证=1时,Ls=N/262（2 2）队列长（期望值）队列长（期望值）有效到达率有效到达率e的引入：的引入：Little公公式式可可应应用用的的条条件件是是：其其平平均均到到达达率率是是在在系系统统有有空空时时的的平平均均到到达达率率。当当系系统统满满员员时时，就就不不能再应用了。要用就应该应用有效到达率。能再应用了。要用就应该应用有效到达率。因因为为系系统统容容量量有有限限，当当满满员员时

45、时，顾顾客客将将被被拒拒绝绝，因因此此实实际际的的顾顾客客到到达达率率为为0，与与不不一一样样，为为了了求求其他指标，需要求得有效到达率为其他指标，需要求得有效到达率为e：可以验证：可以验证：63 此种情况此种情况的公式与的公式与前类似，前类似，只有只有Ls不不同，同，e与与 不同。不同。求求e必须必须先求得先求得P0或或Pn才行。才行。（3 3）顾客逗留时间（期望值）顾客逗留时间（期望值）（4 4）顾客等待时间（期望值）顾客等待时间（期望值）Little公式64例例2某某单单人人理理发发馆馆共共有有六六把把椅椅子子接接待待顾顾客客排排队队，无无座座时时将将离离去，顾客平均到达率为去，顾客平均

46、到达率为3人人/h，理发时间平均为，理发时间平均为15分钟，求：分钟，求：(1)求某一顾客到达就能理发的概率求某一顾客到达就能理发的概率;(2)求需要等待的顾客数的期望值求需要等待的顾客数的期望值;(3)求有效到达率求有效到达率;(4)求一顾客在系统中的逗留时间和排队时间平均值求一顾客在系统中的逗留时间和排队时间平均值;(5)在可能到来的顾客中，有百分之几不等待就离开？在可能到来的顾客中，有百分之几不等待就离开？解：解：N=6+1=7，=3=3，=4=4(1)(1)(2)(2)65(3)(3)(4)(4)(5)(5)P0=0.27780P1=0.20836P2=0.15627P3=0.1172

47、0 =0.9629=96.29%P4=0.08790 故拒绝的概率为3.71%P5=0.06593P6=0.04944663.3 顾客源有限（顾客源有限（M M）的模型）的模型 M/M/1/m/m 本本节节以以机机器器修修理理模模型型为为例例来来说说明明，设设有有m台台机机器器(总总体体)，故故障障待待修修表表示示机机器器到到达达，修修理理工工是是服服务务员员。机机器器修修好好后后有有可可能能再再坏坏，形形成成循循环环。虽虽然然系系统统没没有有容容量量，但但系系统统中中的的顾顾客客也也不不会会超超过过m，故故又又可可写写成成：M/M/1/m/mm/m67 设每个顾客的平均到达率是相同的设每个顾

48、客的平均到达率是相同的(这里这里的的含义是单台机器在单位时间里发生故障的概率或平均含义是单台机器在单位时间里发生故障的概率或平均次数次数)，这是无限源的情形，对于有限源应按每个顾，这是无限源的情形，对于有限源应按每个顾客单独考虑，求出其有效到达率客单独考虑，求出其有效到达率e。设系统内顾客数为设系统内顾客数为Ls，则系统外的顾客为则系统外的顾客为m-Ls.这样这样e是随系统内顾客数而变化的。其状态转是随系统内顾客数而变化的。其状态转移图为：移图为：68 由状态转移图可得状态转移方程：由状态转移图可得状态转移方程：1nm-1 0 0状态状态 n n状态状态 m m状态状态 用递推方法解此差分方程

49、，并注意条件，用递推方法解此差分方程，并注意条件，可以得到如下公式：可以得到如下公式：1 0=m i i P,(1nm)69 各项运行指标为：各项运行指标为：例例3 某车间有某车间有5台机器，每台机器的连续运转时间服从负指数分台机器，每台机器的连续运转时间服从负指数分布。平均连续运转时间布。平均连续运转时间15分钟，有一个修理工，修理时间服从负分钟，有一个修理工，修理时间服从负指数分布，平均每次指数分布，平均每次12分钟。求：分钟。求：(1)修理工空闲时间修理工空闲时间(2)五台机器都出现故障的概率五台机器都出现故障的概率70(3)出故障的平均台数出故障的平均台数(4)等待修理的平均台数等待修理的平均台数(5)故障平均停工时间故障平均停工时间(6)平均等待修理时间平均等待修理时间(7)评价这些结果评价这些结果 解解:(1)m=5,=1/15,=1/12,=4/5=0.8 m=5,=1/15,=1/12,=4/5=0.871(2)(2)(3)(3)台台(5)(5)分钟分钟(4)(4)台台 分钟分钟(6)(6)(7)(7)机器等待过长，忙期长，应增加维修工人或提高效率。机器等待过长，忙期长，应增加维修工人或提高效率。72