运筹学-第八章-排队论课件.ppt

1、1第八章第八章 排队论排队论(Queuing Theory)(Queuing Theory)排队论（排队论（queuing),也称随机服务系统理论，是也称随机服务系统理论，是运筹学的一个主要分支。运筹学的一个主要分支。1909年，丹麦哥本哈根电子公司电话工程师年，丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文的开创性论文“概率论和电话通讯理论概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话，标志此理论的诞生。排队论的发展最早是与电话，通信中的问题相联系的，并到现在是排队论的传统通信中的问题相联系的，并到现在是排队论的传统的应用领域。近年来在计算机通讯网络系统的应

2、用领域。近年来在计算机通讯网络系统、交通、交通运输、医疗卫生系统、库存管理、作战指挥等各领运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。域中均得到应用。2排队论排队论 8-1 基基 本本 概概 念念 8-2 单服务台指数分布的排队系统的分析单服务台指数分布的排队系统的分析 8-3 多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析3 排队是我们在日常生活和生产中经排队是我们在日常生活和生产中经常遇到的现象。常遇到的现象。例如，上、下班搭乘公共汽车；例如，上、下班搭乘公共汽车；顾客到商店购买物品；顾客到商店购买物品；顾客到银行取钱；顾客到银行取钱；旅客到售票处购买车票

3、；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等学生去食堂就餐等就常常出现排队和等待现象。待现象。前前 言言4 排队的不一定是人，也可以是物：排队的不一定是人，也可以是物：例如，通讯卫星与地面若干待传递的例如，通讯卫星与地面若干待传递的信息；信息；生产线上原料、半成品等待加工；生产线上原料、半成品等待加工；因故障停止运转的机器等待修理；码因故障停止运转的机器等待修理；码头的船只等待装卸货物；头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘要降落的飞机因跑道不空而在空中盘旋等等。旋等等。前前 言言5 上述各种问题虽互不相同，但却都有上述各种问题虽互不相同，但却都有要求得到某种服务

4、的人或物和提供服务要求得到某种服务的人或物和提供服务的人或机构。的人或机构。排队论里把要求服务的对象统称为排队论里把要求服务的对象统称为“顾客顾客”,提供服务的人或机构称为提供服务的人或机构称为“服务台服务台”或或“服务员服务员”。前前 言言6 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图8-1至图8-5。图图1 1 单服务台排队系统单服务台排队系统前前 言言7图图2 2 单队列单队列S S个服务台并联的排队系统个服务台并联的排队系统图图3 S3 S个队列个队列S S个服务台的并联排队系

5、统个服务台的并联排队系统前前 言言8图图4 4 单队单队多个服务台的串联排队系统多个服务台的串联排队系统 图图5 5 多队多队多服务台混联网络系统多服务台混联网络系统前前 言言9图图6 6 随机服务系统随机服务系统前前 言言一般的排队系统，都可由下一般的排队系统，都可由下面图加以描述。面图加以描述。10 面对拥挤现象，人们总是希望尽量设法减面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支出就但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费。越大，甚至会出现空闲浪费。如果服务设施太少，顾客排队

6、等待的时间就如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。会很长，这样对顾客会带来不良影响。前前 言言11 顾客排队时间的长短与服务设施规模的大顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛小，就构成了设计随机服务系统中的一对矛盾。盾。如何做到既保证一定的服务质量指标，又如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论这就是随机服务系统理论排队论所要排队论所要研究解决的问题。研究解决的

7、问题。前前 言言12排队结构服务机构顾客源顾客到达排队规则服务规则离去图1 排 队系统示意图 排队系统一般有三个基本组成部分：排队系统一般有三个基本组成部分：1.1.输输入过程；入过程；2.2.排队规则；排队规则；3.3.服务机构。服务机构。13 输入即为顾客的到达，可有下列情况：输入即为顾客的到达，可有下列情况：1）顾客源可能是有限的，也可能是无限的。顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单个到达。顾客是成批到达或是单个到达。3）顾客到达间隔时间可能是随机的或确定的。顾客到达间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立或关联的。所谓独顾客到达可能是相互独立或关

