第八章排队论.ppt

中原工学院机电学院中原工学院机电学院主讲：丁剑飞主讲：丁剑飞dingjf06@Chapter 8 排队论排队论( (Queuing TheoryQueuing Theory) )排队论的基本概念排队论的基本概念单服务台系统单服务台系统多服务台系统多服务台系统本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page 3引言引言　　　　在人们生活和生产的实践活动中，经常会遇到拥挤现象，在人们生活和生产的实践活动中，经常会遇到拥挤现象，从而产生排队为了获取较好的经济效益，有必要研究排队从而产生排队为了获取较好的经济效益，有必要研究排队现象的规律性要求得到服务的对象统称为现象的规律性要求得到服务的对象统称为顾客顾客；顾客不仅；顾客不仅可以是人，也可以是物例如等待加工的零件，出故障等待可以是人，也可以是物例如等待加工的零件，出故障等待维修的机器等都是顾客提供服务的对象称为维修的机器等都是顾客提供服务的对象称为服务机构服务机构顾客和服务机构形成了一个客和服务机构形成了一个服务系统服务系统例如到医院就医的患者例如到医院就医的患者和医院；出现故障的机器和及机器维修班组等，都是服务系和医院；出现故障的机器和及机器维修班组等，都是服务系统。

统　　　　顾客到达服务机构，当然是希望立即得到服务然而服顾客到达服务机构，当然是希望立即得到服务然而服务机构已经占满时，例如理发店的座位已满，维修班组已忙务机构已经占满时，例如理发店的座位已满，维修班组已忙于维修机器，再到的顾客只能排队等候或者消失，这样造成于维修机器，再到的顾客只能排队等候或者消失，这样造成的损失称为的损失称为排队费用排队费用例如机器的停工损失，在仓库的存储例如机器的停工损失，在仓库的存储Page 4排队论的基本概念排队论的基本概念费用，因等候而降低的价值等，都属于排队费用排队的时费用，因等候而降低的价值等，都属于排队费用排队的时间越长，排队费用越大另一方面，设立的服务机构越多，间越长，排队费用越大另一方面，设立的服务机构越多，服务效率越高，需要支付的费用也越大，然而却可以减少排服务效率越高，需要支付的费用也越大，然而却可以减少排队时间如何根据顾客的实际情况，设立适当的服务机构，队时间如何根据顾客的实际情况，设立适当的服务机构，以使得服务费用和排队费用总和最少，是排队论所要讨论和以使得服务费用和排队费用总和最少，是排队论所要讨论和解决的问题解决的问题8.1 排队论的基本概念排队论的基本概念　　　　顾客到达服务机构，依照一定的规律等待，然后接受服顾客到达服务机构，依照一定的规律等待，然后接受服务，服务完毕后离去。

这个过程称为务，服务完毕后离去这个过程称为服务过程服务过程Page 5引言引言如果顾客到达和接受服务的时间都具有随机性，那么这个服务如果顾客到达和接受服务的时间都具有随机性，那么这个服务系统就称为系统就称为随机服务系统随机服务系统，又称为，又称为排队系统排队系统；服务过程称为；服务过程称为排排队过程队过程一个排队过程，大体分为三个基本部分：输入过程、一个排队过程，大体分为三个基本部分：输入过程、排列规则、服务机构排列规则、服务机构输入过程输入过程排队规则排队规则服务机构服务机构Page 6排队论的基本概念排队论的基本概念一、输入过程一、输入过程　　对于排队系统，顾客是输入　　对于排队系统，顾客是输入输入过程输入过程是指顾客按怎样的是指顾客按怎样的规律到达服务机构顾客来源的总体称为规律到达服务机构顾客来源的总体称为顾客源顾客源例如待修机例如待修机器和维修班组所形成的排队系统，工厂的全部机器是顾客源；器和维修班组所形成的排队系统，工厂的全部机器是顾客源；对于到理发店来理发的顾客来说，全体居民是顾客源，等等对于到理发店来理发的顾客来说，全体居民是顾客源，等等顾客源可以是无限集合，也可以是有限集合。

顾客可能单个到顾客源可以是无限集合，也可以是有限集合顾客可能单个到达，也可能是成批到达，或者是接连不断地到达本章我们主达，也可能是成批到达，或者是接连不断地到达本章我们主要讨论称为泊松流或者最简单流的到达方式要讨论称为泊松流或者最简单流的到达方式1. 泊松流（记为泊松流（记为M））　　顾客的输入过程如果具备以下三个特点，则称为　　顾客的输入过程如果具备以下三个特点，则称为泊松流泊松流Page 7排队论的基本概念排队论的基本概念（（1））平稳性平稳性 对于任何对于任何t>0和非负整数和非负整数k，在区间，在区间(a,a+t]内有内有k个顾客到达系统的概率对任何个顾客到达系统的概率对任何a≥0都是相等的也就是说，都是相等的也就是说，这个概率只与这个概率只与t和和k有关，而与有关，而与a有关我们以有关我们以vk(t)记这个概率，记这个概率，以以x(t)记在长为记在长为t的时间段内到达的顾客数，则有的时间段内到达的顾客数，则有（（2））无后效性无后效性 在时间区间在时间区间(a,a+t]内到达内到达k个顾客的概率与个顾客的概率与时刻时刻a以前系统的状况无关就是说，事件以前系统的状况无关就是说，事件(x(t)=k)与与a以前以前系统所发生的事件相互独立。

