第12章排队论(清华教材)ppt课件.ppt

《第12章排队论(清华教材)ppt课件.ppt》由会员分享，可在线阅读，更多相关《第12章排队论(清华教材)ppt课件.ppt（98页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 排排 队队 论论Queueing theory 篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统一、排队系统的特征及排队论一、排队系统的特征及排队论第一节引言第一节引言排队论（排队论（queueing theory）是研究排队系统的数学理论和方法）是研究排队系统的数学理论和方法排队论又叫随机服务系统理论。排队论又叫随机服务系统理论。在日常生活中，人们会遇到各种各样的排队问题。在日常生活中，人们会遇到各种各样的排队问题。如进餐馆

2、如进餐馆就餐，到图书馆借书，在车站等车，去医院看病，去售票处就餐，到图书馆借书，在车站等车，去医院看病，去售票处购票，上工具房领物品等等购票，上工具房领物品等等。在这些问题中，餐馆的服务员。在这些问题中，餐馆的服务员与顾客、公共汽车与乘客、图书馆的出纳员与借阅者、医生与顾客、公共汽车与乘客、图书馆的出纳员与借阅者、医生与病人、售票员与买票人、管理员与工人等，均分别构成一与病人、售票员与买票人、管理员与工人等，均分别构成一个排队系统或服务系统。个排队系统或服务系统。是运筹学的一个重要分支。是运筹学的一个重要分支。排队问题的表现形式往往是拥挤现象，随着生产与服务的排队问题的表现形式往往是拥挤现象，

3、随着生产与服务的日益社会化，由排队引起的拥挤现象会愈来愈普遍。日益社会化，由排队引起的拥挤现象会愈来愈普遍。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统一、排队系统的特征（一、排队系统的特征（2）第一节引言（第一节引言（2）排队除了是排队除了是有形的队列外有形的队列外，还可以是，还可以是无形的队列无形的队列。排队的可以是人，也可以是物。排队的可以是人，也可以是物。如如生产线上的原材料或半成品在等待加工；生产线上的原材料或半成品在等待加工；因故障而停止运转的机器在等待修理；因故障而停止运转的机器在等待修理；码头上的船只等待装货或卸货

4、；码头上的船只等待装货或卸货；要降落的飞机因跑道被占用而在空中盘旋等等。要降落的飞机因跑道被占用而在空中盘旋等等。当然，提供服务的也可以是人，也可以是跑道、自动售货机、当然，提供服务的也可以是人，也可以是跑道、自动售货机、公共汽车等。公共汽车等。为了一致起见，我们约定一些术语：为了一致起见，我们约定一些术语：顾客顾客将要求得到服务的对象统称为将要求得到服务的对象统称为“顾客顾客”服务员或服务员或服务机构服务机构将提供服务的服务者称为将提供服务的服务者称为“服务员服务员或或“服务机构服务机构”篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的

5、系统排队系统的一般描述（排队系统的一般描述（1）实际的排队系统可以千差万别，但都可以一般地描述如下：实际的排队系统可以千差万别，但都可以一般地描述如下：顾客为了得到某种服务而到达系统，若不能立即获得服务而又顾客为了得到某种服务而到达系统，若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统允许排队等待，则加入等待队伍，待获得服务后离开系统顾客到达顾客到达服务台服务台服务完成后离去服务完成后离去队列队列正在接受服务的顾客正在接受服务的顾客单服务台排队系统单服务台排队系统顾客到达顾客到达服务台服务台1服务完成后离去服务完成后离去队列队列多服务台排队系统多服务台排队系统服务台服务

6、台2服务台服务台S篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统排队系统的一般描述（排队系统的一般描述（2）但不管具体的排队系统何种形式，都可描述成下列形式但不管具体的排队系统何种形式，都可描述成下列形式顾客到达顾客到达服务台服务台1服务完成后离去服务完成后离去多个队列多个队列多服务台多队列多服务台多队列的排队系统的排队系统服务台服务台2服务台服务台S多服务台串联排队系统多服务台串联排队系统队列队列顾客到达顾客到达服务台服务台1服务完成后离去服务完成后离去队列队列服务台服务台2输入（聚）输入（聚）服务机构服务机构输出（散）输出（散）

