随机服务系统理论：排队论.ppt

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

1、随机服务系统理论：随机服务系统理论：排队论排队论排队论主要知识点排队论主要知识点n n排队论的基本概念排队论的基本概念排队论的基本概念排队论的基本概念l l排队系统的组成与特征排队系统的组成与特征排队系统的组成与特征排队系统的组成与特征l l排队系统的模型分类排队系统的模型分类排队系统的模型分类排队系统的模型分类l l顾客到达间隔时间和服务时间的经验分布与理论分布顾客到达间隔时间和服务时间的经验分布与理论分布顾客到达间隔时间和服务时间的经验分布与理论分布顾客到达间隔时间和服务时间的经验分布与理论分布l l稳态概率稳态概率稳态概率稳态概率PnPn的计算的计算的计算的计算n nM/M/1M/M/1

2、模型模型模型模型l l标准的标准的标准的标准的M/M/1M/M/1模型模型模型模型(M/M/1(M/M/1:/FCFS):/FCFS)l l系统容量有限制的模型系统容量有限制的模型系统容量有限制的模型系统容量有限制的模型M/M/1:N/FCFSM/M/1:N/FCFSl l顾客源有限模型顾客源有限模型顾客源有限模型顾客源有限模型M/M/1/M/FCFSM/M/1/M/FCFS2 2n nM/M/C模型模型l l标准的标准的标准的标准的M/M/CM/M/C模型模型模型模型M/M/C:/FCFSM/M/C:/FCFS l lM/M/CM/M/C型系统和型系统和型系统和型系统和C C个个个个M/M/

3、1M/M/1型系统型系统型系统型系统l l系统容量有限制的多服务台模型系统容量有限制的多服务台模型系统容量有限制的多服务台模型系统容量有限制的多服务台模型(M/M/C/N/)(M/M/C/N/)l l顾客源为有限的多服务台模型顾客源为有限的多服务台模型顾客源为有限的多服务台模型顾客源为有限的多服务台模型(M/M/C/M)(M/M/C/M)n n一般服务时间的（一般服务时间的（M/G/1）模型）模型l lPollaczek-Khintchine(P-K)Pollaczek-Khintchine(P-K)公式公式公式公式l l定长服务时间定长服务时间定长服务时间定长服务时间 M/D/1 M/D/1

4、模型模型模型模型l l爱尔朗服务时间爱尔朗服务时间爱尔朗服务时间爱尔朗服务时间M/Ek/1M/Ek/1模型模型模型模型n n排队系统优化排队系统优化l lM/M/1 M/M/1 模型中的最优服务率模型中的最优服务率模型中的最优服务率模型中的最优服务率u un n标准的标准的标准的标准的M/M/1ModelM/M/1Modeln n系统容量为系统容量为系统容量为系统容量为N N的情形的情形的情形的情形l lM/M/CM/M/C模型中最优服务台数模型中最优服务台数模型中最优服务台数模型中最优服务台数C C3 3 排队系统一般有三个基本组成部分：排队系统一般有三个基本组成部分：排队系统一般有三个基本

5、组成部分：排队系统一般有三个基本组成部分：1.1.1.1.输入过程；输入过程；输入过程；输入过程；2.2.2.2.排队规则；排队规则；排队规则；排队规则；3.3.3.3.服务机构。服务机构。服务机构。服务机构。1 1 排队论的基本概念排队论的基本概念1.1 1.1 1.1 1.1 排队系统的组成与特征排队系统的组成与特征排队系统的组成与特征排队系统的组成与特征4 4输入即为顾客的到达，可有下列输入即为顾客的到达，可有下列输入即为顾客的到达，可有下列输入即为顾客的到达，可有下列3 3种情况：种情况：种情况：种情况：1 1）顾客来源。顾客总体）顾客来源。顾客总体）顾客来源。顾客总体）顾客来源。顾客

6、总体(称为顾客源称为顾客源称为顾客源称为顾客源)的组成可能是有的组成可能是有的组成可能是有的组成可能是有限的，也可能是无限的。如，上游河水流入水库可以限的，也可能是无限的。如，上游河水流入水库可以限的，也可能是无限的。如，上游河水流入水库可以限的，也可能是无限的。如，上游河水流入水库可以认为总体是无限的，工厂内停机待修的机器显然是有认为总体是无限的，工厂内停机待修的机器显然是有认为总体是无限的，工厂内停机待修的机器显然是有认为总体是无限的，工厂内停机待修的机器显然是有限的总体。限的总体。限的总体。限的总体。2 2）顾客到达方式。顾客到来的方式可能是一个一个）顾客到达方式。顾客到来的方式可能是一