8、联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。立就是以前顾客的到达对以后顾客的到达无影响。5）输入过程可以是平稳的（输入过程可以是平稳的（stationarystationary）或说）或说是对时间齐次的（是对时间齐次的（Homogeneous in timeHomogeneous in time），也可以），也可以是非平稳的。输入过程平稳的指顾客相继到达的间是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。平稳的则是与时间相关，非平稳的处理比较困难。14这是

9、指服务台从队列中选取顾客进行服务的顺序。这是指服务台从队列中选取顾客进行服务的顺序。可以分为可以分为损失制、等待制、混合制损失制、等待制、混合制3 3大类。大类。(1)(1)损失制。损失制。这是指如果顾客到达排队系统时，这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。拔号，这种服务规则即为损失制。1

10、5 (2)(2)等待制等待制。指当顾客来到系统时，所有服务台。指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有等待制中，服务台在选择顾客进行服务时，常有如下四种规则：如下四种规则：先到先服务（先到先服务（FCFS FCFS）。按顾客到达的先后顺。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。序对顾客进行服务，这是最普遍的情形。后到先服务（后到先服务（LCFSLCFS）。仓库中迭放的钢材，。仓库中迭放的钢材，后迭放上去

11、的都先被领走，就属于这种情况。后迭放上去的都先被领走，就属于这种情况。16 随机服务（随机服务（RAND）。即当服务台空。即当服务台空闲时，不按照排队序列而随意指定某个顾客闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就去接受服务，如电话交换台接通呼叫电话就是一例。是一例。优先权服务（优先权服务（PR）。如老人、儿童先。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，要处理计算机立即中断其他数据的处理等，均属于此种服务规则。均属于此种服务规则。17 (3)(3)混合制混合制这是等待制与损

12、失制相结合的一这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：列无限长下去。具体说来，大致有三种：队长有限。队长有限。当排队等待服务顾客人数超过当排队等待服务顾客人数超过规定数量时，后来顾客就自动离去，另求服务。规定数量时，后来顾客就自动离去，另求服务。如水库的库容、旅馆的床位等都是有限的如水库的库容、旅馆的床位等都是有限的。18 等待时间有限等待时间有限。即顾客在系统中的。即顾客在系统中的等待时间不超过某一给定的长度等待时间不超过某一给定的长度T T，当等待，当等待时间超过时间超过T T时，顾

13、客自动离去，不再回来。时，顾客自动离去，不再回来。如易损坏的电子元器件的库存问题，如易损坏的电子元器件的库存问题，超过一定存储时间被自动认为失效。超过一定存储时间被自动认为失效。又如顾客到饭馆就餐，等了一定时间后又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。不愿再等而自动离去另找饭店用餐。19 逗留时间逗留时间(等待时间与服务时间之和等待时间与服务时间之和)有限。有限。例如用高射炮射击敌机，当敌机飞越高射例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为炮射击有效区域的时间为t t时，若在这个时时，若在这个时间内未被击落，也就不可能再被击落了。间内未被击落，也就不可

14、能再被击落了。不难注意到，损失制和等待制可看成是不难注意到，损失制和等待制可看成是混合制的特殊情形，如记混合制的特殊情形，如记c c为系统中服务台为系统中服务台的个数，则当的个数，则当K=cK=c 时，混合制即成为损失制；时，混合制即成为损失制；当当K=K=时，混合制即成为等待制。时，混合制即成为等待制。20 1 1）服务机构可以是单服务员和多服务员服务，）服务机构可以是单服务员和多服务员服务，这种服务形式与队列规则联合后形成了多种不同这种服务形式与队列规则联合后形成了多种不同队列，不同形式的排队服务机构。如前图队列，不同形式的排队服务机构。如前图8-18-1到到8-8-5 5：2)2)服务方