7、篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统排队系统的一般描述（排队系统的一般描述（3）上图通常上图通常称为一个随机聚散服务系统称为一个随机聚散服务系统输入（聚）输入（聚）服务机构服务机构输出（散）输出（散）任一排队系统都是一个随机聚散服务系统。任一排队系统都是一个随机聚散服务系统。“聚聚”表示顾客的到达，表示顾客的到达，“散散”表示顾客的离去。表示顾客的离去。随机性则是排队系统的一个普通特点：随机性则是排队系统的一个普通特点：是指顾客的到达情况（如相继到达时间间隔）与每个顾客接受是指顾客的到达情况（如相继到达时间间隔）与每个顾客

8、接受服务的时间往往是事先无法确切知道的，或者说是随机的。服务的时间往往是事先无法确切知道的，或者说是随机的。一般来说，排队论所研究的排队系统中，顾客相继到达时一般来说，排队论所研究的排队系统中，顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的间间隔和服务时间这两个量中至少有一个是随机的.因此，排队论又称为随机服务系统理论排队论又称为随机服务系统理论。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统二、排队系统的描述二、排队系统的描述 排队系统概括起来可看成由排队系统概括起来可看成由3个基本部分组成：个基本部分组成：1.输入过

9、程输入过程输入过程说明顾客接怎样的规律到达系统，需要输入过程说明顾客接怎样的规律到达系统，需要从三个方面来刻划一个输入过程从三个方面来刻划一个输入过程(1)顾客总体（顾客源）数顾客总体（顾客源）数 可以是有限的，也可以是无限的可以是有限的，也可以是无限的河流上游流入水库的水量可认为是无限的河流上游流入水库的水量可认为是无限的车间内停机待修的机器是有限的车间内停机待修的机器是有限的输入过程输入过程 排队及排队规则排队及排队规则服务机制服务机制(2)到达方式到达方式 是单个到达还是成批到达。是单个到达还是成批到达。库存问题中，若把进来的货看成顾客，则为成批到达库存问题中，若把进来的货看成顾客，则为

10、成批到达(3)顾客（单个或成批）相继到达时间间隔的分布顾客（单个或成批）相继到达时间间隔的分布 这是刻划输入过程的最重要的内容这是刻划输入过程的最重要的内容令令T00，Tn表示第表示第n个顾客到达的时刻个顾客到达的时刻则有则有T0 T1 T2 Tn 篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统输入过程输入过程(2)(3)顾客（单个或成批）相继到达时间间隔的分布顾客（单个或成批）相继到达时间间隔的分布 这是刻划输入过程的最重要的内容这是刻划输入过程的最重要的内容令令T00，Tn表示第表示第n个顾客到达的时刻个顾客到达的时刻则有则有T

11、0 T1 T2 Tn 顾客到达的时刻顾客到达的时刻顾客相继到达的间隔时刻顾客相继到达的间隔时刻记记Xn=Tn-Tn-1,(n1，2，)则则Xn是第是第n个顾客与第个顾客与第n一一1个顾客到达的时间间隔个顾客到达的时间间隔一般，假定一般，假定Xn是独立同分布的是独立同分布的记分布函数为记分布函数为A(t)篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统输入过程输入过程(3)1)定长分布定长分布(D)顾客相继到达时间间隔为一常数顾客相继到达时间间隔为一常数a如产品通过传送带进入包装箱就是定长分布的例子。如产品通过传送带进入包装箱就是定长分

12、布的例子。用随机变量用随机变量 表示所在顾客到达间隔时间，则表示所在顾客到达间隔时间，则P(a)=1，用分布函数表示有：用分布函数表示有：其数学期望其数学期望关于关于Xn的分布，排队论中经常用到的有以下几种：的分布，排队论中经常用到的有以下几种：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统输入过程输入过程(4)称称 服从负指数分布，其分布函数为服从负指数分布，其分布函数为负指数分布常作各种负指数分布常作各种“寿命寿命”分布的近似，分布的近似，例如无线电例如无线电器元件的寿命、动物寿命、电话问题中的通话时间等器元件的寿命、动物寿命、