7、个一个）顾客到达方式。顾客到来的方式可能是一个一个）顾客到达方式。顾客到来的方式可能是一个一个的，也可能是成批的。如，到餐厅就餐就有单个到来的，也可能是成批的。如，到餐厅就餐就有单个到来的，也可能是成批的。如，到餐厅就餐就有单个到来的，也可能是成批的。如，到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客。的顾客和受邀请来参加宴会的成批顾客。的顾客和受邀请来参加宴会的成批顾客。的顾客和受邀请来参加宴会的成批顾客。1.1.1.1.输入过程输入过程输入过程输入过程5 53 3）顾顾顾顾客客客客流流流流的的的的概概概概率率率率分分分分布布布布。顾顾顾顾客客客客随随随随机机机机一一一一个个个个(

8、批批批批)个个个个(批批批批)来来来来到到到到排排排排队队队队系系系系统统统统，顾顾顾顾客客客客流流流流的的的的概概概概率率率率分分分分布布布布用用用用来来来来描描描描述述述述相相相相继继继继到到到到达达达达的的的的顾顾顾顾客客客客之之之之间间间间的的的的间间间间隔隔隔隔时时时时间间间间分分分分布布布布是是是是确确确确定定定定的的的的还还还还是是是是随随随随机机机机的的的的，分分分分布布布布参参参参数数数数是是是是什什什什么么么么，到到到到达达达达的的的的间间间间隔隔隔隔时时时时间间间间是是是是否否否否独独独独立立立立，分分分分布布布布是是是是随随随随时时时时间间间间变化的还是平稳的。变化的还

9、是平稳的。变化的还是平稳的。变化的还是平稳的。当输入过程是泊松流时，两顾客相继到达的时间当输入过程是泊松流时，两顾客相继到达的时间当输入过程是泊松流时，两顾客相继到达的时间当输入过程是泊松流时，两顾客相继到达的时间间隔间隔间隔间隔T T T T独立且服从负指数分布。（等价）独立且服从负指数分布。（等价）独立且服从负指数分布。（等价）独立且服从负指数分布。（等价）6 6 1 1）损失制。顾客到达时，如果所有的服务台都被）损失制。顾客到达时，如果所有的服务台都被）损失制。顾客到达时，如果所有的服务台都被）损失制。顾客到达时，如果所有的服务台都被占用，且服务机构又不允许顾客等待，顾客只能离占用，且服

10、务机构又不允许顾客等待，顾客只能离占用，且服务机构又不允许顾客等待，顾客只能离占用，且服务机构又不允许顾客等待，顾客只能离去，这种服务规则就是损失制。去，这种服务规则就是损失制。去，这种服务规则就是损失制。去，这种服务规则就是损失制。2 2）等待制。当顾客到达时，如果所有服务台都被顾）等待制。当顾客到达时，如果所有服务台都被顾）等待制。当顾客到达时，如果所有服务台都被顾）等待制。当顾客到达时，如果所有服务台都被顾客占用而无空闲，这时该顾客自动加入队列排队等客占用而无空闲，这时该顾客自动加入队列排队等客占用而无空闲，这时该顾客自动加入队列排队等客占用而无空闲，这时该顾客自动加入队列排队等待服务，

11、服务完才离开。待服务，服务完才离开。待服务，服务完才离开。待服务，服务完才离开。（1 1）先到先服务）先到先服务）先到先服务）先到先服务 FCFS FCFS（2 2）后到先服务）后到先服务）后到先服务）后到先服务 LCFS LCFS（3 3）随机服务）随机服务）随机服务）随机服务RAND RAND （4 4）有优先权服务）有优先权服务）有优先权服务）有优先权服务 PR PR。2 2 2 2.排队规则排队规则排队规则排队规则7 7 1 1）服服服服务务务务机机机机构构构构可可可可以以以以是是是是单单单单服服服服务务务务员员员员和和和和多多多多服服服服务务务务员员员员服服服服务务务务，这这这这种种

12、种种服服服服务务务务形形形形式式式式与与与与队队队队列列列列规规规规则则则则联联联联合合合合后后后后形形形形成成成成了了了了多多多多种种种种不不不不同同同同队队队队列列列列，不不不不同形式的排队服务机构，如：同形式的排队服务机构，如：同形式的排队服务机构，如：同形式的排队服务机构，如：3 3 3 3.服务机构服务机构服务机构服务机构8 8上述特征中最主要的、影响最大的是：上述特征中最主要的、影响最大的是：n n顾客相继到达的间隔时间分布顾客相继到达的间隔时间分布n n服务时间的分布服务时间的分布n n服务台数服务台数 2)2)服务方式分为单个顾客服务和成批顾客服务。服务方式分为单个顾客服务和成