系统所发生的事件相互独立3））普通性普通性 记记 为在时间段为在时间段t内，到达两个和两个以上顾内，到达两个和两个以上顾客的概率，即客的概率，即 ，则有，则有t→0时，时， Page 8排队论的基本概念排队论的基本概念　　　　实际上，许多排队系统的输入过程都近似满足这些特征实际上，许多排队系统的输入过程都近似满足这些特征可以证明，凡是具备上述可以证明，凡是具备上述3个特征的输入过程，个特征的输入过程，x(t)都是服从泊都是服从泊松分布的随机变量即松分布的随机变量即x(t)的期望值和方差分别为的期望值和方差分别为E[x(t)]=λt，，Var[x(t)]=λt若取t=1，，则则E[x(1)]=λ这即是说，这即是说，λ表示单位时间内到达系统顾客数的表示单位时间内到达系统顾客数的平均值，平均值，λ称为顾客的称为顾客的到达率到达率或或输入率输入率　　还可以证明，如果顾客的到达数服从泊松分布，那么它一　　还可以证明，如果顾客的到达数服从泊松分布，那么它一定满足上述的定满足上述的3个特性8.1)Page 9排队论的基本概念排队论的基本概念2. 定长输入（记为定长输入（记为D））　　流水线上定时送往包装机的成品，其输入过程就是定长输　　流水线上定时送往包装机的成品，其输入过程就是定长输入。

如果规定的产品到达的间隔时间为入如果规定的产品到达的间隔时间为c，则相继到达产品间，则相继到达产品间隔时间隔时间t的分布函数为的分布函数为3. k阶爱尔朗分布（记为阶爱尔朗分布（记为Ek））　　设　　设t1,t2,…,tk是是k个相互独立的，且具有相同参数个相互独立的，且具有相同参数λ的负指的负指数分布随机变量，则随机变量数分布随机变量，则随机变量t=t1+t2+…+tk服从服从k阶爱尔朗分布，阶爱尔朗分布，t的密度函数为的密度函数为(8.2)Page 10排队论的基本概念排队论的基本概念　　　　　　　　　　　　　　随机变量随机变量t的期望值和方差分别为：的期望值和方差分别为：　　例如，如果顾客连续接受串联的　　例如，如果顾客连续接受串联的k个服务台的服务，各服务个服务台的服务，各服务台的服务时间相互独立，且均服从参数为台的服务时间相互独立，且均服从参数为λ的负指数分布，则顾的负指数分布，则顾客接受客接受k个服务台总共所需的时间就服从个服务台总共所需的时间就服从k阶爱尔朗分布阶爱尔朗分布8.3)Page 11排队论的基本概念排队论的基本概念4. 一般独立输入（记为一般独立输入（记为GI)　　如果各相继到达顾客的间隔时间　　如果各相继到达顾客的间隔时间t1,t2,…是相互独立的同是相互独立的同分布的随机变量，那么称为一般独立输入。

分布的随机变量，那么称为一般独立输入二、排队规则二、排队规则　　所谓　　所谓排队规则排队规则，就是到达服务机构的顾客，若不能立即得，就是到达服务机构的顾客，若不能立即得到服务，应按怎样的方式等待接受服务到服务，应按怎样的方式等待接受服务　　　　1. 等待制等待制　　顾客到达后，如果服务机构已经占满，当允许顾客等待时，　　顾客到达后，如果服务机构已经占满，当允许顾客等待时，再到的顾客便排队等待常见的有以下几种排队方式：再到的顾客便排队等待常见的有以下几种排队方式：Page 12排队论的基本概念排队论的基本概念　　（　　（1））先到先服务先到先服务 这是最普遍的情形这是最普遍的情形　　（　　（2））后到先服务后到先服务 许多存储系统运用这种规则许多存储系统运用这种规则　　（　　（3））随机服务随机服务 当一名顾客服务完毕离去时，随机地从等当一名顾客服务完毕离去时，随机地从等待的顾客中选择一名进行服务等待中的每位顾客被选中的概待的顾客中选择一名进行服务等待中的每位顾客被选中的概率是相等的，例如订票服务率是相等的，例如订票服务　　（　　（4））优先服务优先服务 对于不同的顾客规定不同的优先权，具备对于不同的顾客规定不同的优先权，具备较高优先权的顾客优先接受服务。

较高优先权的顾客优先接受服务　　　　2. 消失制消失制　　当服务机构已经全部占满时，再到的顾客不能进入服务系　　当服务机构已经全部占满时，再到的顾客不能进入服务系统，顾客自动消失，也就是不允许排队的情形对于消失制的统，顾客自动消失，也就是不允许排队的情形对于消失制的情形，不存在排队现象主要考虑的是顾客消失的概率和服务情形，不存在排队现象主要考虑的是顾客消失的概率和服务机构的利用率机构的利用率Page 13排队论的基本概念排队论的基本概念　　　　3. 混合制混合制　　等待制的排队方式可以认为排队的队伍长度没有限制当　　等待制的排队方式可以认为排队的队伍长度没有限制当允许排队、但服务机构的空间和排队时间有限时，队伍长度必允许排队、但服务机构的空间和排队时间有限时，队伍长度必然有一定的限制，这种情形称为然有一定的限制，这种情形称为混合制混合制　　（　　（1））等待空间有限等待空间有限 若服务机构最多只能容纳若服务机构最多只能容纳k个顾客，当个顾客，当顾客少于顾客少于k时，再来者可以排队等待，当顾客等于时，再来者可以排队等待，当顾客等于k时，再来的时，再来的顾客就自动消失顾客就自动消失　　（　　（2））等待时间有限等待时间有限 若顾客从进入系统开始，到开始接受若顾客从进入系统开始，到开始接受服务为止，这段等候的时间称为服务为止，这段等候的时间称为等待时间等待时间，也就是顾客在排队，也就是顾客在排队系统中排队所占的时间。