13、电话问题中的通话时间等负指数分布负指数分布的一个重要性质是的一个重要性质是无记忆性无记忆性或或无后效性无后效性即即2)负指数分布负指数分布（记为（记为M）一个随机变量一个随机变量，它的分布密度函数为它的分布密度函数为其数学期望其数学期望方差方差篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统输入过程输入过程(5）3)最简流最简流 或称或称 Poisson流流(M)顾顾客客相相继继到到达达时时间间间间隔隔Xn为为独独立立的的,服服从从同同参参数数 的负指数分布的负指数分布其密度函数为其密度函数为（4）输入过程是平稳的或称对时间是齐次的）

14、输入过程是平稳的或称对时间是齐次的是是指指相相继继到到达达的的间间隔隔时时间间和和所所含含参参数数（如如期期望望值、方差等）都值、方差等）都与时间无关的与时间无关的，否则称为非平稳的否则称为非平稳的篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2、排队及排队规则、排队及排队规则排队分为有限排队和无限排队两类排队分为有限排队和无限排队两类：有限排队有限排队是指排队系统中的顾客数是有限的是指排队系统中的顾客数是有限的即系统的空间是有限的，当系统被占满时，即系统的空间是有限的，当系统被占满时，后面再来的顾客将不能进入系统；后面再来的顾客将

15、不能进入系统；无限排队无限排队是指系统中顾客数可以是无限的是指系统中顾客数可以是无限的队列可以排到无限长，顾客到达系统后队列可以排到无限长，顾客到达系统后均可进入系统排队或接受服务。均可进入系统排队或接受服务。这类系统又称为等待制排队系统这类系统又称为等待制排队系统 对有限排队系统，可进一步分为两种：对有限排队系统，可进一步分为两种：(a)损失制排队系统损失制排队系统(b)混合制排队系统混合制排队系统篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2、排队及排队规则、排队及排队规则(2)(a)损失制排队系统损失制排队系统这种系统是指排

16、队空间为零的系统这种系统是指排队空间为零的系统实际上是不允许排队。实际上是不允许排队。当顾客到达系统时，如果所有服务台均被占用，则自当顾客到达系统时，如果所有服务台均被占用，则自动离去，并不再回来，称这部分顾客被损失掉了。动离去，并不再回来，称这部分顾客被损失掉了。例如某些电话系统即可看作损失制排队系统。例如某些电话系统即可看作损失制排队系统。(b)混合制排队系统混合制排队系统该系统是等待制和损失制系统的结合该系统是等待制和损失制系统的结合一般是指允许排队，但又不允许队列无限长下去一般是指允许排队，但又不允许队列无限长下去具体说来，大致有三种：具体说来，大致有三种：篮球比赛是根据运动队在规定的

17、比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统队长有限：队长有限：即系统的等待空间是有限的。即系统的等待空间是有限的。例如最多只能容纳例如最多只能容纳K个顾客在系统中，当新顾客到达时，个顾客在系统中，当新顾客到达时，若系统中的顾客数（又称为队长）小于若系统中的顾客数（又称为队长）小于K，则可进入系统，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。如水库的库容是有限的，旅馆的床位是有限的。等待时间有限：等待时间有限：即即顾顾客客在在系系统统中中的的等等待待时时间间

18、不不超超过过某某一一给给定定的的长长度度T，当当等等待待时时间间超超过过T时时，顾顾客客将将自自动动离离去去，并不再回来。并不再回来。如如易易损损坏坏的的电电子子元元器器件件的的库库存存问问题题，超超过过一一定定存存储时间的元器件被自动认为失效。储时间的元器件被自动认为失效。2、排队及排队规则、排队及排队规则(3)篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2、排队及排队规则、排队及排队规则(4)逗留时间有限：逗留时间有限：不难注意到，损失制和等待制可看成是混合制的特殊情形不难注意到，损失制和等待制可看成是混合制的特殊情形等待时间

19、与服务时间之和有限等待时间与服务时间之和有限例如例如用高射炮射击敌机，当敌机飞越高射炮射击用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为有效区域的时间为t时，若在这个时间内未被击落，时，若在这个时间内未被击落，也就不可能再被击落了也就不可能再被击落了。如记如记s为系统中服务台的个数，则当为系统中服务台的个数，则当K=s时，混合制时，混合制即成为损失制；当即成为损失制；当K=时，即成为等待制。时，即成为等待制。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2、排队及排队规则、排队及排队规则(5)(2)排队规则排队规则服务台对顾