15、式分为单个顾客服务和成批顾客服务。服务方式分为单个顾客服务和成批顾客服务。3)3)服务时间分为确定型和随机型。服务时间分为确定型和随机型。4)4)服务时间的分布在这里我们假定是平稳的。服务时间的分布在这里我们假定是平稳的。21 上述特征中最主要的、影响最大的是：上述特征中最主要的、影响最大的是：顾客相继到达的间隔时间分布顾客相继到达的间隔时间分布服务时间的分布服务时间的分布服务台数服务台数 D.G.KendallD.G.Kendall，19531953提出了分类法，称为提出了分类法，称为KendallKendall记号记号(适用于并列服务台适用于并列服务台)即：即：X/Y/Z/A/B/CX/Y

16、/Z/A/B/C22 式中：式中：X顾客相继到达间隔时间分布。顾客相继到达间隔时间分布。M负指数分布负指数分布Markov，D确定型分布确定型分布Deterministic，EkK阶爱尔朗分布阶爱尔朗分布Erlang，GI 一般相互独立随机分布一般相互独立随机分布(General Independent)，G 一般随机分布。一般随机分布。Y填写服务时间分布（与上同）填写服务时间分布（与上同）Z填写并列的服务台数填写并列的服务台数 A排队系统的最大容量排队系统的最大容量 B顾客源数量顾客源数量 C排队规则排队规则 如如 即为顾客到达为泊松过程，即为顾客到达为泊松过程，服务时间为负指数分布，单台，

17、无限容量，无限源，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。先到先服务的排队系统模型。23 一个实际问题作为排队问题求解时，首先研一个实际问题作为排队问题求解时，首先研究它属于哪个模型，其中只有顾客到达的间隔时究它属于哪个模型，其中只有顾客到达的间隔时间分布和服务时间的分布需要实测的数据来确定，间分布和服务时间的分布需要实测的数据来确定，其他的因素都是在问题提出时给定的。其他的因素都是在问题提出时给定的。求解一般排队系统问题的目的主要是通过研究求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定排队系统运行的效率指标，估计服务质量，确

18、定系统的合理结构和系统参数的合理值，以便实现系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。对现有系统合理改进和对新建系统的最优设计等。24 排队问题的一般步骤：排队问题的一般步骤：1 1.确定或拟合确定或拟合排队系统顾客到达的时间排队系统顾客到达的时间间隔分布和服务时间分布间隔分布和服务时间分布(可实测可实测)。2 2.研究分析排队系统理论分布的概率特研究分析排队系统理论分布的概率特征。征。3 3.研究研究系统状态的概率。系统状态是指系统状态的概率。系统状态是指系统中顾客数。状态概率用系统中顾客数。状态概率用P Pn n(t)(t)表示表示,即在即在t

19、t时刻系统中有时刻系统中有n n个顾客的概率，也称瞬态个顾客的概率，也称瞬态概率。概率。25 求解状态概率求解状态概率P Pn n(t)(t)方法是建立含方法是建立含P Pn n(t)(t)的微分差的微分差分方程，通过求解微分差分方程得到系统瞬态解，由分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此常常使用它的极限很难使用。因此常常使用它的极限(如果存在的话如果存在的话)：nttnp)(plim 稳态的物理意义图，系稳态的物理意义图，系统的稳态一般很快都能统的稳态一般很快都能达到，但实际中达

20、不到达到，但实际中达不到稳态的现象也存在。要稳态的现象也存在。要注意的是求稳态概率注意的是求稳态概率P Pn n并不一定求并不一定求t的极限的极限,只需求只需求P Pn n(t)=0(t)=0。过渡状态 稳定状态 pn t 图3 排队系统状态变化示意图 称为稳态称为稳态(steady state)steady state)解，解，或称统计平衡状态或称统计平衡状态 (Statistical Equilibrium State)Statistical Equilibrium State)的解的解。26 4 4.根据排队系统对应的理论模型根据排队系统对应的理论模型求用以判断系求用以判断系统运行优劣的