当顾客的等待时间有限时，到时若不系统中排队所占的时间当顾客的等待时间有限时，到时若不能得到服务，那么顾客就会自动消失能得到服务，那么顾客就会自动消失　　（　　（3））逗留时间优先逗留时间优先 顾客从进入系统到接受服务完毕离开顾客从进入系统到接受服务完毕离开Page 14排队论的基本概念排队论的基本概念这段时间称为这段时间称为逗留时间逗留时间也就是说，逗留时间等于等待时间加也就是说，逗留时间等于等待时间加接受服务的时间接受服务的时间　　　　三、服务机构三、服务机构　　服务机构中可能是单服务台，也可能是多服务台当有多　　服务机构中可能是单服务台，也可能是多服务台当有多个服务台时，排队的顾客可以排成一个队，依次到空出的服务个服务台时，排队的顾客可以排成一个队，依次到空出的服务台去接受服务；也可以每个服务台前排成一队，且一旦排好后，台去接受服务；也可以每个服务台前排成一队，且一旦排好后，不能再更换不能再更换Page 15排队论的基本概念排队论的基本概念　　本章首先讨论单服务台的情形由于顾客的情形不同，　　本章首先讨论单服务台的情形由于顾客的情形不同，服务所需要的时间（称为服务所需要的时间（称为服务时间服务时间））T也不同，因此也不同，因此T是个随是个随机变量。

最常见的情形是机变量最常见的情形是T服从负指数分布，即服从负指数分布，即T的概率密度的概率密度函数为函数为　　　　(8.4)Page 16排队论的基本概念排队论的基本概念其中参数其中参数μ>0T的分布函数为的分布函数为对于服从负指数分布的时间对于服从负指数分布的时间T，有一个特性，就是不论过去已经，有一个特性，就是不论过去已经服务多久，如果到现在仍然没有服务完毕，那么剩余的服务时服务多久，如果到现在仍然没有服务完毕，那么剩余的服务时间仍具有原来的概率分布即对任何间仍具有原来的概率分布即对任何t, >0(8.5)(8.6)Page 17排队论的基本概念排队论的基本概念这个性质称为这个性质称为无后效性无后效性或或马尔科夫性马尔科夫性可以证明，凡是具有这可以证明，凡是具有这个性质的随机变量，必须服从负指数分布对于负指数分布，个性质的随机变量，必须服从负指数分布对于负指数分布，其期望和方差分别为：其期望和方差分别为：这就是说，这就是说，μ表示在单位时间中可以为多少个顾客服务完毕，称表示在单位时间中可以为多少个顾客服务完毕，称为为服务率服务率　　现举一例设一个顾客到达服务机构后，有　　现举一例。

设一个顾客到达服务机构后，有c个服务率都为个服务率都为μ的服务台同时为其服务，只要有一个服务台完成服务过程，那的服务台同时为其服务，只要有一个服务台完成服务过程，那么整个服务就结束例如么整个服务就结束例如c个命中率相同的射手对一个目标进行个命中率相同的射手对一个目标进行射击，只要有一名射手射中，那么目标就被消灭由于射击，只要有一名射手射中，那么目标就被消灭由于(8.7)Page 18排队论的基本概念排队论的基本概念　　　　　　　　　　这个结果表明参加工作的服务台越多，平均所需要的服务时间这个结果表明参加工作的服务台越多，平均所需要的服务时间越短四、排队系统的分类四、排队系统的分类　　　　D.G. Kendall 在在1953年提出一个分类方法，按照上述各部年提出一个分类方法，按照上述各部分特征中最主要的，影响最大的三个，即：分特征中最主要的，影响最大的三个，即：　　（　　（1）相继顾客到达间隔时间的分布；）相继顾客到达间隔时间的分布；　　（　　（2）服务时间分布；）服务时间分布；Page 19排队论的基本概念排队论的基本概念　　（　　（3）服务台个数服务台个数　　按照这三个特征分类，并利用一定符号表示，称为　　按照这三个特征分类，并利用一定符号表示，称为Kendall记号。

这只对并列的服务台（如果服务台多于一个的记号这只对并列的服务台（如果服务台多于一个的话）的情形，他使用的符号形式是话）的情形，他使用的符号形式是　　　　　　　　　　　　　　　　　　　　X/Y/Z其中，其中，X处填写表示相继到达的间隔时间分布的记号：处填写表示相继到达的间隔时间分布的记号：　　　　　　Y处填写表示服务时间分布的记号；处填写表示服务时间分布的记号；　　　　　　Z处填写并列的服务台数目处填写并列的服务台数目　　表示相继到达间隔时间和服务时间的各种分布符号是：　　表示相继到达间隔时间和服务时间的各种分布符号是：　　　　M—负指数分布（负指数分布（M是是Markov的字头，因为负指数分布具的字头，因为负指数分布具有无记忆性，即有无记忆性，即Markov性）；性）；Page 20排队论的基本概念排队论的基本概念　　　　D—确定型（确定型（Deterministic））　　　　Ek—k阶爱尔朗（阶爱尔朗（Erlang）分布；）分布；　　　　GI—一般相互独立（一般相互独立（General Independent)的时间间隔的的时间间隔的分布；分布；　　　　G—一般一般(General)服务时间的分布。