20、客进行服务所遵循的规则通常有：服务台对顾客进行服务所遵循的规则通常有：当顾客到达时，若所有服务台都被占用且又允当顾客到达时，若所有服务台都被占用且又允许排队，则该顾客将进入队列等待。许排队，则该顾客将进入队列等待。先来先服务先来先服务(FCFS)规则规则即按顾客到达的先后对顾客进行服务，这是最普遍的情况即按顾客到达的先后对顾客进行服务，这是最普遍的情况后来先服务后来先服务(LCFS)规则规则在许多库存系统中会出现这种情形，如钢板存入仓库后，在许多库存系统中会出现这种情形，如钢板存入仓库后，需要时总是从最上面的权出；又如情报系统中，后来到达需要时总是从最上面的权出；又如情报系统中，后来到达的信息

21、往往更加重要，应首先加以分析和利用。的信息往往更加重要，应首先加以分析和利用。具有优先权的服务具有优先权的服务(PS)规则规则服务台根据顾客的优先权进行服务，优先权高的先接受服务。服务台根据顾客的优先权进行服务，优先权高的先接受服务。如病危的患者应优先治疗，加急的电报电话应优先处理等。如病危的患者应优先治疗，加急的电报电话应优先处理等。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3、服务机制的描述、服务机制的描述(1)排队系统的排队系统的服务机制主要包括：服务机制主要包括：3服务机制服务机制服务员的数量及其连接形式（串联或并联）服

22、务员的数量及其连接形式（串联或并联）顾客是单个还是成批接受服务顾客是单个还是成批接受服务服务时间的分布服务时间的分布在这些因素中，服务时间的分布更为重要一些在这些因素中，服务时间的分布更为重要一些记某服务台的服务时间为记某服务台的服务时间为V其分布函数为其分布函数为B(t)，密度函数为，密度函数为b(t)则常见的分布有则常见的分布有：(1)定长分布定长分布(D)每个顾客接受服务的时间是一个确定的常数每个顾客接受服务的时间是一个确定的常数(2)负指数分布负指数分布(M)每个顾客接受服务的时间相互独立，具有每个顾客接受服务的时间相互独立，具有相同的负指数分布：相同的负指数分布：其中其中0为一常数为

23、一常数 篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3、服务机制的描述、服务机制的描述(2)(3)K阶爱尔朗分布阶爱尔朗分布(EK)每每个个顾顾客客接接受受服服务务的的时时间间服服从从 k阶阶爱尔朗分布，其密度函数为爱尔朗分布，其密度函数为其中其中0，为，为一常数一常数爱尔朗分布比负指数分布具有更多的适应性爱尔朗分布比负指数分布具有更多的适应性当当k=1时，爱尔朗分布即为负指数分布；时，爱尔朗分布即为负指数分布；当当k增加时，爱尔朗分布逐渐变为对称的增加时，爱尔朗分布逐渐变为对称的事实上，当事实上，当k30以后，爱尔朗分布近似于正

24、态分布。以后，爱尔朗分布近似于正态分布。当当k时，由方差为时，由方差为1/k2 2可知，方差将趋于零，即可知，方差将趋于零，即为完全非随机的。为完全非随机的。所以，所以，K阶爱尔朗分布可看成完全随机（阶爱尔朗分布可看成完全随机（K=1）与完全）与完全非随机之间的分布，能更广泛地适应于现实世界。非随机之间的分布，能更广泛地适应于现实世界。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统三、排队系统的符号表示和模型分类三、排队系统的符号表示和模型分类可根据输入过程、排队规则和服务机制的变化可根据输入过程、排队规则和服务机制的变化对排队模型

25、进行对排队模型进行描述或分类：描述或分类：D.G.Kendall提出一种目前在排队论中被广泛采用的提出一种目前在排队论中被广泛采用的“Kendall记记号号”A表示系统的容量，即可容纳的最多顾客数表示系统的容量，即可容纳的最多顾客数其一般形式为：其一般形式为：XYZABC其中其中X表示顾客相继到达时间间隔的分布；表示顾客相继到达时间间隔的分布；Y表示服务时间的分布；表示服务时间的分布；B表示顾客源的数目表示顾客源的数目Z表示服务台的个数；表示服务台的个数；C表示服务规则表示服务规则例如，例如，MM1FCFS表示了一个顾客的到达时间间隔服从相同的负指数分布、服务表示了一个顾客的到达时间间隔服从相