13、批顾客服务。服务方式分为单个顾客服务和成批顾客服务。服务方式分为单个顾客服务和成批顾客服务。3)3)服务时间分为确定型和随机型。服务时间分为确定型和随机型。服务时间分为确定型和随机型。服务时间分为确定型和随机型。4)4)服务时间的分布在这里我们假定是平稳的。服务时间的分布在这里我们假定是平稳的。服务时间的分布在这里我们假定是平稳的。服务时间的分布在这里我们假定是平稳的。1111.2.2.2.2 排队系统的模型分类排队系统的模型分类排队系统的模型分类排队系统的模型分类9 9式中：式中：式中：式中：XX填写顾客相继到达间隔时间分布。填写顾客相继到达间隔时间分布。填写顾客相继到达间隔时间分布。填写顾

14、客相继到达间隔时间分布。MM负指数分布负指数分布负指数分布负指数分布MarkovMarkov，D D确定型分布确定型分布确定型分布确定型分布DeterministicDeterministic，EkK EkK阶爱尔朗分布阶爱尔朗分布阶爱尔朗分布阶爱尔朗分布ErlangErlang，G G 一般随机分布。一般随机分布。一般随机分布。一般随机分布。YY填写服务时间分布（与上同）填写服务时间分布（与上同）填写服务时间分布（与上同）填写服务时间分布（与上同）ZZ填写并列的服务台数填写并列的服务台数填写并列的服务台数填写并列的服务台数AA排队系统的最大容量排队系统的最大容量排队系统的最大容量排队系统的最

15、大容量BB顾客源数量顾客源数量顾客源数量顾客源数量 CC排队规则排队规则排队规则排队规则 如如如如 M/M/1M/M/1M/M/1M/M/1:/FCFS:/FCFS:/FCFS:/FCFS即即即即为为为为顾顾顾顾客客客客到到到到达达达达为为为为泊泊泊泊松松松松过过过过程程程程，服服服服务务务务时时时时间间间间为为为为负负负负指指指指数数数数分分分分布布布布，单单单单台台台台，无无无无限限限限容容容容量量量量，无无无无限限限限源源源源，先先先先到到到到先先先先服服服服务务务务的的的的排排排排队队队队系系系系统统统统模型。模型。模型。模型。D.G.KendallD.G.Kendall，195319

16、53提提提提出出出出了了了了分分分分类类类类法法法法，称称称称为为为为KendallKendall记记记记号号号号(适适适适用用用用于于于于并列服务台并列服务台并列服务台并列服务台)即：即：即：即：X/Y/Z:A/B/CX/Y/Z:A/B/C1010系统指标系统指标系统指标系统指标(1)(1)队长队长队长队长:指在系统中的顾客数，它的期望值记指在系统中的顾客数，它的期望值记指在系统中的顾客数，它的期望值记指在系统中的顾客数，它的期望值记LsLs；(2)(2)排队长排队长排队长排队长:指在系统中排队等待服务的顾客数，它的指在系统中排队等待服务的顾客数，它的指在系统中排队等待服务的顾客数，它的指在

17、系统中排队等待服务的顾客数，它的期望值记作期望值记作期望值记作期望值记作LqLq。系 统中 顾客 数在队列中等待服务的顾客数正被服务的顾客数+=一般情形，一般情形，一般情形，一般情形，Ls(Ls(或或或或Lq)Lq)越大，说明服务效率越低。越大，说明服务效率越低。越大，说明服务效率越低。越大，说明服务效率越低。1111(3)(3)逗逗逗逗留留留留时时时时间间间间，指指指指一一一一个个个个顾顾顾顾客客客客在在在在系系系系统统统统中中中中的的的的停停停停留留留留时时时时间间间间，它它它它的的的的期望值记作期望值记作期望值记作期望值记作WsWs；(4)(4)等等等等待待待待时时时时间间间间，指指指指

18、一一一一个个个个顾顾顾顾客客客客在在在在系系系系统统统统中中中中排排排排队队队队等等等等待待待待的的的的时时时时间间间间，它的期望值记作它的期望值记作它的期望值记作它的期望值记作WqWq；等待时间 服务时间+逗留时间=12121.1.排排排排队队队队系系系系统统统统的的的的统统统统计计计计推推推推断断断断:即即即即通通通通过过过过对对对对排排排排队队队队系系系系统统统统主主主主要要要要参参参参数数数数的的的的统统统统计计计计推推推推断断断断和和和和对对对对排排排排队队队队系系系系统统统统的的的的结结结结构构构构分分分分析析析析，判判判判断断断断一一一一个个个个给给给给定定定定的的的的排排排排队