服务时间的分布　　后来，在　　后来，在1971年一次关于排队论符号标准化会议上，又将年一次关于排队论符号标准化会议上，又将Kendall符号扩充变为符号扩充变为 X/Y/Z/A/B/C　　其中前三项意义不变，而　　其中前三项意义不变，而A处填写系统容量限制处填写系统容量限制N，，B处填处填写顾客源数目写顾客源数目m，，C处填写服务规则，例如先到先服务处填写服务规则，例如先到先服务FCFS，，后到先服务后到先服务LCFS等，并约定，如约去后三项，即指等，并约定，如约去后三项，即指X/Y/Z/∞/∞/FCFS的情形Page 21排队论的基本概念排队论的基本概念五、主要的数量指标五、主要的数量指标　　经常运用以下几个数量指标来评价一个排队系统　　经常运用以下几个数量指标来评价一个排队系统　　　　1. 队伍长度队伍长度　　在排队系统中的平均顾客数，称为队伍长度，简称队长，　　在排队系统中的平均顾客数，称为队伍长度，简称队长，这是顾客和设计人员都关心的问题队长的大小直接关系到顾这是顾客和设计人员都关心的问题队长的大小直接关系到顾客的利益，也关系到服务机构的利用率。

客的利益，也关系到服务机构的利用率　　　　2. 逗留时间逗留时间w和等待时间和等待时间wq的分布的分布　　这是顾客最关心的指标，但各个顾客关心的角度不同例　　这是顾客最关心的指标，但各个顾客关心的角度不同例如就诊病人对等待时间比较关心，对诊断时间却不希望太快如就诊病人对等待时间比较关心，对诊断时间却不希望太快　　　　3. 服务台的利用率服务台的利用率　　服务台工作的时间占总时间的比例，可以衡量服务台的劳　　服务台工作的时间占总时间的比例，可以衡量服务台的劳动强度及服务成本的大小这是服务部门所关心的动强度及服务成本的大小这是服务部门所关心的Page 22排队论的基本概念排队论的基本概念　　　　4. 顾客损失率顾客损失率　　对于消失制和混合制的排队系统，必须考虑因服务能力不　　对于消失制和混合制的排队系统，必须考虑因服务能力不足导致顾客消失的比例，因为这直接关系到经济利益足导致顾客消失的比例，因为这直接关系到经济利益Page 23单服务台系统单服务台系统　　　　本节将讨论输入过程服从泊松分布过程、服务时间服从负本节将讨论输入过程服从泊松分布过程、服务时间服从负指数分布、单服务台的排队系统。

现将其分为：指数分布、单服务台的排队系统现将其分为：标准的标准的M/M/1模型（模型（M/M/1/∞/∞/FCFS ））　　标准的　　标准的M/M/1是指符合下列条件的排队系统：是指符合下列条件的排队系统：　　（　　（1）输入过程）输入过程——顾客源是无限的，顾客单个到来，相顾客源是无限的，顾客单个到来，相互独立，一定的到达时间服从泊松分布，到达过程平稳互独立，一定的到达时间服从泊松分布，到达过程平稳　　（　　（2）排队规则）排队规则—单队，且队长没有限制，先到先服务单队，且队长没有限制，先到先服务　　（　　（3）服务机构）服务机构—单服务台，各顾客的服务时间相互独立，单服务台，各顾客的服务时间相互独立，服从相同的负指数分布服从相同的负指数分布　　此外，还假定到达间隔时间和服务时间相互独立　　此外，还假定到达间隔时间和服务时间相互独立Page 24单服务台系统单服务台系统　　在分析标准的　　在分析标准的M/M/1模型时首先要求出系统在任意时刻模型时首先要求出系统在任意时刻t的的状态为状态为n（系统中有（系统中有n个顾客）的概率个顾客）的概率Pn(t)，它决定了系统运，它决定了系统运行的特征。

行的特征　　因为已知到达规律服从参数为　　因为已知到达规律服从参数为λ的泊松过程，服务时间服的泊松过程，服务时间服从参数为从参数为μ的负指数分布，所以在的负指数分布，所以在[t,t+Δt]时间区间内分为：时间区间内分为：　　（　　（1）有）有1个顾客到达的概率为个顾客到达的概率为λΔt+ο(Δt)；没有顾客到达的；没有顾客到达的概率是概率是1- λΔt+ο(Δt)　　（　　（2）当顾客在接受服务时，）当顾客在接受服务时，1个顾客被服务完了（离去）个顾客被服务完了（离去）的概率是的概率是μΔt+ο(Δt)，没有离去的概率概率是，没有离去的概率概率是1- μΔt+o(Δt)　　（　　（3）多于）多于1个顾客到达或离去的概率是个顾客到达或离去的概率是o(Δt)，是可以忽略，是可以忽略的Page 25单服务台系统单服务台系统　　　　在时刻在时刻t+Δt，系统中有，系统中有n个顾客（个顾客（n>0）存在下列四种情况）存在下列四种情况（到达或离去（到达或离去2个以上的没列入）个以上的没列入）情况情况在时刻在时刻t顾客数顾客数在区间在区间[t, Δt]在时刻在时刻t+Δt顾客数顾客数到达到达离去离去(A)n××n(B)n+1×〇〇n(C)n-1〇〇×n(D)n〇〇〇〇nPage 26单服务台系统单服务台系统它们的概率分别是（略去它们的概率分别是（略去o(Δt)）：）：　　情况（　　情况（A）） Pn(t)(1-λΔt)(1-μΔt)　　情况（　　情况（B) Pn+1(t)(1-λΔt)·μΔt　　　　情况（情况（C) Pn-1(t)·λΔt(1-μΔt)　　情况（　　情况（D）） Pn(t)·λΔt·μΔt)　　　　这四种情况是不相容的，所以这四种情况是不相容的，所以Pn(t+Δt)应是这四项之和，应是这四项之和，即（将关于即（将关于Δt的高阶无穷小合成一项）的高阶无穷小合成一项）　　　　 Pn(t+Δt)=Pn(t)(1-λΔt-μΔt)+Pn+1(t)μΔt+Pn-1(t)λΔt+o(Δt)令令Δt→0，得关于，得关于Pn(t)的微分差分方程的微分差分方程Page 27单服务台系统单服务台系统当当n=0，则只有上表中，则只有上表中A、、B两种情况，即两种情况，即　　　　P0(t+Δt)=P0(t)(1-λΔt ) +P1(t)(1-λΔt)μΔt　　同理求得同理求得这样系统状态（这样系统状态（n）随时间变化的过程是称为）随时间变化的过程是称为生灭过程生灭过程的一个的一个特殊情况。