26、同的负指数分布、服务时间为负指数分布、单个服务台、系统容量为无限（等待制）、时间为负指数分布、单个服务台、系统容量为无限（等待制）、顾客源无限、排队规则为先来先服务的排队模型。顾客源无限、排队规则为先来先服务的排队模型。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统三、排队系统的符号表示三、排队系统的符号表示(2)在排队论中，一般约定如下：在排队论中，一般约定如下：如果如果 Kendall记号中略去后记号中略去后 3项时项时例如例如：MM1 FCFS表示为表示为MM1的排队模型的排队模型 MMsK则表示了则表示了一个顾客相继到时间间

27、隔服从相一个顾客相继到时间间隔服从相同的负指数分布、服务时间为负指数分布、同的负指数分布、服务时间为负指数分布、s个服务台、系统容量为个服务台、系统容量为K、顾客源无限、顾客源无限、先来先服务的排队模型。先来先服务的排队模型。是指是指XYZ FCFS的情形的情形GIM1则表示则表示一个单服务台、服务时间为负指数分一个单服务台、服务时间为负指数分布、顾客相继到达时间间隔为独立同分布的布、顾客相继到达时间间隔为独立同分布的等待制排队模型，等待制排队模型，篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统四四.排队系统的主要数量指标和记号排队

28、系统的主要数量指标和记号1队长和排队长队长和排队长 队长队长 是指系统中的顾客数（排队等待的顾客数与正在是指系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和），它的期望值记为接受服务的顾客数之和），它的期望值记为LS排队长：排队长：是指系统中正在排队等待服务的顾客数。它的期是指系统中正在排队等待服务的顾客数。它的期望值记为望值记为Lq队长和排队长一般都是随机变量队长和排队长一般都是随机变量对这两个指标进行研究时，当然是希望能确定它们的分对这两个指标进行研究时，当然是希望能确定它们的分布，或至少能确定它们的平均值（即平均队长和平均排布，或至少能确定它们的平均值（即平均队长和平均排队长）

29、及有关的矩（如方差等）。队长）及有关的矩（如方差等）。队长的分布队长的分布是顾客和服务员都关心的，特别是对系统设是顾客和服务员都关心的，特别是对系统设计人员来说，如果能知道队长的分布，就能确定队长超计人员来说，如果能知道队长的分布，就能确定队长超过某个数的概率，从而确定合理的等待空间。过某个数的概率，从而确定合理的等待空间。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统四四.排队系统的主要数量指标和记号排队系统的主要数量指标和记号(2)2等待时间和逗留时间等待时间和逗留时间等待时间：等待时间：是从顾客到达时刻起到他开始接受服务止这是

30、从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，段时间称为等待时间，它的期望值记为它的期望值记为Wq也是顾客最关心的指标，因为顾客通常是希望等也是顾客最关心的指标，因为顾客通常是希望等待时间越短越好。待时间越短越好。逗留时间：逗留时间：是从顾客到达时刻起到他接受服务完成止这段是从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间时间称为逗留时间它的期望值记为它的期望值记为WS对这两个指标的研究当然是希望能确定它们的分布对这两个指标的研究当然是希望能确定它们的分布或或至少能知道顾客的平均等待时间和平均逗留时间至少能知道顾客的平均等待时间和平均逗留时间逗留时间等待时间服务时间逗留时间等待

31、时间服务时间篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统四四.排队系统的主要数量指标和记号排队系统的主要数量指标和记号(3)3忙期和闲期忙期和闲期忙期：忙期：这是个随机变量这是个随机变量是服务员最为关心的指标，因为它关系到服务员的服务强度。是服务员最为关心的指标，因为它关系到服务员的服务强度。是是指指从从顾顾客客到到达达空空闲闲着着的的服服务务机机构构起起，到到服服务务机机构再次成为空闲止的这段时间构再次成为空闲止的这段时间即即服务机构连续忙的时间服务机构连续忙的时间闲期：闲期：服务机构连续保持空闲的时间服务机构连续保持空闲的时间