19、队队队系系系系统统统统符符符符合合合合于于于于哪哪哪哪种种种种模模模模型型型型，以以以以便便便便根根根根据据据据排排排排队队队队理理理理论论论论进行研究。进行研究。进行研究。进行研究。2.2.系系系系统统统统性性性性态态态态问问问问题题题题:即即即即研研研研究究究究各各各各种种种种排排排排队队队队系系系系统统统统的的的的概概概概率率率率规规规规律律律律性性性性，主主主主要要要要研研研研究究究究队队队队长长长长分分分分布布布布、等等等等待待待待时时时时间间间间分分分分布布布布和和和和忙忙忙忙期期期期分分分分布布布布等统计指标等统计指标等统计指标等统计指标,包括了瞬态和稳态两种情形。包括了瞬态和稳

20、态两种情形。包括了瞬态和稳态两种情形。包括了瞬态和稳态两种情形。3.3.最最最最优优优优化化化化问问问问题题题题：即即即即包包包包括括括括最最最最优优优优设设设设计计计计(静静静静态态态态优优优优化化化化)，最最最最优优优优运营（动态优化）。运营（动态优化）。运营（动态优化）。运营（动态优化）。1 1 1 1.3.3.3.3 排队论研究的基本问题排队论研究的基本问题排队论研究的基本问题排队论研究的基本问题13131.4 1.4 1.4 1.4 排队问题求解排队问题求解排队问题求解排队问题求解(主要指性态问题主要指性态问题主要指性态问题主要指性态问题)求求求求解解解解一一一一般般般般排排排排队队

21、队队系系系系统统统统问问问问题题题题的的的的目目目目的的的的主主主主要要要要是是是是通通通通过过过过研研研研究究究究排排排排队队队队系系系系统统统统运运运运行行行行的的的的效效效效率率率率指指指指标标标标，估估估估计计计计服服服服务务务务质质质质量量量量，确确确确定定定定系系系系统统统统的的的的合合合合理理理理结结结结构构构构和和和和系系系系统统统统参参参参数数数数的的的的合合合合理理理理值值值值，以以以以便便便便实实实实现现现现对对对对现现现现有有有有系系系系统统统统合合合合理改进和对新建系统的最优设计等。理改进和对新建系统的最优设计等。理改进和对新建系统的最优设计等。理改进和对新建系统的最

22、优设计等。排队问题的一般步骤：排队问题的一般步骤：排队问题的一般步骤：排队问题的一般步骤：1 1.确确确确定定定定或或或或拟拟拟拟合合合合排排排排队队队队系系系系统统统统顾顾顾顾客客客客到到到到达达达达的的的的时时时时间间间间间间间间隔隔隔隔分分分分布布布布和和和和服务时间分布服务时间分布服务时间分布服务时间分布(可实测可实测可实测可实测)。2.2.研研研研究究究究系系系系统统统统状状状状态态态态的的的的概概概概率率率率。系系系系统统统统状状状状态态态态是是是是指指指指系系系系统统统统中中中中顾顾顾顾客客客客数数数数。状状状状态态态态概概概概率率率率用用用用Pn(t)Pn(t)表表表表示示示示

23、,即即即即在在在在t t时时时时刻刻刻刻系系系系统统统统中中中中有有有有n n个个个个顾顾顾顾客的概率，也称瞬态概率。客的概率，也称瞬态概率。客的概率，也称瞬态概率。客的概率，也称瞬态概率。1414 求求求求解解解解状状状状态态态态概概概概率率率率Pn(t)Pn(t)方方方方法法法法是是是是建建建建立立立立含含含含Pn(t)Pn(t)的的的的微微微微分分分分差差差差分分分分方方方方程程程程，通通通通过过过过求求求求解解解解微微微微分分分分差差差差分分分分方方方方程程程程得得得得到到到到系系系系统统统统瞬瞬瞬瞬态态态态解解解解，由由由由于于于于瞬瞬瞬瞬态态态态解解解解一一一一般般般般求求求求出出

24、出出确确确确定定定定值值值值比比比比较较较较困困困困难难难难，即即即即便便便便求求求求得得得得一一一一般般般般也也也也很很很很难难难难使使使使用用用用。因此我们常常使用它的极限因此我们常常使用它的极限因此我们常常使用它的极限因此我们常常使用它的极限(如果存在的话如果存在的话如果存在的话如果存在的话)：稳稳稳稳态态态态的的的的物物物物理理理理意意意意义义义义见见见见右右右右图图图图，系系系系统统统统的的的的稳稳稳稳态态态态一一一一般般般般很很很很快快快快都都都都能能能能达达达达到到到到，但但但但实实实实际际际际中中中中达达达达不不不不到到到到稳稳稳稳态态态态的的的的现现现现象象象象也也也也存存存