特殊情况　　解式（　　解式（8.8）和（）和（8.9）是很麻烦的，求得的解（瞬态解））是很麻烦的，求得的解（瞬态解）中因为含有修正的贝塞尔函数，也不便于应用，我们只讨中因为含有修正的贝塞尔函数，也不便于应用，我们只讨(8.8)(8.9)Page 28单服务台系统单服务台系统论稳态的情况，这时论稳态的情况，这时Pn(t)与与t无关，可写成无关，可写成Pn，它的导数为，它的导数为0由式（由式（8.8）和（）和（8.9）可得）可得　这是关于　这是关于Pn的差分方程它表明了个状态间的转移关系，用的差分方程它表明了个状态间的转移关系，用下图表示下图表示8.10)(8.11)Page 29单服务台系统单服务台系统由上图可见，状态由上图可见，状态0转移到状态转移到状态1的转移率为的转移率为λP0，状态，状态1转移到转移到状态状态0的转移率为的转移率为μP1对状态0必须满足以下平衡方程：必须满足以下平衡方程： λP0= μP1　　同样，对于任何同样，对于任何n≥1的状态，可得到式（的状态，可得到式（8.11）的平衡方程的平衡方程求解式（求解式（8.10）得：）得：　　　　P1=(λ/μ)P0　将它带入式（　将它带入式（8.11），令），令n=1则有则有　　　　μP2=(λ+μ) (λ/μ)P0-λP0, P2=(λ/μ)2P0　　同理依次推得同理依次推得　　　　 Pn=(λ/μ)nP0　今设　今设 ，又由概率的性质知，又由概率的性质知Page 30单服务台系统单服务台系统　将　将Pn的关系式带入，有的关系式带入，有　得　　　　　　　　　得　　　　　　　　　　上式的　　上式的ρ有其实际意义。

根据表达式的不同，可以有不同的有其实际意义根据表达式的不同，可以有不同的解释当ρ=λ/μ表达时，它是平均到达率与平均服务率之比若表达时，它是平均到达率与平均服务率之比若表示为表示为ρ=(1/μ)/(1/λ)，它是为一个顾客服务时间与到达间隔时间，它是为一个顾客服务时间与到达间隔时间之比；称之比；称ρ为为服务强度服务强度，或称，或称话务强度话务强度8.12)Page 31单服务台系统单服务台系统式式ρ=1-P0刻画了服务机构的繁忙程度；所以又称为刻画了服务机构的繁忙程度；所以又称为服务机构的服务机构的利用率利用率　　以式（　　以式（8.12）为基础可以计算出系统的运行指标：）为基础可以计算出系统的运行指标：　　（　　（1）在系统中平均顾客数（队长期望值）在系统中平均顾客数（队长期望值）Page 32单服务台系统单服务台系统　　（　　（2）在队列中等待的平均顾客数（队列长期望值）在队列中等待的平均顾客数（队列长期望值）　　　　　　关于顾客在系统中逗留的时间　　关于顾客在系统中逗留的时间W（随机变量），在（随机变量），在M/M/1情况下，它服从参数为情况下，它服从参数为μ-λ的负指数分布，即的负指数分布，即　　分布函数　　分布函数F(ω)=1-e-(μ-λ)ω，，ω≥0　　概率密度　　概率密度f(ω)=(μ-λ)e-(μ-λ)ω　　（　　（3）在系统中顾客逗留时间的期望值）在系统中顾客逗留时间的期望值Page 33单服务台系统单服务台系统（（4）在队列中顾客等待时间的期望值。

在队列中顾客等待时间的期望值　　　　　　　　　　　现将以上各式归纳如下：　现将以上各式归纳如下：(8.13)Page 34单服务台系统单服务台系统例例8.1 某医院手术室根据病人来诊和完成手术时间的记录，任意某医院手术室根据病人来诊和完成手术时间的记录，任意抽查抽查100个工作小时，每小时来就诊的病人出现次数见左下表个工作小时，每小时来就诊的病人出现次数见左下表又任意抽查了又任意抽查了100个完成手术的病例，所用时间（小时）的出现个完成手术的病例，所用时间（小时）的出现次数见右下表次数见右下表到达的病人数到达的病人数n出现次数出现次数fn0123456以上以上102829161061合计合计100完成手术时间完成手术时间v出现次数出现次数fv0.0~0.20.2~0.40.4~0.60.6~0.80.8~1.01.0~1.21.2以上以上3825179650合计合计100Page 35单服务台系统单服务台系统　　（　　（1）计算：）计算：　　每小时病人平均达到率　　每小时病人平均达到率=　　每次手术平均时间　　每次手术平均时间=　　每小时完成手术人数（平均服务率）　　每小时完成手术人数（平均服务率）=1/0.4=2.5人人/小时小时 　　（　　（2）取）取λ=2.1，，μ=2.5，可以通过统计检验的方法（如，可以通过统计检验的方法（如χ2检检验法），认为病人到达服从参数为验法），认为病人到达服从参数为2.1的泊松分布，手术时间服的泊松分布，手术时间服从参数为从参数为2.5的负指数分布。