32、在排队系统中，忙期和闲期总是交替出现的。在排队系统中，忙期和闲期总是交替出现的。除了上述几个基本数量指标外，还会用到其它一些重要的指标除了上述几个基本数量指标外，还会用到其它一些重要的指标如在损失制或系统容量有限的情况下，由于顾客被如在损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的拒绝，而使服务系统受到损失的顾客损失率顾客损失率及及服务服务强度强度等，也都是十分重要的数量指标。等，也都是十分重要的数量指标。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统四四.排队系统的主要数量指标和记号排队系统的主要数量指标和记

33、号(4)下面给出上述下面给出上述一些主要数量指标的常用记号一些主要数量指标的常用记号：当当部部分分排排队队系系统统在在运运行行了了一一定定时时间间后后，都都会会趋趋于于一一个个平衡状态（或称平衡状态（或称平稳状态平稳状态）。）。在在平平衡衡状状态态下下，队队长长的的分分布布、等等待待时时间间的的分分布布和和忙忙期期的的分分布布都都和和系统所处的时刻无关，而且系统的初始状态的影响也会消失。系统所处的时刻无关，而且系统的初始状态的影响也会消失。因因此此，我我们们在在本本章章中中将将主主要要讨讨论论与与系系统统所所处处时时刻刻无无关关的的性性质质，即统计平衡性质。即统计平衡性质。系系统统的的状状态态

34、即即指指系系统统中中顾顾客客数数，如如果果系系统统中中有有n个个顾顾客客就就说说系系统的状态是统的状态是n。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统四四.排队系统的主要数量指标和记号排队系统的主要数量指标和记号(5)记记Pn(t)为时刻为时刻t时系统处于状态时系统处于状态n的概率，即的概率，即系统的瞬时分布系统的瞬时分布N：系统处于平稳状态时的队长：系统处于平稳状态时的队长,其其均值为均值为LS,称为平均队长称为平均队长n n：当系统处于状态当系统处于状态n时，新来顾客的时，新来顾客的平均到达率平均到达率T：系统处于平稳状态时

35、顾客的逗留时间，其均值记为系统处于平稳状态时顾客的逗留时间，其均值记为WS，称为平均逗留时间；称为平均逗留时间；Tq：系统处于平稳状态时顾客的等待时间，：系统处于平稳状态时顾客的等待时间，其均值记为其均值记为Wq，称为平均等待时间；称为平均等待时间；Nq:系统处于平稳状态时的排队长，其系统处于平稳状态时的排队长，其均值为均值为Lq,称为平均排队长称为平均排队长根据前面的约定，我们将主要分析系统的平稳分布，根据前面的约定，我们将主要分析系统的平稳分布，当系统达到统计平衡时处于状态当系统达到统计平衡时处于状态n的概率，记为的概率，记为Pn单位时间内来到系统的平均顾客数单位时间内来到系统的平均顾客数

36、篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统四四.排队系统的主要数量指标和记号排队系统的主要数量指标和记号(6)n n：当系统处于状态：当系统处于状态n时，时，整个系统平均服务率整个系统平均服务率单位时间内可以服务完的顾客数单位时间内可以服务完的顾客数当当每每个个服服务务台台的的平平均均服服务务率率为为常常数数时时，记记每每个个服服务台的服务率为务台的服务率为因此，因此，顾客相继到达的平均时间间隔为顾客相继到达的平均时间间隔为 1/平均服务平均服务时间为时间为 1/篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，

37、篮球比赛的计时计分系统是一种得分类型的系统例例2（p308)某服务机构是单服务台，先到先服务，对某服务机构是单服务台，先到先服务，对41个顾客记录到达时刻个顾客记录到达时刻T和服务时间和服务时间S，第，第1号顾客到达时刻为号顾客到达时刻为0，全部服务时间为，全部服务时间为127分钟分钟(1)顾客编号顾客编号i(2)到达时刻到达时刻Ti(3)服务时间服务时间Si(4)到达间隔到达间隔ti(5)排队等待时排队等待时间间Wi(1)(2)(3)(4)(5)i Ti Si ti wi 1 0 5 2 0 2 2 7 4 3 3 6 1 5 6 4 11 9 1 2 5 12 2 7 10 6 19 4

38、3 5 7 22 3 4 6 8 26 3 10 5 9 36 1 2 010 38 2 7 0(1)(2)(3)(4)(5)i Ti Si ti wi 11 45 5 2 0 12 47 4 2 3 13 49 1 3 5 14 52 2 9 3 15 61 1 1 0 16 62 2 3 0 17 65 1 5 0 18 70 3 2 0 19 72 4 8 1 20 80 3 1 0ti=Ti+1-TiWi+1=Wi+Si-ti篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统五、排队论研究的基本问题五、排队论研究的基本问题排队论