25、存在在在在。值值值值得得得得注注注注意意意意的的的的是是是是求求求求稳稳稳稳态态态态概概概概率率率率PnPn并并并并不不不不一一一一定定定定求求求求tt的的的的极极极极限限限限,而而而而只只只只需求需求需求需求P P n n(t(t)=0)=0 即可。即可。即可。即可。过渡状态 稳定状态 pn t 图3 排队系统状态变化示意图 称称称称为为为为稳稳稳稳态态态态(steady steady state)state)解解解解，或或或或称称称称统统统统计计计计平平平平衡衡衡衡状状状状态态态态 (Statistical Equilibrium State)Statistical Equilibrium

26、 State)的解。的解。的解。的解。15152 2 到达间隔时间分布和服务时间的分布到达间隔时间分布和服务时间的分布 一一一一个个个个排排排排队队队队系系系系统统统统的的的的最最最最主主主主要要要要特特特特征征征征参参参参数数数数是是是是顾顾顾顾客客客客的的的的到到到到达达达达间间间间隔隔隔隔时时时时间间间间分分分分布布布布与与与与服服服服务务务务时时时时间间间间分分分分布布布布。要要要要研研研研究究究究到到到到达达达达间间间间隔隔隔隔时时时时间间间间分分分分布布布布与与与与服服服服务务务务时时时时间间间间分分分分布布布布需需需需要要要要首首首首先先先先根根根根据据据据现现现现存存存存系系系

27、系统统统统原原原原始始始始资资资资料料料料统统统统计计计计出出出出它它它它们们们们的的的的经经经经验验验验分分分分布布布布，然然然然后后后后与与与与理理理理论论论论分分分分布布布布拟拟拟拟合合合合，若若若若能能能能照照照照应应应应，我们就可以得出上述的分布情况。我们就可以得出上述的分布情况。我们就可以得出上述的分布情况。我们就可以得出上述的分布情况。16162.1 2.1 2.1 2.1 经验分布经验分布经验分布经验分布 经经验验分分布布是是对对排排队队系系统统的的某某些些时时间间参参数数根根据据经经验验数数据据进进行行统统计计分分析析，并并依依据据统统计计分分析析结结果果假假设设其其统统计计

28、样样本本的的总总体体分分布布，选选择择合合适适的的检检验验方方法法进进行行检检验验，当当通通过过检检验验时时，我我们们认认为为时时间参数的经验数据服从该假设分布。间参数的经验数据服从该假设分布。分分布布的的拟拟合合检检验验一一般般采采用用 2检检验验。由由数数理理统统计计的的知知识识我我们们知知：若若样样本本量量n充充分分大大(n50)，则则当当假假设设H0为为真真时时，统统计计量量总总是是近近似似地地服服从从自自由由度度为为k-r-1的的 2分分布布，其其中中k为为分分组组数数，r为为检验分布中被估计的参数个数。检验分布中被估计的参数个数。17172.2 2.2 2.2 2.2 理论分布理论

29、分布理论分布理论分布 式中式中为常数为常数(0)0)，称，称X X服从参数为服从参数为的泊松分的泊松分布，若在上式中引入时间参数布，若在上式中引入时间参数t t，即令，即令tt代替代替，则，则有：有：1 1.泊松分布泊松分布泊松分布泊松分布 在在在在概概概概率率率率论论论论中中中中，我我我我们们们们曾曾曾曾学学学学过过过过泊泊泊泊松松松松分分分分布布布布，设设设设随随随随机机机机变变变变量量量量为为为为X X，则有：，则有：，则有：，则有：n=0,1,2,（1）与与时时间间有有关关的的随随机机变变量量的的概概率率，是是一一个个随随机机过过程程，即，即泊松过程泊松过程。t0，n=0,1,2,（2