的负指数分布　　（　　（3））　　它说明服务机构（手术室）有　　它说明服务机构（手术室）有84%的时间是繁忙的，平均的时间是繁忙的，平均16%的时间空闲的时间空闲Page 36单服务台系统单服务台系统　　（　　（4）依次带入（）依次带入（8.13），计算出各指标：），计算出各指标：　　在病房中病人数（期望值）　　在病房中病人数（期望值）　　排队等待病人数（期望值）　　排队等待病人数（期望值）　　病人在病房中逗留时间（期望值）　　病人在病房中逗留时间（期望值）　　病人排队等待时间（期望值）　　病人排队等待时间（期望值）　　不同的服务规则（先到先服务，后到先服务，随即服务）　　不同的服务规则（先到先服务，后到先服务，随即服务）它们的不同点主要反映在等待时间的分布函数的不同，而一些它们的不同点主要反映在等待时间的分布函数的不同，而一些期望值是相同的上面讨论的各种指标，因为都是期望值，所期望值是相同的上面讨论的各种指标，因为都是期望值，所以这些指标的计算公式对三种服务规则都适用（但对有优先权以这些指标的计算公式对三种服务规则都适用（但对有优先权的规则不适用）的规则不适用）Page 37单服务台系统单服务台系统系统容量有限制的情况（系统容量有限制的情况（M/M/1/N/∞））　　如果系统的最大容量为　　如果系统的最大容量为N，对于单服务台的情形，排队等，对于单服务台的情形，排队等待的顾客最多为待的顾客最多为N-1，在某时刻一顾客到达时，如果系统中已，在某时刻一顾客到达时，如果系统中已经有经有N个顾客，那么这个顾客就被拒绝进入系统。

个顾客，那么这个顾客就被拒绝进入系统　　当　　当N=1是为即时服务的情形，当是为即时服务的情形，当N→∞，为容量无限制的情，为容量无限制的情形　　若只考虑稳态的情形，可作各状态间概率强度的转换关系　　若只考虑稳态的情形，可作各状态间概率强度的转换关系图Page 38单服务台系统单服务台系统根据上图，列出状态概率的稳态方程：根据上图，列出状态概率的稳态方程：　　　　　　　　　　解这个差分方程与解（　　解这个差分方程与解（8.3）（）（8.4）很类似，所不同的是）很类似，所不同的是　　　　P0+P1+…+PN=1　　仍令　　仍令ρ=λ/μ，因而得，因而得Page 39单服务台系统单服务台系统在对容量没有限制的情形，我们曾设在对容量没有限制的情形，我们曾设ρ<1，这个仅是实际问题，这个仅是实际问题的需要，也是无穷级数收敛所必需的在容量为有限数的需要，也是无穷级数收敛所必需的在容量为有限数N的情的情形下，这个条件就没有必要了（为什么？）当形下，这个条件就没有必要了（为什么？）当ρ>1时，表示时，表示损失率的损失率的PN（或表示被拒绝排队的顾客平均数（或表示被拒绝排队的顾客平均数λPN）将是很大）将是很大的。

的　　根据式（　　根据式（8.9）我们可以导出系统的各种指标（计算过程略））我们可以导出系统的各种指标（计算过程略）：：　　（　　（1）队长（期望值））队长（期望值）　　　　　　　　　　　　　　（　　（2）队列长（期望值））队列长（期望值）Page 40单服务台系统单服务台系统　　　　　　　　　　　　　　当研究顾客在系统平均逗留时间　　当研究顾客在系统平均逗留时间Ws和在队列中平均等待时和在队列中平均等待时间间Wq时，虽然公式（时，虽然公式（8.7）仍可以利用，但要注意平均到达率）仍可以利用，但要注意平均到达率λ是在系统有空时的平均到达率当系统已满，是在系统有空时的平均到达率当系统已满，n=N时，则到达时，则到达率为率为0，因此需要求出有效到达率，因此需要求出有效到达率λe=λ(1-PN)可以验证可以验证　　（　　（3）顾客逗留时间（期望值）顾客逗留时间（期望值）　　　　　　（　　（4）顾客等待时间（期望值））顾客等待时间（期望值）Wq=Ws-1/μPage 41单服务台系统单服务台系统现把现把M/M/1/N/∞型的指标归纳如下（型的指标归纳如下（ρ≠1）：）：　　　　　　　　　　　　　　　　例例8.2 单人理发馆有单人理发馆有6张椅子接待人们排队等待理发。

当张椅子接待人们排队等待理发当6个个椅子都坐满时，后来到的客人不进店就离开顾客平均到达率椅子都坐满时，后来到的客人不进店就离开顾客平均到达率为为3人人/小时，理发平均小时，理发平均15分钟分钟/人则　　　　N=7为系统中最大的顾客数，为系统中最大的顾客数，λ=3人人/小时，小时，μ=4人人/小时　　（　　（1）求某顾客一到达就能理发的概率）求某顾客一到达就能理发的概率(8.14)Page 42单服务台系统单服务台系统　这种情况相当于理发馆内没有顾客，所求概率　这种情况相当于理发馆内没有顾客，所求概率　　　　　　　　　　（　　（2）求需要等待的顾客数的期望值）求需要等待的顾客数的期望值　　　　　　　　　　　　　　　　（　　（3）求有效到达率）求有效到达率　　（　　（4）求一顾客在理发馆内逗留的期望时间）求一顾客在理发馆内逗留的期望时间Page 43单服务台系统单服务台系统　　　　Ws=Ls/λ=2.11/2.89=0.73(小时小时)=43.8(分钟分钟)　　（　　（5）在可能到来的顾客中，不等就离开的概率）在可能到来的顾客中，不等就离开的概率　　这就是求系统中有　　这就是求系统中有7个顾客的概率个顾客的概率　　　　　　这也是理发馆的损失率。