39、研究的首要问题是排队系统主要数量指标的概率规律排队论研究的首要问题是排队系统主要数量指标的概率规律即研究系统的整体性质，然后进一步研究系统的优化问题即研究系统的整体性质，然后进一步研究系统的优化问题与这两个问题相关的还包括排队系统的统计推断与这两个问题相关的还包括排队系统的统计推断(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及通过研究主要数量指标在瞬时或平稳状态下的概率分布及 其数字特征，了解其数字特征，了解系统运行的基本特征系统运行的基本特征。（2）统计推断问题统计推断问题，建立适当的排队模型是排队论研究的，建立适当的排队模型是排队论研究的 第一步，建立模型过程中经常会碰到如下问题

40、：检验第一步，建立模型过程中经常会碰到如下问题：检验 系统是否达到平稳状态；检验顾客相继到达时间间隔的系统是否达到平稳状态；检验顾客相继到达时间间隔的 相互独立性；确定服务时间的分布及有关参数等。相互独立性；确定服务时间的分布及有关参数等。（3）系统优化问题系统优化问题，又称为系统控制问题或系统运营问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。其基本目的是使系统处于最优或最合理的状态。系系统统优优化化问问题题包包括括最最优优设设计计问问题题和和最最优优运运营营问问题题，其其内内容容很很多多，有有最最少少费费用用问问题题、服服务务率率的的控控制制问问题题、服服

41、务务台台的的开开关关策策略略、顾顾客（或服务）根据优先权的最优排序等方面的问题客（或服务）根据优先权的最优排序等方面的问题篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第二节第二节 生灭过程和生灭过程和Poisson过程过程一、生灭过程简介一、生灭过程简介如果用如果用“生生”表示顾客的表示顾客的到达到达，“灭灭”表示顾客的表示顾客的离去离去，则对许多排队过程来说，则对许多排队过程来说，N(t)，t0 也是一类特殊的也是一类特殊的 随机过程随机过程生灭过程生灭过程。在排队论中，如果在排队论中，如果N(t)表示表示时刻时刻t系统中的顾客

42、数系统中的顾客数，则则N(t)，t0就构成了就构成了一个随机过程一个随机过程定义定义1 设设N(t)，t0 是一个随机过程。若是一个随机过程。若N(t)的概率分布具的概率分布具 有有以下性质：以下性质：(1)设设N(t)=n,则从时刻则从时刻t起到下一个顾客到达时刻止的时间起到下一个顾客到达时刻止的时间 服从参数为服从参数为n n的的负指数分布负指数分布，n=0,1,2,(2)假设假设 N(t)=n，则从时刻，则从时刻 t起下一个顾客离去时刻止的起下一个顾客离去时刻止的 时间服从参数为时间服从参数为n n的负指数分布，的负指数分布，n=0,1,2,(3)同一时刻只有一个顾客到达或离去。同一时刻

43、只有一个顾客到达或离去。则则称称N（t），），t0为一个为一个生灭过程生灭过程。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统一、生灭过程定义一、生灭过程定义(2)一一般般说说来来，得得到到N(t)的的分分布布Pn(t)=PN(t)=n（n=0,1,2,)是是比比较较困困难难的的，因因此此通通常常是是求求当当系系统统达达到到平平稳稳状状态态后后的的状状态态分分布布，记记为为 pn，n=0,1,2,为求平稳分布，考虑系统可能处的任一状态为求平稳分布，考虑系统可能处的任一状态n假设记录了一段时间内系统进入状态假设记录了一段时间内系统进入

44、状态n和离开状态和离开状态n的次数，的次数，则则因为因为“进入进入”和和“离开离开”是交替发生的是交替发生的，所以这所以这两个数要么相等，要么相差为两个数要么相等，要么相差为1。但就这两种事件的平均发生率来说，但就这两种事件的平均发生率来说，可以认为是相等的可以认为是相等的即即当系统运行相当时间而达到平稳状态后，对任一状态当系统运行相当时间而达到平稳状态后，对任一状态n来说，来说，单位时间内进入该状态的平均次数和单位时间内离开该状态的单位时间内进入该状态的平均次数和单位时间内离开该状态的平均次数应该相等平均次数应该相等这就是系统在统计平衡下的这就是系统在统计平衡下的“流入流入=流出流出”原理。