21、基本数量指标的概率分布或特征数。统运行优劣的基本数量指标的概率分布或特征数。数量指标主要包括数量指标主要包括:(1)(1)队长（队长（L Ls s）:系统中的顾客数。系统中的顾客数。队列长（队列长（L Lg g）:系统中排队等待服务的顾客数。系统中排队等待服务的顾客数。系统中顾客数系统中顾客数L Ls s=系统中排队等待服务的顾客数系统中排队等待服务的顾客数L Lg g+正被正被服务的顾客数服务的顾客数c c(2)(2)逗留时间逗留时间(Ws):(Ws):指一个顾客在系统中的停留时间。指一个顾客在系统中的停留时间。等待时间等待时间(Wg):(Wg):一个顾客在系统中排队等待的时间。一个顾客在系

22、统中排队等待的时间。(3)(3)忙期：指从顾客到达空闲服务机构起到服务机构再次为忙期：指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）数都是衡量服务机构效率的指标，忙期关系到工作强度）5.5.排队系统指标优化排队系统指标优化 问题问题1 1 系统中顾客数系统中顾客数=平均队长（平均队长（L Ls s）+1+1？27 一个排队系统的最主要特征参数是一个排队系统的最主要特征参数是顾客顾客的到达间隔时间分布与服务时间分布的到达间隔时间分布与服务时间分布。

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

24、检验时，我们认为时间参数的经验数据服从该假设分布。经验数据服从该假设分布。分布的拟合检验一般采用分布的拟合检验一般采用2检验。由数理统检验。由数理统计的知识我们知：若样本量计的知识我们知：若样本量n充分大充分大(n50)，则则当假设当假设H0为真时，统计量总是近似地服从自由度为真时，统计量总是近似地服从自由度为为k-r-1的的2分布，其中分布，其中k为分组数，为分组数，r为检验分布为检验分布中被估计的参数个数。中被估计的参数个数。29随机变量随机变量 数数 随着实验的结果的不同而变化随着实验的结果的不同而变化 离散型：离散型：的所有可能只有限或至多可列个的所有可能只有限或至多可列个 连续型：连

25、续型：（）取值于某个区间（）取值于某个区间（a a，b b）分布函数分布函数(连续连续):):xpxF aFbFbap 的概率分布的概率分布(离散):iixpxp i=1,2,311iixp30 数学期望数学期望:(离散)E()=1iiipxdxxxf (连续)E()=方差方差:2EED EE22=BApBpABp 条件概率条件概率:密度函数密度函数:(连续)dttfxFx 0 xf 1dttf,31tnnenttP !)(式中式中为常数为常数(0)0)，称，称X X服从参数为服从参数为的泊松分布，的泊松分布，若在上式中引入时间参数若在上式中引入时间参数t t，即令，即令tt代替代替，则有：，

26、则有：在概率论中，我们曾学过泊松分布，设随机变在概率论中，我们曾学过泊松分布，设随机变量为量为X，则有：，则有：!nenxPn n=0,1,2,（1）与时间有关的随机变量的概率与时间有关的随机变量的概率，是一个，是一个随机过程随机过程，即即泊松过程泊松过程。t0，n=0,1,2,（2）32)()(,1221ntNtNPttPn（t2t1，n0）若设若设N(t)N(t)表示在时间区间表示在时间区间0,t)0,t)内到达的顾客数内到达的顾客数(t0),P(t0),Pn n(t(t1 1,t,t2 2)表示在时间区间表示在时间区间tt1 1,t,t2 2)(t)(t2 2tt1 1)内有内有n(0)

27、n(0)个顾客到达的概率。即：个顾客到达的概率。即：在一定的假设条件下在一定的假设条件下 顾客的到达过程就是顾客的到达过程就是一个泊松过程。一个泊松过程。当当P Pn n(t(t1 1,t,t2 2)符合下述三个条件时，顾客到达过程符合下述三个条件时，顾客到达过程就是泊松过程就是泊松过程(顾客到达形成普阿松流顾客到达形成普阿松流)。33 无后效性：无后效性：各区间的到达相互独立各区间的到达相互独立,即即MarkovMarkov性。性。.t0 t1 t2 tn-1 tn|)(|)(11112211)()(,.,)(,)(nnnnxtxnxtxxtxxtxnntxPntxP 也就是说过程在也就是说

28、过程在t+tt+t所处的状态与所处的状态与t t以前所处的状以前所处的状态无态无关。关。平稳性：平稳性：即对于足够小的即对于足够小的tt，有：，有：)()(tttttP ，1普阿松流具有如下特性：普阿松流具有如下特性：在在t,t+tt,t+t内有一个顾客到达的概率与内有一个顾客到达的概率与t t无关无关,而与而与tt成正比。成正比。34 普通性：普通性：对充分小的对充分小的t,t,在时间区间（在时间区间（t,t+tt）内有内有2 2个或个或2 2个以上顾客到达的概率是一高阶无穷小个以上顾客到达的概率是一高阶无穷小.由此知，在由此知，在(t，t+t)t)区间内没有顾客到达的概率为：区间内没有顾客