现以本例比较对长为无限和有限　　这也是理发馆的损失率现以本例比较对长为无限和有限两种结果如下：两种结果如下：λ=3人人/ /小时小时μ=4人人/ /小时小时LsLqWsWqP0P7有限队长有限队长N=7N=72.111.390.730.480.2783.7%无限队长无限队长32.251.00.750.250Page 44单服务台系统单服务台系统顾客源为有限的情形（顾客源为有限的情形（M/M/1/∞/m））　　现以常见的机器因故障停机待修的问题来说明设共有　　现以常见的机器因故障停机待修的问题来说明设共有m台机器（顾客总体），机器因故障停机表示台机器（顾客总体），机器因故障停机表示“到达到达”，待修的，待修的机器形成队列，修理工人是服务机构，这里只讨论单服务台的机器形成队列，修理工人是服务机构，这里只讨论单服务台的情形类似的例子还有情形类似的例子还有m个打字员共用一台打字机，个打字员共用一台打字机，m个会计个会计共用一个计算机终端等等顾客总体虽然只有共用一个计算机终端等等顾客总体虽然只有m个，但每个顾个，但每个顾客到来并经过服务后，仍然回到原来总体，所以仍然可以到来客到来并经过服务后，仍然回到原来总体，所以仍然可以到来。

在机器故障问题中，同一台机器除了故障（到来）并经修好在机器故障问题中，同一台机器除了故障（到来）并经修好（服务完了）仍可再出现故障（见下图）模型中的第四项虽（服务完了）仍可再出现故障（见下图）模型中的第四项虽然写了然写了∞，这表示对系统的容量没有限制，但实际上它永远不，这表示对系统的容量没有限制，但实际上它永远不会超过会超过m，所以和写成（，所以和写成（M/M/1/m/m）的意义相同的意义相同Page 45单服务台系统单服务台系统　　　　　　　　　　　　关于平均达到率，在无限源的情形是按照全体顾客来考虑　　关于平均达到率，在无限源的情形是按照全体顾客来考虑的；在有限源的情形必须按每个顾客来考虑为了简单起见，的；在有限源的情形必须按每个顾客来考虑为了简单起见，设各个顾客的到达率都是相同的设各个顾客的到达率都是相同的λ（在这里（在这里λ 的含义是每台机器的含义是每台机器单位运转时间内发生故障的概率或平均次数），这时在系统外单位运转时间内发生故障的概率或平均次数），这时在系统外的顾客平均数为的顾客平均数为m-L，对系统的有效到达率，对系统的有效到达率λe应是　　　　　应是　　　　　Page 46单服务台系统单服务台系统对于对于(M/M/1/∞/m)模型的分析可以用前述的方法。

在稳态的情模型的分析可以用前述的方法在稳态的情况下，考虑状态间的转移率当由况下，考虑状态间的转移率当由0状态转移到状态状态转移到状态1，每台设，每台设备由正常状态转移为故障状态，其转移率为备由正常状态转移为故障状态，其转移率为λP0，现有，现有m台设备台设备无故障状态转移为有一台设备（不论哪一台）发生故障，其转无故障状态转移为有一台设备（不论哪一台）发生故障，其转移率为移率为mλP0至于由状态至于由状态1转移到状态转移到状态0，其状态转移率为，其状态转移率为μP1所以在状态所以在状态0时有平衡方程时有平衡方程mλP0=μP1其关系可以由下图表示其关系可以由下图表示由图可得到各状态间的转移差分方程由图可得到各状态间的转移差分方程Page 47单服务台系统单服务台系统解这些差分方程，用递推方法，并注意到解这些差分方程，用递推方法，并注意到Page 48单服务台系统单服务台系统　得　得　　求得系统的各项指标为　　求得系统的各项指标为(8.15)(8.16)Page 49单服务台系统单服务台系统　在机器故障问题中　在机器故障问题中Ls就是平均故障台数，而就是平均故障台数，而m-Ls表示正常运表示正常运转的平均台数。