45、原理。根据这一原理，可得到任一状态下的平衡方程如下：根据这一原理，可得到任一状态下的平衡方程如下：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统一、生灭过程简介一、生灭过程简介(3)根据在统计平衡下的根据在统计平衡下的“流入流入=流出流出”原理，得原理，得n=0,1,2,由上述平衡方程得：由上述平衡方程得：记记由概率分布由概率分布篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统二、二、Poisson 过程和指数分布过程和指数分布 Poisson 过程过程又称为又称为Pois

46、son流，最简流流，最简流是排队论中经常用到的一种用来描述顾客到达规律的特殊随机过程是排队论中经常用到的一种用来描述顾客到达规律的特殊随机过程与概率论中的与概率论中的Poisson分布和负指数分布有密切的联系分布和负指数分布有密切的联系 定义：定义：设设N(t)为时间为时间0，t内到达系统的顾客数，内到达系统的顾客数，如果满足下面三个条件：如果满足下面三个条件：(2)独立性独立性：任意两个不相交的区间内顾客到达情况：任意两个不相交的区间内顾客到达情况 相互独立相互独立(无后效性）无后效性）(1)平稳性：平稳性：在在t,t+t内有一个顾客到达的内有一个顾客到达的 概率为概率为 t+(t)(3)普

47、通性普通性：在：在t,t+t内多于一个顾客到达的内多于一个顾客到达的 概率为概率为(t)则称则称N(t)，t0为为Poisson过程过程篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统二、二、Poisson 过程和指数分布（过程和指数分布（2）Poisson过程与过程与Poisson分布的关系：分布的关系：定理定理1：设：设N(t)为时间为时间0，t内到达系统的顾客数内到达系统的顾客数即表明到达的顾客数的分布恰为即表明到达的顾客数的分布恰为Poisson分布分布n=1,2,3,.则则N(t)，t0为为Poisson过程的过程的充要条件

48、是：充要条件是：定理定理2：设设N(t)为时间为时间0，t内到达系统的顾客数内到达系统的顾客数则则N(t)，t0为为Poisson过程的充要条件是：过程的充要条件是：相继到达时间间隔服从相互独立的参数为相继到达时间间隔服从相互独立的参数为 的负指数分布的负指数分布篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第三节第三节 单服务台负指数分布排队系统单服务台负指数分布排队系统一、标准的一、标准的M/M/1模型模型(1)顾客的相继到达时间间隔服从参数为顾客的相继到达时间间隔服从参数为的负指数的负指数分布，顾客单个到达，相互独立；分布，顾

49、客单个到达，相互独立；(2)服务台数为服务台数为1；(3)服务时间服务时间V服从参数为服从参数为的负指数分布，服务时的负指数分布，服务时间相互独立；间相互独立；(4)系统空间无限；系统空间无限；(5)单队，队长无限制，即允许永远排队；单队，队长无限制，即允许永远排队；(6)先到先服务；先到先服务；M/M/1/是指是指:为了分析此模型，先为了分析此模型，先求出系统在任意时刻的状态求出系统在任意时刻的状态n（系统中有（系统中有n个顾客）的概率个顾客）的概率Pn(t)，Pn(t)决定了系统运行的特征决定了系统运行的特征篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计

50、分系统是一种得分类型的系统一、一、单服务台单服务台M/M/1/模型模型(2)因为因为顾客的到达间隔时间服从参数为顾客的到达间隔时间服从参数为的负指数分布的负指数分布服务时间服务时间V服从参数为服从参数为的负指数分布，的负指数分布，故故t，t+t)时间内分为：时间内分为：(1)有一个顾客到达的概率为有一个顾客到达的概率为t t(t)t);没有顾客到达的概率就是没有顾客到达的概率就是1 t(t);在时刻在时刻t+t 有有n个顾客存在下列四种情况（到达或离去是个顾客存在下列四种情况（到达或离去是2个以上忽略掉）：个以上忽略掉）：(2)当当有顾客在接受服务时，有顾客在接受服务时，1个顾客被服务完离去的