三2010暑期培训排队论

1、董 珺排队论排队论（ Queuing theory）排队论排队论一、概率论及随机过程回顾n随机变量随机变量离散型随机变量n概率分布和概率分布图概率分布和概率分布图n数学期望和方差数学期望和方差n常见离散型随机变量的概率分布常见离散型随机变量的概率分布A二点分布二点分布?A二项式分布二项式分布?APoisson分布分布?1.1、随机变量与概率分布一、概率论及随机过程复习n随机变量随机变量离散型随机变量n概率分布和概率分布图概率分布和概率分布图n数学期望和方差数学期望和方差n常见离散型随机变量的概率分布常见离散型随机变量的概率分布A二点分布二点分布?A二项式分布二项式分布?APoisson分布分布

2、?一、随机变量与概率分布pXPpXP1)0(,) 1(), 1 , 0( ,)(nkqpCkXPknkkn)(,)(0;, 1 ,0!)(XDXEkekkXPkn随机变量随机变量连续型随机变量连续型随机变量n概率密度函数概率密度函数n概率分布函数概率分布函数n数学期望和方差数学期望和方差n常见连续型随机变量的概率分布常见连续型随机变量的概率分布A均匀分布均匀分布A指数分布？指数分布？A正态正态分布？分布？Ak阶爱尔朗分布？阶爱尔朗分布？一、随机变量与概率分布2/1)(,/1)()0(0,00,)(XDXExxexax 随机变量随机变量X X为时间间隔，如顾客到达的为时间间隔，如顾客到达的时间间

3、隔、电话呼叫的时间、产品的寿命等。时间间隔、电话呼叫的时间、产品的寿命等。密度函数密度函数),()(,)()0,( ,21)(222)(22NXXDXERRxexax 随机变量随机变量X X为时间为时间( (长度），如产品的尺寸、长度），如产品的尺寸、重量、测量误差等。重量、测量误差等。密度函数密度函数? 爱尔朗分布211)(,1)(0,)!1()()(kTDTEtekktktbktkkkXXX,21k 为为k k个相互独立的随机变量；个相互独立的随机变量；服从相同参数服从相同参数 的负指数分布；的负指数分布；kXXXT21设设 ，则，则T T的密度函数为的密度函数为 如如k k个服务台串联（

4、个服务台串联（k k个服务阶段），个服务阶段），一个顾客接受一个顾客接受k k个服务共需的服务时间个服务共需的服务时间T T，T T 爱尔朗分布。爱尔朗分布。若顾客连续接受串联的若顾客连续接受串联的k k个服务台的服个服务台的服务，各服务台的服务时间相互独立，务，各服务台的服务时间相互独立，且均服从负指数分布，则且均服从负指数分布，则顾客接受顾客接受k k个服务共需的服务时间个服务共需的服务时间T T k k阶阶爱尔朗爱尔朗分布。分布。1.2 随机过程的有关概念n随机过程随机过程(Random process)的定义的定义),(TttX 设设 ，是一族随机变量，是一族随机变量，T T是一个实数

5、集，对是一个实数集，对 是一个是一个随机变量，则称随机变量，则称 为随机过程。为随机过程。)(,tXTt),(TttXTt T T：参数集合参数集合 当当T=0,1,n,T=0,1,n,时，称为随机序列时，称为随机序列 ：随机过程的一个状态：随机过程的一个状态 状态空间状态空间E=X(t)E=X(t)全体可能取值，全体可能取值， ktX)(n随机过程的基本类型随机过程的基本类型二阶矩过程二阶矩过程平稳过程平稳过程平稳独立增量过程平稳独立增量过程常见随机过程常见随机过程A马尔可夫过程？马尔可夫过程？APoisson过程？过程？A生灭过程？生灭过程？1.2 随机过程的有关概念n定义： 若满足如下性

6、质： 对任意非负整数 ，只要就有 则称 具有马尔可夫性，马尔可夫性，或或无后效性。无后效性。马尔可夫过程 马尔可夫链离散离散,.2 , 1 , 0),(nnXttttr.21)()()(,.,)(,)()(2211rrrritXjtXPitXitXitXjtXP0)(,.,)(,)(2211rritXitXitXP)(nX1t2trt1rtt过去过去现在现在 将来将来 “ “将来将来”的情况与的情况与“过去过去”无关，无关，只是通过只是通过“现在现在”与与“过去过去”发生联系，若发生联系，若“现在现在”已知，已知，“将来将来”与与“过去过去”无关。无关。)(nXn时齐的马氏链时齐的马氏链：马氏

7、链 若满足： 则称 为时齐马尔可夫链时齐马尔可夫链)(mPiXjXPijnmn,.2 , 1 , 0),(nnX,.2 , 1 , 0),(nnX)(mPij 系统由状态系统由状态i i经过经过m m 个时间间隔个时间间隔（或或m m 步）转移到状态步）转移到状态j j 的的转移概率转移概率n其中其中PoissonPoisson过程过程是应用最为广泛的是应用最为广泛的一类随机过程，常用来描述派对系一类随机过程，常用来描述派对系统中顾客到达的过程、城市中的交统中顾客到达的过程、城市中的交通事故、保险公司的理赔次数等。通事故、保险公司的理赔次数等。Poisson过程n定义：设 为时间 内到达系统的

8、顾客数，若满足下面三个条件：n独立性：在任意两个不相交的区间内顾客到 达的情况相互独立；n平稳性：在 内有一个顾客到达的 概率为n普通性：在 内多于一个顾客到达 的率为 。则称 为Poisson过程。且N(t)服从Poisson分布。)(tNt ,00),(ttNttt , );( tt)( tttt , （1 1）只与区间长度与）只与区间长度与 起点无关。起点无关。（2 2）单位时间内一个）单位时间内一个 顾客到达的概率顾客到达的概率 为为 。Poisson过程与过程与Poisson分布分布定理定理1 1：设：设 为时间为时间 内到达系统的顾客数内到达系统的顾客数 则则 为为PoissonP

9、oisson过程的充要条件是过程的充要条件是)(tNt ,00),(ttN,.2 , 1!)()(nentntNPtn数理统计方法数理统计方法容易初步判断容易初步判断: :期望期望= =方差方差ttNDttNE)(,)(Poisson过程与负指数分布过程与负指数分布tTPsTstTP定理定理2 2：设：设 为时间为时间 内到达系统的顾客数内到达系统的顾客数 则则 为参数为为参数为 的的PoissonPoisson过程的过程的 充要条件是相继到达的时间间隔充要条件是相继到达的时间间隔T T服从相互服从相互 独立的参数为独立的参数为 的负指数分布。的负指数分布。)(tNt ,00),(ttN0,

10、00,)(ttetatT负指数分布的性质负指数分布的性质: 2/1)(,/1tNDTE马尔可夫马尔可夫性，性，或或无无后效性后效性对于对于PoissonPoisson流：流： 单位时间平均到达的顾客数单位时间平均到达的顾客数 顾客相继到达的平均间隔时间顾客相继到达的平均间隔时间/1n定义：定义：设设 为一个随机过程，若为一个随机过程，若N(t)N(t)的概率分布具有以下性质：的概率分布具有以下性质： (1) (1)假设假设N(t)=nN(t)=n，则从时刻到下一个顾客则从时刻到下一个顾客到达到达时刻止的时间服从参数为时刻止的时间服从参数为 的负指数分布；的负指数分布； (2) (2)假设假设N

11、(t)=nN(t)=n，则从时刻到下一个顾客则从时刻到下一个顾客离开离开时刻止的时间服从参数为时刻止的时间服从参数为 的负指数分布；的负指数分布； (3) (3)同一时刻是只有一个同一时刻是只有一个 顾客到达或离去。顾客到达或离去。 则称则称 为一个为一个生灭过程生灭过程。 0),(ttN0),(ttNnn生灭生灭过程过程1 10 001nn-1n+11nnn1n平稳生灭过程系统状态平稳生灭过程系统状态n n平衡方程：平衡方程：“流入流入= =流出流出”nnnnnnnppppp)(011111100系统达到平稳状态时：系统达到平稳状态时：.)2 , 1 , 0(),(ntppnn)(tN的分布

12、的分布.)2 , 1 , 0(,)()(nntNPtpn系统达到平稳状态时：系统达到平稳状态时：100110210111.,.2 , 1,nnnnnnnnnnnCppCnpCp其中其中nnnnnnnppppp)(011111100平衡方程：平衡方程： 当当 时才有意义时才有意义1nnC.)2 , 1 , 0(,)()(nntNPtppnn现实生活中的排队模型现实生活中的排队模型 Bank Airport Hospital Road Manufacturing Hotel Restaurant WC 运筹学运筹学排队模型排队模型二、排队论的基本知识什么是排队论什么是排队论什么是排队论什么是排队论

13、排队系统的描述排队系统的描述n涉及的要素涉及的要素n顾客顾客n队列队列n服务台服务台n到达间隔时间到达间隔时间n服务时间服务时间n排队规则排队规则运筹学运筹学排队模型排队模型排队系统的描述排队系统的描述n绩效测度绩效测度n等待顾客数等待顾客数n顾客等待时间顾客等待时间n服务台忙期服务台忙期n服务台闲期服务台闲期n服务台利用率服务台利用率运筹学运筹学排队模型排队模型排队模型存在的问题排队模型存在的问题n如何以最经济的方式控制排队如何以最经济的方式控制排队系统，使其达到特定的要求？系统，使其达到特定的要求？n提供过多的服务能力来控制排提供过多的服务能力来控制排队系统将会造成过量的成本队系统将会造成

14、过量的成本n提供的服务能力不足将会导致提供的服务能力不足将会导致过多的等待，降低顾客满意度过多的等待，降低顾客满意度并造成顾客流失，减少收益并造成顾客流失，减少收益顾客源顾客源2.1、排队排队模型模型排队系统排队系统排队排队结构结构服务服务机构机构排队规则服务规则服务规则接受接受服务服务后离去后离去（A BAsic Queuing system） 下图下图 就是排队过程的一般模型就是排队过程的一般模型 。n各个顾客由顾客源（总体）出发，到达服务机构（服务台、各个顾客由顾客源（总体）出发，到达服务机构（服务台、服务员）前排队等侯接受服务，服务完了后就离开。服务员）前排队等侯接受服务，服务完了后就

15、离开。n排队结构指队列的数目和排列方式，排队规则和服务规则排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。是说明顾客在排队系统中按怎样的规则、次序接受服务的。n我们所说的排队系统就指图中虚线所包括的部分。我们所说的排队系统就指图中虚线所包括的部分。n 在现实中的排队现象是多种多样的在现实中的排队现象是多种多样的n在现实中的排队现象是多种多样的，对上在现实中的排队现象是多种多样的，对上面所说的面所说的“顾客顾客”和和“服务员服务员”，要作广，要作广泛地理解，它现可以是人，也可以是非生泛地理解，它现可以是人，也可以是非生物；物；n队列可以是具体

16、地排列，也可以是无形的队列可以是具体地排列，也可以是无形的（例如向电话交换台要求通话的呼唤）；（例如向电话交换台要求通话的呼唤）；n顾客可以走向服务机构，也可以相反（如顾客可以走向服务机构，也可以相反（如送货上门）。送货上门）。n下面举一些例子说明实现中形形色色的排下面举一些例子说明实现中形形色色的排队系统队系统 到达的顾客到达的顾客要求服务内容要求服务内容服务机构服务机构1 1不能运转的机器不能运转的机器2 2修理技工修理技工3 3病人病人4 4电话呼唤电话呼唤5 5文件稿文件稿6 6提货单提货单7 7到达机场上空的飞机到达机场上空的飞机8 8驶入港口的货船驶入港口的货船9 9上游河水进入水

17、库上游河水进入水库1010进入我方阵地的敌机进入我方阵地的敌机修理修理领取修配零件领取修配零件诊断或动手术诊断或动手术通话通话打字打字提取存货提取存货降落降落装（卸）货装（卸）货放水，调整水位放水，调整水位我方高射炮进行射击我方高射炮进行射击修理技工修理技工发放修配零件的管理员发放修配零件的管理员医生（或包括手术台）医生（或包括手术台）交换台交换台打字员打字员仓为管理员仓为管理员跑道跑道装（卸）货码头装（卸）货码头( (泊位泊位) )水闸管理员水闸管理员我方高射炮我方高射炮服务服务机构机构服务服务台台( (a) a) 一个一个队列、单服务队列、单服务台台（阶段阶段）服务台服务台1服务台服务台2

18、( (b) b) 一个一个队列、队列、s s个服务阶段个服务阶段服务服务机构机构服务台服务台1服务台服务台2服务服务机构机构( (c c) ) 一个一个队列、队列、s s个服务台个服务台 一个服务阶段一个服务阶段服务台服务台3服务台服务台4服务台服务台1服务台服务台2服务服务机构机构( (d d) ) s s个个队列、队列、s s个服务阶段个服务阶段服务台服务台3服务台服务台4服务台服务台1服务台服务台2: 124: 243: 3214服务服务机构机构( (e e) )混合混合型型排队排队结构结构服务服务台台( (f f) ) 一个一个队列队列服务服务台台( (g g) ) s s个个队列队列

19、排队系统的组成和特征排队系统的组成和特征n一般的排队系统都有三个基本组成部一般的排队系统都有三个基本组成部分分n1.输入过程；输入过程；n2.排队规则；排队规则；n3.服务机构。服务机构。n 现在分别说明各部分的特征：现在分别说明各部分的特征：n（1）输入过程：输入即指顾客到达排队系统。）输入过程：输入即指顾客到达排队系统。可能有下列各种不同情况，当然这些情况并不可能有下列各种不同情况，当然这些情况并不是彼此排斥的。是彼此排斥的。n（a）顾客的总体（称为顾客源）的组成可能）顾客的总体（称为顾客源）的组成可能是有限的，也可能是无限的。工厂内停机待修是有限的，也可能是无限的。工厂内停机待修的机器显

20、然是有限的总体。的机器显然是有限的总体。n（b）顾客到来的方式可能是一个一个的，也）顾客到来的方式可能是一个一个的，也可能是成批的。例如到餐厅就餐就有单个到来可能是成批的。例如到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客，我们的顾客和受邀请来参加宴会的成批顾客，我们将只研究单个至来的情形。将只研究单个至来的情形。 n（c）顾客相继到达的间隔时间可以是确定型的，也）顾客相继到达的间隔时间可以是确定型的，也可以是随机型的。可以是随机型的。n如在自动装配线上装配的各部件就必须按确定的时如在自动装配线上装配的各部件就必须按确定的时间间隔到达装配点，定期运行的班车、班轮、班机间间隔到达装配点

21、，定期运行的班车、班轮、班机的到达也都是确定型的。的到达也都是确定型的。n但一般到商店购物的顾客、到医院诊病的病人、通但一般到商店购物的顾客、到医院诊病的病人、通过路口的车辆等，它们的到达都是随机型的。过路口的车辆等，它们的到达都是随机型的。n对于随机型的情形，要知道单位时间内的顾客到达对于随机型的情形，要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布（下图）数或相继到达的间隔时间的概率分布（下图）顾客到达时间ti-1titi+1输入过程输入过程n(d)顾客的到达可以是相互独立的。顾客的到达可以是相互独立的。n就是说，以前的到达情况对以后顾客的就是说，以前的到达情况对以后顾客的到来没

22、有影响，否则不是有关联的。到来没有影响，否则不是有关联的。n例如，工厂内的机器在一个短的时间内例如，工厂内的机器在一个短的时间内出现停机（顾客到达）的概率就受已经出现停机（顾客到达）的概率就受已经待修或被修理的机器数目的影响。待修或被修理的机器数目的影响。n我们主要讨论的是相互独立的情形。我们主要讨论的是相互独立的情形。输入过程输入过程n（e）输入过程可以是平衡的，或称对）输入过程可以是平衡的，或称对时间是齐次的，是指描述相继到达间隔时间是齐次的，是指描述相继到达间隔时间分布和所含参数（如期望值、方差时间分布和所含参数（如期望值、方差等）都是与时间无关的，否则称为非平等）都是与时间无关的，否则

23、称为非平衡的，非平稳情形的数学处理是很困难衡的，非平稳情形的数学处理是很困难的。的。n顾客到达时间间隔的分布顾客到达时间间隔的分布:：第：第n n个顾客与第个顾客与第n-1n-1个顾客到达的时间间隔；个顾客到达的时间间隔；nXnT：第：第n n个顾客到达的时刻；个顾客到达的时刻；设设nTTT100, 2 , 1,1nTTXnnn令令1T2TnT1nT1nT0TnXn顾客到达时间间隔的分布顾客到达时间间隔的分布:假定假定 是独立同分布，分布函数为是独立同分布，分布函数为 ，排队论中常用的有两种：排队论中常用的有两种：nX)(tAnX（2 2）最简流（即）最简流（即PoissonPoisson流）

24、（流）（M M）：）： 顾客到达时间间隔顾客到达时间间隔 为独立的，为独立的， 服从负指数分布，其密度函数为服从负指数分布，其密度函数为（1 1）定长分布（）定长分布（D D）：）：顾客到达时间间隔为确定的。顾客到达时间间隔为确定的。000)(ttetat因为负指数分布因为负指数分布具有无后效性具有无后效性（即（即Markov性）性）大多数排队模型假设到达间大多数排队模型假设到达间隔时间的概率分布形式是指隔时间的概率分布形式是指数分布数分布小间隔时间出现的可能性很小间隔时间出现的可能性很大，而大间隔时间出现的机大，而大间隔时间出现的机会则很小，这个间隔时间的会则很小，这个间隔时间的特征能在实践

25、中观察到特征能在实践中观察到负指数分布负指数分布n随机变量随机变量T的概率密度若是的概率密度若是n n则称则称T服从负指数分布，它的分布函数是服从负指数分布，它的分布函数是n n n数学期望数学期望ET= ,方差方差DT= ，n标准差标准差T= 。 0, 00,)(ttetftT0, 00,1)(ttetFtT1121 fT(t)t1)(TEn负指数分布有下列性质：负指数分布有下列性质：n（1）由条件概率公式容易证明）由条件概率公式容易证明n n这性质称为无记忆性或马尔柯夫性，若这性质称为无记忆性或马尔柯夫性，若T表示排队系统中顾客到达的间隔时间，表示排队系统中顾客到达的间隔时间，那么这个性质

26、说明一个顾客到来所需的那么这个性质说明一个顾客到来所需的时间与过去一个顾客到来所需时间时间与过去一个顾客到来所需时间s无关，无关，所以说这情形下的顾客到达是纯随机的。所以说这情形下的顾客到达是纯随机的。 tTPsTstTP|n（2）当输入过程是普阿松流时，那么顾）当输入过程是普阿松流时，那么顾客相继到达的间隔时间客相继到达的间隔时间T必服从负指数分必服从负指数分布。这时因为对于普阿松流，在布。这时因为对于普阿松流，在0,t)区区间内至少有间内至少有1个顾客到达的概率是：个顾客到达的概率是：n n而这概率又可表示为而这概率又可表示为n 0,1)(10tetPt)(tFtTPtn对于普阿松流，对于

27、普阿松流，表示单位时间平均到达表示单位时间平均到达的顾客数，所以的顾客数，所以1就表示相继顾客到就表示相继顾客到达平均间隔时间，而这正和达平均间隔时间，而这正和ET的意义的意义相符。相符。（2 2）排队规则）排队规则n（a）顾客到达时，如所有服务台都正被）顾客到达时，如所有服务台都正被占用，在这种情形下顾客可以随即离去，占用，在这种情形下顾客可以随即离去，也可以排队等侯。也可以排队等侯。n随即离去的称为即时制或称损失制，因为随即离去的称为即时制或称损失制，因为这将失掉许多顾客；这将失掉许多顾客；n排队等侯的称为等待制。排队等侯的称为等待制。n普通市内电话的呼唤属于前者，而登记市普通市内电话的呼

28、唤属于前者，而登记市外长途电话的呼唤属于后者。外长途电话的呼唤属于后者。 排队规则排队规则n对于对于等待制等待制，为顾客进行服务的次序可以采用下列，为顾客进行服务的次序可以采用下列各种规则：各种规则：n先到先服务，后到先服务，随机服务，有优先权的先到先服务，后到先服务，随机服务，有优先权的服务等。服务等。n先到先服务先到先服务(FCFS)，即按到达次序接受服务，这是，即按到达次序接受服务，这是通常的情形。通常的情形。n后到先服务后到先服务(LCFS)，如乘用电梯的顾客常是后人先，如乘用电梯的顾客常是后人先出的。仓库中存放的厚钢板也是如此。在情报系统出的。仓库中存放的厚钢板也是如此。在情报系统中

29、，最后到达的信息往往是最有价值的，因而常采中，最后到达的信息往往是最有价值的，因而常采用后到先服务（指被采用）的规则。用后到先服务（指被采用）的规则。排队规则排队规则n随机服务随机服务(SIRO) ，指服务员从等待的顾客中随机，指服务员从等待的顾客中随机地选取其一进行服务，而不管到达的先后，如电话地选取其一进行服务，而不管到达的先后，如电话交换台接通呼唤的电话就是如此。交换台接通呼唤的电话就是如此。n有优先权的服务有优先权的服务(PR) ，如医院对于病情严重的患者，如医院对于病情严重的患者将给予优先治疗。将给予优先治疗。n（b）从占有的空间来看，队列可以排在具体的处所）从占有的空间来看，队列可

30、以排在具体的处所（如售票处、候诊室等），也可以是抽象的（如向（如售票处、候诊室等），也可以是抽象的（如向电话交换台要求通话的呼唤）。电话交换台要求通话的呼唤）。n由于空间的限制或其它原因，有的系统要规定容量由于空间的限制或其它原因，有的系统要规定容量（即允许进入排队系统的顾客数）的最大限；有的（即允许进入排队系统的顾客数）的最大限；有的没有这种限制（即认为容量可以是无限的）。没有这种限制（即认为容量可以是无限的）。排队规则排队规则n（c）从队列的数目看，可以是单列，也）从队列的数目看，可以是单列，也可以是多列。可以是多列。n在多列的情形，各列间的顾客有的可以在多列的情形，各列间的顾客有的可以互

31、相转移，有的不能（如用绳子或栏杆互相转移，有的不能（如用绳子或栏杆隔开）。隔开）。n有的排队顾客因等候时间过长而中途退有的排队顾客因等候时间过长而中途退出，有的不能退出（如高速公路上的汽出，有的不能退出（如高速公路上的汽车流），必须坚持到被服务为止。车流），必须坚持到被服务为止。n我们将只讨论各列间不能互相转移、也我们将只讨论各列间不能互相转移、也不能中途退出的情形。不能中途退出的情形。3 3）服务机构）服务机构n从服务机构的形式和工作情况来看有以从服务机构的形式和工作情况来看有以下几种情况。下几种情况。n（a）服务机构可以没有服务员，也可以）服务机构可以没有服务员，也可以有一个或多个服务员（

32、服务台、通道、有一个或多个服务员（服务台、通道、窗口等）窗口等）.n例如，在敞架售书的书店，顾客选书时例如，在敞架售书的书店，顾客选书时就没有服务员，但交款时可能有多个服就没有服务员，但交款时可能有多个服务员。务员。服务机构服务机构n（b）在有多个服务台的情形中，它们可以是平行排列）在有多个服务台的情形中，它们可以是平行排列（并列）的，可以是前后排列（串列）的，也可以是混合（并列）的，可以是前后排列（串列）的，也可以是混合的。下图说明这些情形。的。下图说明这些情形。n图图a是单队是单队单服务台，图单服务台，图b是多队是多队多服务台，多服务台，图图c是单队是单队多服务台（并列）的情形，图多服务台

33、（并列）的情形，图d是多服务台（串是多服务台（串列）的情形，图列）的情形，图e是多服务台（混合）的情形。是多服务台（混合）的情形。112cc1212cabcd111e服务机构服务机构n(d) 服务方式可以对单个顾客进行，也可以对成服务方式可以对单个顾客进行，也可以对成批顾客进行，公共汽车对站台等候的顾客就成批批顾客进行，公共汽车对站台等候的顾客就成批进行服务，我们将只研究单个单个地服务方式。进行服务，我们将只研究单个单个地服务方式。n（e）和输入过程一样，服务时间也分确定型的）和输入过程一样，服务时间也分确定型的和随机型的。自动冲洗（服务）的时间就是确和随机型的。自动冲洗（服务）的时间就是确定

34、定 ，但大多数情形的服务时间是随机型的。对，但大多数情形的服务时间是随机型的。对于随机型的服务时间，需要知道它的概率分布。于随机型的服务时间，需要知道它的概率分布。n（f）和输入过程一样，服务时间的分布我们总）和输入过程一样，服务时间的分布我们总假定是平稳的，即分布的期望值、方差等参数都假定是平稳的，即分布的期望值、方差等参数都不受时间的影响。不受时间的影响。n服务时间分布服务时间分布: : 设某服务台的服务时间为设某服务台的服务时间为V V，其密度函数其密度函数为为b b（t t），），常见的分布有：常见的分布有：（1 1）定长分布（）定长分布（D D）：）：每个顾客接受服务的时间每个顾客接

35、受服务的时间 是一个确定的常数。是一个确定的常数。（2 2）负指数分布（）负指数分布（M M）：）：每个顾客接受服务时间每个顾客接受服务时间 相互独立，具有相互的负指数分布：相互独立，具有相互的负指数分布： 其中其中 ，为一常数。，为一常数。000)(ttetbt0- - 单位时间平均服务完成的顾客数单位时间平均服务完成的顾客数1/1/ - - 每个顾客的平均服务时间每个顾客的平均服务时间n服务时间分布服务时间分布:（3 3）k k阶爱尔朗（阶爱尔朗（ErlangErlang）分布：每个顾客接受服务分布：每个顾客接受服务 时间服从时间服从k k阶爱尔朗分布，其密度函数为：阶爱尔朗分布，其密度函

36、数为：tkkektkktb)!1()()(1 Erlang Distribution (爱尔朗分布) 服务时间的波动量介于指数分布和常量之间 有一个形状参数k决定其标准差erlAng DistriBution (爱尔朗分布)n例如串列的例如串列的k个服务台，每台服务时间相个服务台，每台服务时间相互独立，服从相同的负指数分布（参数互独立，服从相同的负指数分布（参数ku），那么一顾客走完），那么一顾客走完k个服务台总共个服务台总共所需要服务时间就服从上述的所需要服务时间就服从上述的k阶爱朗分阶爱朗分布布。n注意：爱尔朗分布族提供更为广泛的模注意：爱尔朗分布族提供更为广泛的模型类。比指数分布有更大的

37、适应性。事型类。比指数分布有更大的适应性。事实上，当实上，当k=1时，爱尔朗分布化为负指时，爱尔朗分布化为负指数分布，这可看成是完全随机时；当数分布，这可看成是完全随机时；当k增增大时，爱尔朗分布的图形逐渐变为对称大时，爱尔朗分布的图形逐渐变为对称为；当为；当k30时爱尔朗分布近似于正态分时爱尔朗分布近似于正态分布；布；k时；由看出时；由看出VarT0，因此，因此这时爱尔朗分布化为确定型分布这时爱尔朗分布化为确定型分布,所以一所以一般般k阶爱尔朗分布可看成完全随机与完全阶爱尔朗分布可看成完全随机与完全确定的中间型，能对现实世界提供更为确定的中间型，能对现实世界提供更为广泛的适应性。广泛的适应性

38、。排队系统的分类排队系统的分类nD.G.Kendall在在1953年提出一个分类方年提出一个分类方法，按照上述各部分的特征中最主要的、法，按照上述各部分的特征中最主要的、影响最大的三个，即影响最大的三个，即n1相继顾客到达间隔时间的分布；相继顾客到达间隔时间的分布；n2服务时间的分布；服务时间的分布；n3服务台个数。服务台个数。排队系统的分类排队系统的分类n按照这三个特征分类，并用一定符号表示，称按照这三个特征分类，并用一定符号表示，称为为Kendall记号。这只对并列的服务台（如果记号。这只对并列的服务台（如果服务台是多于一个的话）的情形，他用的符号服务台是多于一个的话）的情形，他用的符号形

39、式是：形式是：n X/Y/Zn其中其中X处填写表示相继到达间隔时间的分布，处填写表示相继到达间隔时间的分布，nY处填写表示服务时间的分布，处填写表示服务时间的分布，nZ处填写并列的服务台数目。处填写并列的服务台数目。排队系统的分类排队系统的分类n表示相继到达间隔时间和服务时间的各种分布表示相继到达间隔时间和服务时间的各种分布的符号是：的符号是：nM负指数分布（负指数分布（M是是Markov的字头，因的字头，因为负指数分布具有无记忆性，即为负指数分布具有无记忆性，即Markov性）性）nD确定定型（确定定型（Deterministic）nEkk阶爱尔朗阶爱尔朗(Erlang)分布分布nGI般相互

40、独立（般相互独立（General Independent）的时间间隔的分布的时间间隔的分布nG一般（一般（General）服务时间的分布）服务时间的分布排队系统的分类排队系统的分类n例如：例如：nMM1表示相继到达间隔时间为负指表示相继到达间隔时间为负指数分布、服务时间负指数分布、单服务数分布、服务时间负指数分布、单服务台的模型；台的模型；nDMc表示确定的到达间隔、服务时表示确定的到达间隔、服务时间为负指数分布、间为负指数分布、c个平行服务台（但顾个平行服务台（但顾客是一队）的模型。客是一队）的模型。 排队系统的分类排队系统的分类n以后，在以后，在1971年一次关于排队论符号标准化会年一次关

41、于排队论符号标准化会议上决定，将议上决定，将Kendall符号扩充成为：符号扩充成为：n XYZABCn形式，其中前三项意义不变，形式，其中前三项意义不变，n A处填写系统容量限制处填写系统容量限制N，n B处填写顾客源数目处填写顾客源数目m，n C处填写服务规则，如先到服务处填写服务规则，如先到服务FCFS，后到，后到先服务先服务LCFS 等。等。n并约定，如略去后三项，即指并约定，如略去后三项，即指XYZFCFS的情形。在本节中，因只讨论先到先的情形。在本节中，因只讨论先到先服务服务FCFS的情形，所以略去第六项。的情形，所以略去第六项。 例：例：M/M/s/KM/M/s/K表示？表示？M

42、/M/s/K表示相继到达间隔时表示相继到达间隔时间为负指数分布、服务时间负间为负指数分布、服务时间负指数分布、指数分布、s个服务台、系统容个服务台、系统容量为量为K的模型的模型例如例如 M / M / 1 / M / M / 1 / / / 表示顾客到达过程服从负指数分布，服务表示顾客到达过程服从负指数分布，服务时间服从负指数分布，一个服务台，排队的长时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。度无限制和顾客的来源无限制。其他模型其他模型nM/M/c/K/Kn顾客来源是有限的服务系统顾客来源是有限的服务系统. 例如：例如： 一个饭店有一个饭店有 X 张桌子张桌子和和 Y

43、个服务生服务来源有限的顾客个服务生服务来源有限的顾客.nM/D/1n服务时间不变的服务系统服务时间不变的服务系统.nD/M/1n确定性到达模式确定性到达模式, 及指数分布服务时间及指数分布服务时间. 例如：医生赴约治例如：医生赴约治病的时间表病的时间表.nM/E k/1n服务服从服务服从 Erlang 分布分布. 例如：用相同平均时间去完成一些例如：用相同平均时间去完成一些程序。程序。排队问题的求解排队问题的求解n一个实际问题作为排队问题求解时，首先要研一个实际问题作为排队问题求解时，首先要研究它属于哪个模型，其中只有顾客到达的间隔究它属于哪个模型，其中只有顾客到达的间隔时间分布和服务时间的分

44、布需要实测的数据来时间分布和服务时间的分布需要实测的数据来确定，其它因素都是在问题提出时给定的。解确定，其它因素都是在问题提出时给定的。解决排队问题首先要根据原始资料做出顾客到达决排队问题首先要根据原始资料做出顾客到达间隔和服务时间的经验分布，然后按照统计学间隔和服务时间的经验分布，然后按照统计学的方法（例如的方法（例如x x2检验法）以确定合于那种理论检验法）以确定合于那种理论分布，并估计它的参数值。分布，并估计它的参数值。解排队问题的目的解排队问题的目的n解排队问题的目的，是研究排队系统运解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参行的效率，估计服务质量，确定系统参

45、数的最优值，以决定系统结构是否合理、数的最优值，以决定系统结构是否合理、研究设计改进措施等。研究设计改进措施等。n所以必须确定用以判断系统运行优劣的所以必须确定用以判断系统运行优劣的基本数量指标，解排队问题就是首先求基本数量指标，解排队问题就是首先求出这些数量指标的概率分布或特征数。出这些数量指标的概率分布或特征数。 排队系统的指标排队系统的指标n这些指标通常是：这些指标通常是：n（1）队长，指在系统中的顾客数，它的期望）队长，指在系统中的顾客数，它的期望值记作值记作Ls；n 排队长（队列长，指在系统中排队等待服排队长（队列长，指在系统中排队等待服务的顾客数，它的期望值记作务的顾客数，它的期望

46、值记作Lq;n Ls = Lq + 正在接受服务的顾客数正在接受服务的顾客数n一般情形，一般情形，Ls（或（或Lq）越大，说明服务率越）越大，说明服务率越低，排队成龙，是顾客最厌烦的。低，排队成龙，是顾客最厌烦的。排队系统的指标排队系统的指标n（2）逗留时间，指一个顾客在系统中的）逗留时间，指一个顾客在系统中的停留时间，它的期望值记作停留时间，它的期望值记作Ws；n （3）等待时间，指一个顾客在系统）等待时间，指一个顾客在系统中排队等待的时间，它的期望值记作中排队等待的时间，它的期望值记作Wq，WS = Wq + 服务时间服务时间 排队系统的指标排队系统的指标n在机器故障问题中，无论是等待修理

47、或在机器故障问题中，无论是等待修理或正在修理都使工厂受到停工的损失，所正在修理都使工厂受到停工的损失，所以逗留时间（停工时间）是主要的；但以逗留时间（停工时间）是主要的；但一般购物、诊病等问题中仅仅等待时间一般购物、诊病等问题中仅仅等待时间常是顾客们所关心的。常是顾客们所关心的。 排队系统的指标排队系统的指标n此外，还有此外，还有忙期忙期(Busy Period)指从顾指从顾客到达空闲服务机构起到服务机构再次客到达空闲服务机构起到服务机构再次为空闲止这段时间长度，即服务机构连为空闲止这段时间长度，即服务机构连续繁忙的时间长度，它关系到服务员的续繁忙的时间长度，它关系到服务员的工作强度，忙期和一

48、个忙期中平均完成工作强度，忙期和一个忙期中平均完成服务顾客都是衡量服务机构效率的指标。服务顾客都是衡量服务机构效率的指标。排队系统的指标排队系统的指标n在即时制或排队有限缺点情形，还有由在即时制或排队有限缺点情形，还有由于顾客被拒绝而使企业受到损失的损失于顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等，这率以及以后经常遇到的服务强度等，这些都是很重要的指标。些都是很重要的指标。排队系统的状态排队系统的状态n计算这些指标的基础是表达系统状态的概率，计算这些指标的基础是表达系统状态的概率，所谓系统的状态即指系统中顾客数，如系统中所谓系统的状态即指系统中顾客数，如系统中有有n个顾客就

49、说系统的状态是个顾客就说系统的状态是n，它的可能值是，它的可能值是n（1）队长没有限制时，）队长没有限制时，n0，1，2n（2）队长有限制，最大数为）队长有限制，最大数为N时，时，n0，1，2，N,n（3）即时制，服务台个数是）即时制，服务台个数是c时，时，n=0，1，2，c。n后者，状态后者，状态n又表示正在工作（繁忙）的服务台又表示正在工作（繁忙）的服务台数。数。 排队系统的状态排队系统的状态n这些状态的概率一般是随时刻这些状态的概率一般是随时刻t 而变化，所以在时而变化，所以在时刻刻t、系统状态为、系统状态为n的概率用的概率用Pn（t）表示。）表示。n求状态概率求状态概率Pn(t)的方法

50、，首先要建立含的方法，首先要建立含Pn（t）的）的关系式关系式,因因t为是连续变量，而为是连续变量，而n只取非负整数，所以只取非负整数，所以建立的建立的Pn（t）的关系式一般是微分差分方程（关）的关系式一般是微分差分方程（关于于t微分瞬态解是不容易的，一般地，即使求出也很微分瞬态解是不容易的，一般地，即使求出也很难利用，因此我们常用它的极限（如果存在的话）难利用，因此我们常用它的极限（如果存在的话） n称称 为稳态（为稳态（Steady state），或称），或称统计平衡状态统计平衡状态(Statistical Equilibrium State)的的解。解。nntPtP)(lim排队系统的状

51、态排队系统的状态n稳态的物理含义是，当系统运行了无限长的时稳态的物理含义是，当系统运行了无限长的时间之后，初始间之后，初始(t=0)出发状态的概率分布出发状态的概率分布（Pn(0)，n0）的影响将消失，而且系统的）的影响将消失，而且系统的状态概率分布不再随时间变化。当然，在实际状态概率分布不再随时间变化。当然，在实际应用中大多数问题，系统会很快趋于稳态，而应用中大多数问题，系统会很快趋于稳态，而无需等到无需等到t以后。但永远达不到稳态的情以后。但永远达不到稳态的情形也确实是存在的。形也确实是存在的。n求稳态概率求稳态概率Pn时，并不一定求时，并不一定求t时时Pn（t）的极限，而只需令导数的极限

52、，而只需令导数P/ /n=0即可，我们以下即可，我们以下着重研究稳态的情形。着重研究稳态的情形。三三. .单服务台负指数分布单服务台负指数分布排队系统分析排队系统分析 3.1 3.1 M/M/1M/M/1模型模型即(M/M/1/M/M/1/);3.2 3.2 M/M/1/N/ M/M/1/N/ 模型模型( (即系统的容量有限即系统的容量有限) )3.3 3.3 M/M/1/ /m M/M/1/ /m 模型（即顾客源为有限）模型（即顾客源为有限）标准的标准的/M/MM M1 1模型（模型（M MM M1/1/）n标准的标准的M/M/1M/M/1模型，是指适合下列条件的排队模型，是指适合下列条件的

53、排队系统：系统：n （1 1）输入过程）输入过程顾客源是无限的，顾顾客源是无限的，顾客单个到来，相互独立，一定时间的到达数服客单个到来，相互独立，一定时间的到达数服从普阿松分布，到达过程已是平稳的。从普阿松分布，到达过程已是平稳的。n （2 2）排队规则）排队规则单队，且对队长没有单队，且对队长没有限制，先到先服务。限制，先到先服务。n （3 3）服务机构）服务机构单服务台，各顾客的单服务台，各顾客的服务时间是相互独立的服从相同的负指数分布。服务时间是相互独立的服从相同的负指数分布。顾客源顾客源排队系统排队系统排队排队结构结构服务服务机构机构排队规则服务规则服务规则接受接受服务服务后离去后离去

54、 3.1 3.1 M/M/1M/M/1模型模型无限无限输入过程服从输入过程服从参数为参数为 的的PoissonPoisson过程过程单队单队队长无限队长无限先到先服务先到先服务服务时间服从服务时间服从参数为参数为 的的负指数分布负指数分布n此外，还假定到达时间和服务时间是相此外，还假定到达时间和服务时间是相互独立的。互独立的。n在分析标准的在分析标准的MM1模型时，首先要模型时，首先要求出系统在任意时刻求出系统在任意时刻t的状态为的状态为n（系统（系统中有中有n个顾客）的概率个顾客）的概率Pn(t)，它决定了，它决定了系统运行的特征。系统运行的特征。 求解：求解：np: :系统达到平稳后，系统

55、有系统达到平稳后，系统有n n个顾客的概率。个顾客的概率。1n 0)(0n 01110nnnPPPPP平衡方程：平衡方程：1n )1(1 0nnPP1 :令，且当，且当时时01102101.,.2, 1,ppCnpCpnnnnnnnnn其中其中排队系统的生灭过程与状态转移方程排队系统的生灭过程与状态转移方程一、排队系统的生灭过程一、排队系统的生灭过程( (一一) )生灭过程的背景与定义生灭过程的背景与定义 设某系统具有状态集S=0,1,2,或S=0,1,2,k,N(t)表示系统在时刻 t (t=0) 的状态。 若在N(t)=n的条件下，随机过程N(t),t=0满足以下条件: (1) N(t+t

56、)转移到“n+1”的概率为n(t ) ; (2) N(t+t)转移到“n-1”的概率为n(t ) ; (3) N(t+t)转移到其他状态“S-n+1,n-1”的概 率为o(t )(高阶无穷小) ; 则称随机过程N(t),t=0为生灭过程。n ，n ， t ( ？)( (二二) )生灭过程状态变化的性质生灭过程状态变化的性质 (1) 在无穷小在无穷小 t内内,系统或生长系统或生长1个个;或灭亡或灭亡1个个;或既或既 不生长又不灭亡不生长又不灭亡（概率概率:1- n( t ) -n( t ) ）; (2)系统生长一个的概率系统生长一个的概率n( t )与与 t有关，而与有关，而与t无无 关关; 与

57、系统当前状态与系统当前状态n有关，而与以前的状态无关；有关，而与以前的状态无关； (3)系统灭亡一个的概率系统灭亡一个的概率n( t )与与 t有关，而与有关，而与t无无 关关; 与系统当前状态与系统当前状态n有关，而与以前的状态无关；有关，而与以前的状态无关；马尔可夫性质马尔可夫性质( (三三) ) 排队系统的生灭过程排队系统的生灭过程n顾客到达顾客到达“生生”；n顾客离开顾客离开“灭灭”顾客到达顾客到达顾客离去顾客离去n ， n ，(1)(1)生灭过程示意生灭过程示意 若排队系统具有下列性质若排队系统具有下列性质: (1) 顾客到达为泊松流，时间间隔服从参顾客到达为泊松流，时间间隔服从参

58、数为数为n的负指数分布的负指数分布; (2) 顾客服务时间服从参数为顾客服务时间服从参数为 n的负指的负指 数分布数分布; 则排队系统的随机过程则排队系统的随机过程N(t),t=0具有具有马马 尔可夫性质尔可夫性质, , 为为一个生灭过程一个生灭过程.(2)(2)生灭过程定义生灭过程定义二、排队系统的状态转移方程二、排队系统的状态转移方程( (一一) ) 排队系统状态的概率及其分布排队系统状态的概率及其分布 (1) (1)瞬态概率瞬态概率P Pn n(t)(t) 表示时刻系统状态表示时刻系统状态N(t)N(t)= =n n的概率的概率; ; (2) (2) 稳态概率稳态概率P Pn n P P

59、n n= = P Pn n(t)(t) ; ;limt 一般，稳态概率一般，稳态概率P Pn n的分布，是分析计算的分布，是分析计算排队系统运行优劣的基础。排队系统运行优劣的基础。( (二二) ) 排队系统状态概率的微分差分方程排队系统状态概率的微分差分方程00 01 1()()();0,0dP tP tPttndt1111()()() () ();0,0nnnnnnnndPtP tP tPttndt 推导过程见后面推导过程见后面求解可得瞬态概率求解可得瞬态概率P Pn n(t)(t) ( (三三) ) 排队系统状态转移方程排队系统状态转移方程求解可得稳态概率求解可得稳态概率P Pn n0 0

60、1 1()() 0P tPt1111()() () ();0nnnnnnnP tP tP tn 0()0;dP tdt()0ndPtdt令令则则排队系统状态转移方程排队系统状态转移方程( (四四) ) 排队系统状态转移图排队系统状态转移图在任意状态在任意状态n达到稳态平衡的条件：达到稳态平衡的条件： 产生该状态的平均速率产生该状态的平均速率 =该状态转变成其他状态的平均速率该状态转变成其他状态的平均速率 （流入（流入=流出）流出）0011pp1112200)(ppp2223311)(ppp11122)(nnnnnnnpppnnnnnnnppp)(1111三、三、 排队系统稳态概率排队系统稳态概