29、到达的概率为：)(1),(0tottttP 令令t1 1=0,t=0,t2 2=t,=t,则则P(tP(t1 1,t,t2 2)=P)=Pn n(0,t)=P(0,t)=Pn n(t)(t)0 0 是常数，它是常数，它表示单位时间到达的顾客数，称表示单位时间到达的顾客数，称为概率强度。为概率强度。2)(),(nntotttP 即即 P P0 0+P+P1 1+P+P22=1=135 为了求为了求Pn(t),即即Pn(0,t)，需要研究它在（，需要研究它在（t，t+tt）上的改变量上的改变量,建立建立P Pn n(t)(t)的微分方程。对于区间的微分方程。对于区间0,0,t+t)+t)可以分成可

30、以分成00，t)t)和和tt，t+t),t+t),其到达总数是其到达总数是n n，不外有，不外有下列三种情况：下列三种情况：36 在在00，t+tt+t内到达内到达n n个顾客应是上面三种互不相个顾客应是上面三种互不相容的情况之一，所以有：容的情况之一，所以有：37 令令t0t0取极限（并注意初始条件）得：取极限（并注意初始条件）得：)()()(1tPtPdttdPnnn0)0(nP(3)(3)当当n=0时，没有时，没有B，C两种情况，则：两种情况，则：)()(00tPdttdP1)0(0P(4)(4)()()1)()(1tOttPttPttPnnn)()()()()(1tOttPttPtPt

31、tPnnnnttOtPtPttPttPnnnn)()()()()(1 凑微分凑微分 区间长度（区间长度（0 0，0 0）有有n n个顾客到达个顾客到达(0,t)(0,t)有有n-1,n-2n-1,n-2个个顾客到达顾客到达38CCt01n C C =0=0ttP )(n0（3 3）式两端乘）式两端乘e e t t并移项得：并移项得：te)t(P 0(5)(5)（没有顾客到达的概率）（没有顾客到达的概率）dtPtdP )()(000CttP )(n0 两边积分得：两边积分得：代入初始条件代入初始条件(t=0)t=0)有有：P P0 0(0)=1(0)=1)t(P)t(Pdt)t(dPnnn1 0

32、)0(nP)()(00tPdttdP39 将将n=1,2,3代入（代入（6）得：）得：tntnetPetPdtd )()(1 11101)()(dtetPetPtnttn (6)(6)110011)()(dtetPetPttt (注意利用注意利用(5)式式)tdteettt 1011tntntne)t(Pe)t(Pedt)t(dP 1tntnnte)t(Pe)t(Pdt)t(dPe 1 凑成凑成P Pn n(t)e(t)e t t两两项乘积的微分项乘积的微分 两边积分两边积分te)t(P 040 如此继续递推下去得：如此继续递推下去得：tettP !2)()(22 （2 2个顾客到达的概率）个

33、顾客到达的概率）（n n个顾客到达的概率）个顾客到达的概率）tnnenttP !)()(即随机变量即随机变量N(t)=n服从泊松分布。它的数学期望服从泊松分布。它的数学期望和方差为：和方差为：ttetP )(1 （1 1个顾客到达的概率）个顾客到达的概率）11011102111)()(dteetdtetPetPtttttt 2221t 41 级数级数.!nx.!xxenx 212 tkke!k)t(0!)()()(11ntnetnPtNEnntnn )!1()(11 nttennt 令令k=n-1，则：，则：!)()(0kttetNEkkt tetetNEtt )(422121)()!1()(

34、)!2()(tntntttennnt tttttettett 22)()1()1(ttar )(N(V 即即：21221)(!)()()(tntnnettPnnntnn 22E(N(t)EN(t)(tNVar 同理方差为：同理方差为：211121)()!1()()!1()()1()()!1()(tntntntetntnnennntnnt 顾客到达过程是一个顾客到达过程是一个泊松过程泊松过程(泊松流泊松流)。43 其概率密度函数为：其概率密度函数为：tTTedtdF)t(f t0t0 当输入过程是泊松流时，我们研究两顾客相继到当输入过程是泊松流时，我们研究两顾客相继到达的时间间隔的概率分布。达的

35、时间间隔的概率分布。设设T T为时间间隔，分布函数为为时间间隔，分布函数为F FT T（t t），则：），则：F FT T（t t）=PTt=PTt 此概率等价于在此概率等价于在00，t t）区间内至少有）区间内至少有1 1个顾客到个顾客到达的概率。达的概率。tTetPtF 1)(1)(0 t0t0tetP)(0 没有顾客到达的概率没有顾客到达的概率为：为：(由（由（5）式而来）式而来)间隔：间隔：间隔：间隔：间隔间隔 对分布函对分布函数微分数微分44 表示单位时间内顾客平均到达数。表示单位时间内顾客平均到达数。1/表示顾客到达的平均间隔时间。表示顾客到达的平均间隔时间。可以证明，间隔时间可以

36、证明，间隔时间T T独立且服从负指数分布与独立且服从负指数分布与顾客到达形成泊松流是等价的。顾客到达形成泊松流是等价的。对顾客的服务时间对顾客的服务时间：系统处于忙期时系统处于忙期时两顾客相继离两顾客相继离开系统的时间间隔开系统的时间间隔，一般地也服从负指数分布，设：，一般地也服从负指数分布，设：即即T服从负指数分布，它的期望及方差为：服从负指数分布，它的期望及方差为：1TE21 TVar 接受服务，然后离开接受服务，然后离开服务时间的分布：服务时间的分布：45其中：其中：表示单位时间内能被服务的顾客数，即平均表示单位时间内能被服务的顾客数，即平均 服务率。服务率。1/1/表示一个顾客的平均服

37、务时间。表示一个顾客的平均服务时间。设设v v1 1,v,v2 2，,v,vk k是是k k个独立的随机变量，服从相同个独立的随机变量，服从相同参数参数 k k 的负指数分布，那么：的负指数分布，那么：tetF 1)(tetf )(，则，则 令令 ，则，则称为服务强度称为服务强度。kT 2146 串列串列k k个服务台个服务台，每台服务时间相互独立，服从，每台服务时间相互独立，服从相同负指数分布（参数相同负指数分布（参数k k），那么一顾客走完），那么一顾客走完k k个服个服务台总共所需要服务时间服从上述务台总共所需要服务时间服从上述k k阶阶ErlangErlang分布。分布。011 te)

38、!k()kt(k)t(ftkkk 则称则称T服从服从k阶阶爱尔朗分布。其特征值为：爱尔朗分布。其特征值为：1TE21 kTVar,其概率密度是其概率密度是1/k1/k表示一个顾客一个服务台的平均服务时间。表示一个顾客一个服务台的平均服务时间。47 例例:有易碎物品有易碎物品500500件件,由甲地运往乙地由甲地运往乙地,根据以根据以往统计资料往统计资料,在运输过程中易碎物品按普阿松流发在运输过程中易碎物品按普阿松流发生破碎生破碎,其概率为其概率为0.002,0.002,现求现求:1.:1.破碎破碎3 3件物品的概件物品的概率率;2.;2.破碎少于破碎少于3 3件的概率和多于件的概率和多于3 3

39、件的概率件的概率;3.;3.至至少有一件破损的概率少有一件破损的概率.解解:=0.002500=1 1 1破碎破碎3 3件物品的概率为件物品的概率为: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件的概率件的概率:48 破碎物品少于破碎物品少于3 3件的概率为件的概率为91.9791.97 破碎物品多于破碎物品多于3 3件的概率为件的概率为:02.098.01!1330 kkekp 3.3.至少有一件破碎的概

40、率为至少有一件破碎的概率为 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.632 9197.021112120 eeknp49 对排队模型，在给定输入和服务条件下，主要对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标：研究系统的下述运行指标：(1)(1)系统的系统的平均队长平均队长LsLs(期望值期望值)和和平均队列长平均队列长LqLq(期望值期望值)；(2)(2)系统中系统中顾客平均逗留时间顾客平均逗留时间WsWs与队列中与队列中平均等平均等待时间待时间WqWq；本节只研究本节只研究M/M/

41、1M/M/1模型，下面分三种情况讨论：模型，下面分三种情况讨论：8.2 M/M/1 8.2 M/M/1 无限源系统无限源系统50 系统中有系统中有n n个顾客个顾客M/M/1:/FCFS/FCFS模型模型 在任意时刻在任意时刻t t，状态为，状态为n n的概率的概率P Pn n(t)(t)（瞬态概率），（瞬态概率），它决定了系统的运行特征。它决定了系统的运行特征。已知顾客到达服从参数为已知顾客到达服从参数为的泊松过程，服务时的泊松过程，服务时间服从参数为间服从参数为的负指数分布。现仍然通过研究区间的负指数分布。现仍然通过研究区间 t，t+tt）的变化来求解。在时刻）的变化来求解。在时刻t+tt

42、，系统中有，系统中有n n个顾客不外乎有下列四种情况（个顾客不外乎有下列四种情况（t，t+tt）内到达）内到达或离开或离开2 2个以上个以上没列入）。没列入）。？5152区区间间(t t,t+t t)情情况况 时时刻刻t t的的顾顾客客 到到达达 离离去去 时时刻刻t+t t的的顾顾客客 (t t,t+t t)的的概概率率 0 0,t+t t 的的概概率率 A n n 1-t+O(t)1-t+O(t)Pn(1-t+O(t)（1-t+O(t)）B n+1 n 1-t+O(t)t+O(t)Pn+1(1-t+O(t)（t+O(t)）C n-1 n t+O(t)1-t+O(t)Pn-1(t+O(t)（

43、1-t+O(t)）D n n t+O(t)t+O(t)Pn(t+O(t)（t+O(t)）由于这四种情况是互不相容的，所以由于这四种情况是互不相容的，所以Pn(t+t)t)应应是这四项之和，则有：是这四项之和，则有：tttPtttPtttPttPnnnn)1)()()1)(1)()(1)()1()(1tOtttPn 所有的高阶无所有的高阶无穷小和并穷小和并53t)t(P)t(P)t(O)t(Ott)(t(Pnnn 11)t(O)t(O)t(Pt)t(P)t(O)t(Pnnn 111)t(Ot)t(Pt)t(P)tt)(t(Pnnn 111t)t(O)t(P)()t(P)t(Pt)t(P)tt(P

44、nnnnn 11 令令t0t0，得关于，得关于P Pn n(t)(t)的微分差分方程：的微分差分方程：)()()()()(11tPtPtPdttdPnnnn(1)当当n=0时，只有表中的（时，只有表中的（A）、（）、（B）两种情况，）两种情况，因为在较小的因为在较小的tt内不可能发生（内不可能发生（D D）（到达后即离）（到达后即离去），若发生可将去），若发生可将tt取小即可。取小即可。54)t()t)(t(P)t)(t(P)tt(P 11100)t(P)t(Pdt)t(dP100 (2)(2)这种系统状态这种系统状态(n)随时间变化的过程就是生灭过随时间变化的过程就是生灭过程（程（Birth

45、 and Death Process）。）。方程方程(1)、(2)解是瞬态解解是瞬态解,无法应用。无法应用。它 对 时它 对 时间的导数为间的导数为0，所以由，所以由(1)、(2)两式得：两式得：稳态时，稳态时，Pn(t)与时间无关与时间无关,可以写成可以写成Pn,011 nnnP)(PP010 PP(3)(3)(4)(4)55 由此可得该排队系统的状态转移图：由此可得该排队系统的状态转移图：由（由（4）得：）得：001PPP 其中其中服务强度服务强度 将其代入（将其代入（3）式并令）式并令n=1,2,(也可从状态转移也可从状态转移图中看出状态平衡方程图中看出状态平衡方程)得：得：011 nn

46、nP)(PP010 PP(3)(3)(4)(4)关于关于Pn的差的差分方程分方程 n-1n-1 n n n+1n+1 2 2 0 0 1 1 状态转移图状态转移图560120 P)(PP n=1n=10020 P)(PP 0202021PP)(P)(P n=2n=20231 P)(PP00230 P)(PP 0303022231PP)(P)(P 57 以此类推以此类推，当，当n=n时，时，00)(PPPnnn (5)(5)1 10 nnP 及概率性质知：及概率性质知：111000 PPnn(数列的极限为数列的极限为 )11 10Pnn)(P 1(6)(6)否则排队无限远否则排队无限远 系统系统

47、稳态稳态概率概率系统的运行指标系统的运行指标58 (1)系统中的队长系统中的队长Ls（平均队长）（平均队长）nnnnsnPnL 001.)(n.)()()(n 11312132.nn.nn 1433223322 132.n(01)1 Ls 即即:(7)(7)期望期望59(2)队列中等待的平均顾客数队列中等待的平均顾客数Lq nnnnqnPnL 111)1()1(nnnn)(n 1111 12sL(8)(8)(3)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间Ws 顾客在系统中的逗留时间是随机变量，可以证顾客在系统中的逗留时间是随机变量，可以证明，它服从参数为明，它服从参数为-的负指数分布

48、，分布函数的负指数分布，分布函数 11nn60 和密度函数为：和密度函数为：w)(e)w(F 1w)(e)()w(f （w00）)WsLs(1wEWs (4)(4)顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间W Wq q 111WsWq)WqLq(等待时等待时间间 顾客在队列中的平均逗留时间应为顾客在队列中的平均逗留时间应为W Ws s减去平均服减去平均服务时间。务时间。考虑考虑L LS S与与W WS S的关的关系系61 LsLsLLqs 12WsLs WqLq 四个指标的关系为四个指标的关系为(Little Little 公式公式)：系统处于空闲状态的概率：系统处于空闲状态的概率：

49、10P 系统处于繁忙状态的概率：系统处于繁忙状态的概率：010P)N(P服服务务强强度度62 在繁忙状态下，队列中的平均顾客数在繁忙状态下，队列中的平均顾客数L Lb b：Ls)N(PLLqb 0 顾客平均等待时间顾客平均等待时间:Ws)N(PWWqb 10 忙期的平均长度忙期的平均长度:1B 1IB(由由 来来)一个忙期平均服务顾客数为：一个忙期平均服务顾客数为：111 L Lb bP P(N0)(N0)=L=Lq q63例题 某机关接待室，接待人员每天工作10小时。来访人员的到来服从泊松过程，每天平均有90人到来，接待时间服从指数分布，平均速度为10人/小时，（平均每人6分钟）（1）试求排

50、队等待接待的平均人数。（2）等待接待的多于2人的概率,如果使等待接待的人平均为2人，接待速度应提高多少？64 答案答案0120.9 9(1)8.1109(2)(2)1()0.7299929=12.3LqP nPPPLq 解得65 当系统容量最大为当系统容量最大为N N时，排队多于时，排队多于N N个的顾客将被个的顾客将被拒绝。当拒绝。当N=1N=1时，即为瞬时制，时，即为瞬时制，NN时，即为容量时，即为容量无限制的情况。无限制的情况。排队系统 服务台顾客 N 4 3 2 1被拒绝66 现在研究系统中有现在研究系统中有n n个顾客的概率个顾客的概率P Pn n(t)(t)。)()()(100tP