转的平均台数m-Ls=(μ/λ)(1-P0)例例5 某车间有某车间有5台机器，每台机器的连续运转时间服从负指数分台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间布，平均连续运转时间15分钟，有一个修理工，每次修理时间分钟，有一个修理工，每次修理时间服从负指数分布，平均每次服从负指数分布，平均每次12分钟求：分钟求：　　（　　（1）修理工空闲的概率；）修理工空闲的概率；　　（　　（2）五台机器都出故障的概率；）五台机器都出故障的概率；　　（　　（3）出故障的平均台数；）出故障的平均台数；　　（　　（4）等待修理的平均台数；）等待修理的平均台数；　　（　　（5）平均停工时间；）平均停工时间；　　（　　（6）平均等待修理时间；）平均等待修理时间；　　（　　（7）评价这些结果评价这些结果Page 50单服务台系统单服务台系统解解 m=5，，λ=1/15，，μ=1/12，，λ/μ=0.8　　Page 51多服务台负指数分布的排队系统多服务台负指数分布的排队系统　　现在讨论单队、并列的多服务台（服务台数　　现在讨论单队、并列的多服务台（服务台数c）的情形，）的情形，分以下三种情形：分以下三种情形：　　（　　（1）标准的）标准的M/M/c模型模型(M/M/c/∞/∞)　　（　　（2）系统容量有限制）系统容量有限制(M/M/c/N/∞））　　（　　（3）有限客源）有限客源(M/M/c/∞/m) 标准的标准的M/M/c模型模型(M/M/c/∞/∞)　　标准　　标准M/M/c模型各种特征的规定与标准的模型各种特征的规定与标准的M/M/1模型的规模型的规定相同。

另外规定各服务台是相互独立的，且平均服务效率相定相同另外规定各服务台是相互独立的，且平均服务效率相同，即同，即μ1=μ2…=μ1=μ于是整个服务台的平均服务效率为于是整个服务台的平均服务效率为cμ令令ρ=λ/cμ，只有当，只有当ρ<1才不会排成无限长的的队列，称它为这才不会排成无限长的的队列，称它为这个系统的服务强度，或称机构的平均利用率个系统的服务强度，或称机构的平均利用率Page 52多服务台负指数分布的排队系统多服务台负指数分布的排队系统在分析排队系统时，仍从状态间的转移关系开始（如下图）在分析排队系统时，仍从状态间的转移关系开始（如下图）如状态如状态1转移到状态转移到状态0，即系统中有一名顾客服务完了（离去），即系统中有一名顾客服务完了（离去）的转移率为的转移率为μP1，状态，状态2转移到状态转移到状态1，这就是在两个服务台上被，这就是在两个服务台上被服务的服务的1个被服务完离去，因为不限哪一个，这时的状态转移率个被服务完离去，因为不限哪一个，这时的状态转移率便是便是2μP2同理，再考虑状态同理，再考虑状态n转移到状态转移到状态n-1的情况当的情况当n≤c时，时，状态转移率为状态转移率为nμPn；当；当n>c时，因为只有时，因为只有c个服务台，最多有个服务台，最多有c个个顾客在服务，顾客在服务，n-c个顾客在等待，因此转移率应为个顾客在等待，因此转移率应为cμPn。

Page 53多服务台负指数分布的排队系统多服务台负指数分布的排队系统　　由上图可得：　　　　由上图可得：　　　　　　　　这里　　这里　　用递推法解上述差分方程，可求得状态概率　　用递推法解上述差分方程，可求得状态概率Page 54多服务台负指数分布的排队系统多服务台负指数分布的排队系统　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　平均队长　　平均队长Page 55多服务台负指数分布的排队系统多服务台负指数分布的排队系统平均等待时间和逗留时间平均等待时间和逗留时间　　　　　　　　　　　　例例6 某售票处有三个窗口，顾客的到达服从泊松过程，平某售票处有三个窗口，顾客的到达服从泊松过程，平均达到率均达到率λ=0.9（人），服务时间服从负指数分布，平均服务（人），服务时间服从负指数分布，平均服务率每分钟率每分钟μ=0.4人现设顾客到达后排成一队，依次向空闲的人现设顾客到达后排成一队，依次向空闲的窗口购票就形成一个窗口购票就形成一个M/M/c型的系统，其中型的系统，其中c=3，，λ/μ=2.25，，ρ=λ/cμ=2.25/3(<1)符合要求的条件，带入公式得：符合要求的条件，带入公式得：　　（　　（1）整个售票处空闲概率）整个售票处空闲概率Page 56多服务台负指数分布的排队系统多服务台负指数分布的排队系统　　（　　（2）平均队长）平均队长　　　　　　（　　（3）平均等待时间和逗留时间）平均等待时间和逗留时间　　　　　　顾客到达后必须等待（即系统中已有　　顾客到达后必须等待（即系统中已有3个人即个服务台都个人即个服务台都没有空闲）的概率没有空闲）的概率　　　　Page 57多服务台负指数分布的排队系统多服务台负指数分布的排队系统系统容量为有限的情形系统容量为有限的情形M/M/c/N/∞　　系统容量最大限制为　　系统容量最大限制为N(N≥c)，当系统中顾客数，当系统中顾客数n已达到已达到N（即队列中顾客人数已达（即队列中顾客人数已达N-c）时，再来的顾客即被拒绝，其）时，再来的顾客即被拒绝，其他条件与标准他条件与标准M/M/c相同。

相同　　这时系统的状态概率和运行指标如下：　　这时系统的状态概率和运行指标如下：　　　　Page 58多服务台负指数分布的排队系统多服务台负指数分布的排队系统　　其中　　其中ρ=λ/cμ，并且不必限制，并且不必限制ρ<1 　　其中，当　　其中，当n=c即关于即关于Pc的公式被称为爱尔朗呼唤损失公式的公式被称为爱尔朗呼唤损失公式　　这时的运行指标如下：　　这时的运行指标如下：Page 59多服务台负指数分布的排队系统多服务台负指数分布的排队系统　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　顾客源为有限的情形（顾客源为有限的情形（M/M/c/∞/m））　　设顾客源为有限数　　设顾客源为有限数m，且，且m>c，和单服务台情形一样，顾，和单服务台情形一样，顾客到达率客到达率λ是按照每个顾客来考虑的，在机器管理问题中，就是是按照每个顾客来考虑的，在机器管理问题中，就是m台机器，有台机器，有c个修理工人，顾客到达就是机器出了故障，而每个修理工人，顾客到达就是机器出了故障，而每个顾客的到达率个顾客的到达率λ是指每台机器单位运转时间出故障的期望次数是指每台机器单位运转时间出故障的期望次数。

系统中顾客数系统中顾客数n就是出故障的机器就是出故障的机器Page 60多服务台负指数分布的排队系统多服务台负指数分布的排队系统台数，当台数，当n≤c时，所有的故障机器都被在修理，有时，所有的故障机器都被在修理，有(c-n)个修理个修理工人在空闲；当工人在空闲；当c