30、）1818（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)n(0)个顾客到达的概率。即：个顾客到达的概率。即：在在一一定定的的假假设设条条件件下下 顾顾客客的的到到达达过过程程就就是是一个泊松过程。一个泊松过程。当当P Pn n(t(t1 1,t,t2 2)符合下述三个条件时，顾客到达过程符合下述三个条件时，顾客到达过程就是泊松过程就是泊松过程(顾客到达形成泊松流顾客到达形

31、成泊松流)。1919 无后效性：无后效性：各区间的到达相互独立各区间的到达相互独立,即即MarkovMarkov性。性。也就是说过程在也就是说过程在t+tt+t所处的状态与所处的状态与t t以前所处的状态以前所处的状态无无关。关。平稳性：平稳性：即对于足够小的即对于足够小的tt，有：有：泊松流具有如下特性：泊松流具有如下特性：在在t,t+tt,t+t内有一个顾客到达的概率与内有一个顾客到达的概率与t t无关无关,而与而与tt成正比。成正比。0 0 是常数，它是常数，它表示单位时间到达的顾客数，称为概率强度。表示单位时间到达的顾客数，称为概率强度。2020 普普通通性性：对对充充分分小小的的t,

32、t,在在时时间间区区间间（t,t+tt）内有内有2 2个或个或2 2个以上顾客到达的概率是一高阶无穷小个以上顾客到达的概率是一高阶无穷小.由此知，在由此知，在(t，t+t)t)区间内没有顾客到达的概率为：区间内没有顾客到达的概率为：令令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)即即 P P0 0+P+P1 1+P+P22=1=1 在在上述假设下，上述假设下，t t时刻系统中有时刻系统中有n n个顾客的概率个顾客的概率p pn(tn(t)：2121 根据排队系统的根据排队系统的状态转移图状态转移图

33、：整理后可得：整理后可得：n-1n-1 n n n+1n+1 2 2 0 0 1 1 2 2 n+1n+1 0 0 1 1 2 2 n-2n-2 n-1n-1 n n 1 1 3 3 n-1n-1 n n n+1n+1 n+2n+2 稳态时，稳态时，它它对对时时间的导数为间的导数为0，所以由，所以由(12.5)、(12.6)两式得：两式得：Pn(t)与时间无关与时间无关,可以写成可以写成Pn,(12.7)(12.7)(12.8)(12.8)2222 表示单位时间内顾客平均到达数。表示单位时间内顾客平均到达数。1/表示顾客到达的平均间隔时间。表示顾客到达的平均间隔时间。2.2.2.2.负指数分布

34、负指数分布负指数分布负指数分布 可以证明当输入过程是泊松流时，两顾客相继到达可以证明当输入过程是泊松流时，两顾客相继到达可以证明当输入过程是泊松流时，两顾客相继到达可以证明当输入过程是泊松流时，两顾客相继到达的时间间隔的时间间隔的时间间隔的时间间隔T T T T独立且服从负指数分布。（等价）独立且服从负指数分布。（等价）独立且服从负指数分布。（等价）独立且服从负指数分布。（等价）（n n个顾客到达的概率）个顾客到达的概率）（4 4）2323 对对排排队队模模型型，在在给给定定输输入入和和服服务务条条件件下下，主主要要研究系统的下述运行指标：研究系统的下述运行指标：(1)(1)系系统统的的平平均

35、均队队长长LsLs(期期望望值值)和和平平均均队队列列长长LqLq(期望值期望值)；(2)(2)系系统统中中顾顾客客平平均均逗逗留留时时间间WsWs与与队队列列中中平平均均等等待时间待时间WqWq；本节只研究本节只研究M/M/1M/M/1模型，下面分三种情况讨论：模型，下面分三种情况讨论：3.M/M/13.M/M/13.M/M/13.M/M/1模型模型模型模型24243.1 3.1 3.1 3.1 标准的标准的标准的标准的M/M/1M/M/1M/M/1M/M/1模型模型模型模型 系统中有系统中有n n个顾客个顾客M/M/1:/FCFS/FCFS模型模型 1.1.稳态概率稳态概率P Pn n的计

36、算的计算 在任意时刻在任意时刻t t，状态为，状态为n n的概率的概率P Pn n(t)(t)（瞬态概率），（瞬态概率），它决定了系统的运行特征。它决定了系统的运行特征。已知顾客到达服从参数为已知顾客到达服从参数为的泊松过程，服务时的泊松过程，服务时间服从参数为间服从参数为的负指数分布。现仍然通过研究区间的负指数分布。现仍然通过研究区间 t，t+tt）的变化来求解。在时刻）的变化来求解。在时刻t+tt，系统中有，系统中有n n个个顾客不外乎有下列四种情况（顾客不外乎有下列四种情况（t，t+tt）内到达或）内到达或离开离开2 2个以上个以上没列入）。没列入）。2525 由此可得该排队系统的由此可

37、得该排队系统的状态转移图状态转移图：由（由（4）得：）得：其中其中服务强度服务强度 将其代入（将其代入（3）式并令）式并令n=1,2,(也可从状态转移也可从状态转移图中看出状态平衡方程图中看出状态平衡方程)得：得：关于关于Pn的差的差分方程分方程 n-1n-1 n n n+1n+1 2 2 0 0 1 1 稳态时，稳态时，它它对对时时间的导数为间的导数为0，所以由，所以由(1)、(2)两式得：两式得：Pn(t)与时间无关与时间无关,可以写成可以写成Pn,(3)(3)(4)(4)2626 n=1n=1 n=2n=2 2727 以此类推以此类推，当，当n=n时，时，(5)(5)以及概率性质知：以及

38、概率性质知：(数列的极限为数列的极限为 )(6)(6)否则排队无限远否则排队无限远 系统系统稳态稳态概率概率系统的运行指标系统的运行指标28282.系统的运行指标计算系统的运行指标计算 (1)系统中的队长系统中的队长Ls（平均队长）（平均队长）(01)即即:(7)(7)期望期望2929(2)队列中等待的平均顾客数队列中等待的平均顾客数Lq(8)(8)3030(Little Little 公式公式)：顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间Ws 顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间Wq 3131 (4)(4)顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间W Wq

39、 q 利用公式（利用公式（12.2612.26）可求出）可求出W Ws s (3)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间Ws 利用公式（利用公式（12.2712.27）可求出）可求出W Wq q3232 3.系统的忙期与闲期系统的忙期与闲期 系统处于空闲状态的概率：系统处于空闲状态的概率：系统处于繁忙状态的概率：系统处于繁忙状态的概率：服务强度服务强度3333例：例：例：例：某医院手术室根据病人来诊和完成手术的时某医院手术室根据病人来诊和完成手术的时某医院手术室根据病人来诊和完成手术的时某医院手术室根据病人来诊和完成手术的时间记录，任意抽查间记录，任意抽查间记录，任意抽查间记录，

40、任意抽查100100个工作小时，每小时来就个工作小时，每小时来就个工作小时，每小时来就个工作小时，每小时来就诊的病人数诊的病人数诊的病人数诊的病人数n n的出现次数如表的出现次数如表的出现次数如表的出现次数如表9-49-4。又任意抽查了。又任意抽查了。又任意抽查了。又任意抽查了100100个完成手术的病历，所用时间个完成手术的病历，所用时间个完成手术的病历，所用时间个完成手术的病历，所用时间v(v(小时小时小时小时)出现的出现的出现的出现的次数如表次数如表次数如表次数如表9-59-5。计算手术室的各项指标。计算手术室的各项指标。计算手术室的各项指标。计算手术室的各项指标。3434到达的病人到达

41、的病人到达的病人到达的病人数数数数n n n n出出出出现现现现次数次数次数次数f f f fn n n n0 0 0 0101010101 1 1 1282828282 2 2 2292929293 3 3 3161616164 4 4 4101010105 5 5 56 6 6 66 6 6 6以上以上以上以上1 1 1 1合合合合计计计计100100100100为为为为病人完成手病人完成手病人完成手病人完成手术时间术时间术时间术时间v(v(v(v(小小小小时时时时)出出出出现现现现次次次次数数数数f f f fv v v v0.00.00.00.00.20.20.20.238383838

42、0.20.20.20.20.40.40.40.4252525250.40.40.40.40.60.60.60.6171717170.60.60.60.60.80.80.80.89 9 9 90.80.80.80.81.01.01.01.06 6 6 61.01.01.01.01.21.21.21.25 5 5 51.21.21.21.2以上以上以上以上0 0 0 0合合合合计计计计100100100100 表9-4 表9-535351.1.参数的确定参数的确定算出每小时病人平均到达率算出每小时病人平均到达率 2.1(2.1(人人/小时小时)每次手术平均时间每次手术平均时间 0.4(0.4(小时

43、小时/人人)每小时完成手术人数每小时完成手术人数(平均服务率平均服务率)2.5(2.5(人人/小时小时)2.2.取取2.12.1，2.52.5，可以通过统计检验的方法，可以通过统计检验的方法(例如例如2 2检检验法验法)，认为病人到达数服从参数为，认为病人到达数服从参数为2.12.1的普阿松分布，手的普阿松分布，手术时间服从参数为术时间服从参数为2.52.5的负指数分布。的负指数分布。3.3.它说明服务机构它说明服务机构(手术室手术室)有有8484的时间是繁忙的时间是繁忙(被利用被利用)，有，有1616的时间是空闲的。的时间是空闲的。36364.4.依次算出各指标：依次算出各指标：在病房中病人

44、数在病房中病人数(期望值期望值)排队等待病人数排队等待病人数(期望值期望值)病人在病房中逗留时间病人在病房中逗留时间(期望值期望值)病人排队等待时间病人排队等待时间(期望值期望值)37373.2 3.2 3.2 3.2 系统容量有限制的模型系统容量有限制的模型系统容量有限制的模型系统容量有限制的模型 M/M/1 M/M/1 M/M/1 M/M/1：N/FCFSN/FCFSN/FCFSN/FCFS 当当当当系系系系统统统统容容容容量量量量最最最最大大大大为为为为N N N N时时时时，排排排排队队队队多多多多于于于于N N N N个个个个的的的的顾顾顾顾客客客客将将将将被被被被拒拒拒拒绝绝绝绝。

45、当当当当N=1N=1N=1N=1时时时时，即即即即为为为为损损损损失失失失制制制制，NNNN时时时时，即即即即为为为为容容容容量量量量无限制的情况。无限制的情况。无限制的情况。无限制的情况。3838 现在研究系统中有现在研究系统中有现在研究系统中有现在研究系统中有n n n n个顾客的概率个顾客的概率个顾客的概率个顾客的概率P P P Pn n n n(t(t(t(t)。(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时，有下面两种情况：时，有下面两种情况

46、：对于对于P P0 0(t)(t)，前面的（前面的（2 2）式仍然成立。）式仍然成立。3939 (8)(8)其状态转移图为其状态转移图为:4040 在稳态情况下有：在稳态情况下有：(9)(9)解（解（9）式得：）式得：而等比数列而等比数列4141(1,(1,nN)(10)nN)(10)(1)平均平均队长队长Ls：(1)其运行指标：其运行指标：4242 (2)有效到达率有效到达率e 系系统统容容量量有有限限，当当满满员员时时，顾顾客客将将被被拒拒绝绝，实实际际的顾客到达率与的顾客到达率与不一样，不一样，还可验证：还可验证：此种情况的公式与此种情况的公式与前类似前类似,只有只有Ls不同不同,e与与

47、 不同。求不同。求e必须先必须先求得求得P0或或PN才行。才行。有效到达率为有效到达率为e。可以证明：可以证明：LsLs4343例例2某某单单人人理理发发馆馆共共有有六六把把椅椅子子接接待待顾顾客客排排队队，无无座座时时将将离离去去，顾顾客客平平均均到到达达率率为为3人人/h，理理发发时时间间平平均为均为15分钟，求：分钟，求：(1)求某一顾客到达就能理发的概率求某一顾客到达就能理发的概率;(2)求需要等待的顾客数的期望值求需要等待的顾客数的期望值;(3)求有效到达率求有效到达率;(4)求求一一顾顾客客在在系系统统中中的的逗逗留留时时间间和和排排队队时时间间平平均值均值;(5)在在可可能能到到

48、来来的的顾顾客客中中，有有百百分分之之几几不不等等待待就就离开？离开？解：解：N=?N=?N=6+1=7，=3=3，=4=44444(1)求某一顾客到达就能理发的概率求某一顾客到达就能理发的概率:(2)求需要等待的顾客数的期望值求需要等待的顾客数的期望值:(3)求有效到达率求有效到达率:(4)求一顾客在系统中的逗留时间和排队时间平均值求一顾客在系统中的逗留时间和排队时间平均值:4545P0=0.27780P1=0.20836P2=0.15627P3=0.11720 =0.9629=96.29%P4=0.08790 故拒绝的概率为故拒绝的概率为3.71%P5=0.06593P6=0.04944(

49、5)在在可可能能到到来来的的顾顾客客中中，有有百百分分之之几几不不等等待待就就离离开开？顾客为何不等待顾客为何不等待就离去？就离去？因为系统已因为系统已经满员经满员46463.3 3.3 3.3 3.3 顾客源有限的模型顾客源有限的模型顾客源有限的模型顾客源有限的模型 M/M/1/m M/M/1/m M/M/1/m M/M/1/m 以以以以机机机机器器器器修修修修理理理理模模模模型型型型为为为为例例例例，设设设设有有有有mm台台台台机机机机器器器器(总总总总体体体体)，故故故故障障障障待待待待修修修修表表表表示示示示机机机机器器器器到到到到达达达达，修修修修理理理理工工工工是是是是服服服服务务

50、务务员员员员。机机机机器器器器修修修修好好好好后后后后有有有有可可可可能能能能再再再再坏坏坏坏，形形形形成成成成循循循循环环环环。虽虽虽虽然然然然系系系系统统统统没没没没有有有有容容容容量量量量限限限限制制制制，但但但但系系系系统统统统中中中中的的的的顾顾顾顾客客客客也也也也不不不不会会会会超超超超过过过过mm，故故故故又又又又可可可可写写写写成成成成：M/M/1/M/M/1/m/mm/mm/mm/m4747 对于有限源应按每个顾客单独考虑，求出其有效对于有限源应按每个顾客单独考虑，求出其有效到达率到达率e。这样这样e是随系统内顾客数而变化的。其状态转是随系统内顾客数而变化的。其状态转移图为：