Lecture排队论

《Lecture排队论》由会员分享，可在线阅读，更多相关《Lecture排队论（63页珍藏版）》请在装配图网上搜索。

1、随机服务系统理论 排队论及其应用排队论及其应用排队论排队论l排队系统描述l基本概念基本概念lM/M/1模型模型lM/M/S 模型第一节 排队系统描述l顾客要求服务的对象统称为“顾客”l服务台把提供服务的人或机构称 为“服务台”或“服务员”l一些排队系统的例子一些排队系统的例子排队系统排队系统顾顾客客服务台服务台服服务务电话系统电话系统电话呼叫电话呼叫电话总机电话总机 接通呼叫或取消呼叫接通呼叫或取消呼叫售票系统售票系统购票旅客购票旅客售票窗口售票窗口 收款、售票收款、售票设备维修设备维修出故障的设备出故障的设备修理工修理工排除设备故障排除设备故障防空系统防空系统进入阵地的敌机进入阵地的敌机高射

2、炮高射炮瞄准、射击，敌机被击落或离开瞄准、射击，敌机被击落或离开l排队的过程可表示为：排队的过程可表示为：排队排队服务机构服务服务机构服务服务后顾客离去服务后顾客离去排队系统排队系统顾客到达顾客到达各种形式的排队系统 随机服务系统排队论所要研究解决的问题 l 面对拥挤现象，人们通常的做法是增加服务设施，但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。如如何何做做到到既既保保证证一一定定的的服服务务质质量量指指标标，又又使使服服务务设设施施费费用用经经济济合合理理，恰当地解决顾客排队时间与服务设施费用大小这对

3、矛盾，就是随机服务系统理论排队论所要研究解决的问题。第二节 基本概念 一、排队系统的描述 二、排队系统的主要数量指标一、排队系统的描述l(一)系统特征和基本排队过程l(二)排队系统的基本组成部分l（三)排队系统的描述符号(一)系统特征和基本排队过程l相似的特征及数学抽象相似的特征及数学抽象：(1)请求服务的人或者物顾客；(2)有为顾客服务的人或者物，即服务员或服务台；(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。l基本排队过程基本排队过程 可以用图 6表示。从图 6可知，每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服

4、务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。(二)排队系统的基本组成部分 排队系统由排队系统由3 3个部分组成个部分组成 1、输入过程 2、服务规则 3、服务台1输入过程 这这是是指指要要求求服服务务的的顾顾客客是是按按怎怎样样的的规规律律到到达达排排队队系系统统的的过过程程，有有时时也也把把它它称称为为顾顾客客流流。一一般般可可以以从从3 3个个方方面来描述一个输入过程。面来描述一个输入过程。(1)(1)顾顾客客总总体体数数，又又称称顾顾客客源源、输输入入源源。这这是是指指顾顾客客的的来源。顾客源可以是有限的，也可以是无限的。来源。顾客源可以是有限的，也可以是无

5、限的。(2)(2)顾顾客客到到达达方方式式。这这是是描描述述顾顾客客是是怎怎样样来来到到系系统统的的，是单个到达，还是成批到达。是单个到达，还是成批到达。(3)(3)顾顾客客流流的的概概率率分分布布，或或称称相相继继顾顾客客到到达达的的时时间间间间隔隔的的分分布布。这这是是求求解解排排队队系系统统有有关关运运行行指指标标问问题题时时，首首先先需需要要确确定定的的指指标标。顾顾客客流流的的概概率率分分布布一一般般有有定定长长分分布布、二二项项分分布布、泊泊松松流流(最最简简单单流流)、爱爱尔尔朗朗分分布布等等若若干种。干种。2服务规则 这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失

6、制、等待制和混合制等3大类。(1)(1)损失制损失制。这是指如果顾客到达排队系统时，所有服务台都被先到的顾客占用，那么他们就自动离开系统永不再来。(2)(2)等待制等待制 这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。等待制中，服务台在选择顾客进行服务时常有如下四种规则：1)先到先服务。按顾客到达的先后顺序对顾客进行服务。2)后到先服务。3)随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客接受服务。4)优先权服务。(3)(3)混混合合制制 这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：1)队长有限。当

7、排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。2)等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。3)逗留时间(等待时间与服务时间之和)有限。3服务台l(1)(1)服服务务台台数数量量及及构构成成形形式式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：单队单服务台式；单队-多服务台并联式;多队多服务台并联式；单队多服务台串联式；单队多服务台并串联混合式，以及多队多服务台并串联混合式等等。l(2)(2)服服务务方方式式。这是指在某一时刻接受服务的顾客数，它有单个

8、服务和成批服务两种。l(3)(3)服服务务时时间间的的分分布布。在多数情况下，对每一个顾客的服务时间是一随机变量。1、泊松分布（泊松分布（Poisson）也称为泊松流，在排队论中常称为最简单流也称为泊松流，在排队论中常称为最简单流。概率分布概率分布：其中，其中，其中，其中，00为一常数，为一常数，为一常数，为一常数，t0t0。求求求求N(t)N(t)的数学期望得的数学期望得的数学期望得的数学期望得:则则=EN(t)/t。因因此此，表表示示单单位位时时间间内内到到达达系统的平均顾客数系统的平均顾客数,又称平均到达率又称平均到达率。附：排队系统中常见的几种典型理论分布附：排队系统中常见的几种典型理

9、论分布最简单流的最简单流的4个基本性质：个基本性质：平平稳稳性性：在在时时间间段段t内内，恰恰有有n个个顾顾客客到到达达系系统统的的概概率率PN(t)=n仅仅与与t的的长长短短有有关关,而与该时间段的起始时刻无关；而与该时间段的起始时刻无关；无无后后效效性性：在在不不相相交交的的时时间间区区间间内内到到达达的顾客数是相互独立的。的顾客数是相互独立的。如如：在在a，a+t时时段段内内到到达达K个个顾顾客客的的概概率与时刻率与时刻a之前到达多少顾客无关；之前到达多少顾客无关；普普通通性性：在在充充分分小小的的间间隔隔时时间间内内至至少少到到达达两个顾客的概率两个顾客的概率(t)=o(t),t0,即

10、即 有有限限性性：在在任任意意有有限限的的时时间间区区间间内内，到到达达有限个顾客的概率为有限个顾客的概率为1，即，即泊松流在排队论中的意义：泊松流在排队论中的意义：实际问题中最常见；实际问题中最常见；数字处理简单；数字处理简单；当实际流与泊松流有较大出入时，经过当实际流与泊松流有较大出入时，经过一定的变换，结果也可达到一定的精度；一定的变换，结果也可达到一定的精度；数学期望和方差：数学期望和方差：定定理理顾顾客客到到达达服服从从参参数数为为的的泊泊松松分分布布等等价价于于顾顾客客相相继继到到达达的的间间隔隔时时间间是是独独立立的的且且同同为负指数分布。为负指数分布。参参数数0表表示示单单位位

11、时时间间内内完完成成服服务务的的顾顾客客平平均数均数,称为称为平均服务率平均服务率。2、负指数分布负指数分布密度函数和分布函数密度函数和分布函数：3、爱尔朗分布爱尔朗分布当当顾顾客客在在系系统统内内所所接接受受的的服服务务可可以以分分为为K个个阶阶段段，每每个个阶阶段段的的服服务务时时间间T1，T2，Tk为为服服从从同同一一分分布布（参参数数为为k的的负负指指数数分分布布）的的k个个相相互互独独立立的的随随机机变变量量，顾顾客客在在完完成成全全部部服服务务内内容容并并离离开开系系统统后后，另另一一个个顾顾客客才才能能进进入入服服务务系系统统，则则顾顾客客在在系系统统内内接接受受服服务务时时间间

12、之之和和T=T1+T2+Tk服服从从k阶阶爱爱尔朗分布尔朗分布Ek，其分布密度函数为：其分布密度函数为：相应的数学期望和方差为：相应的数学期望和方差为：当当k=1时时，爱爱尔尔朗朗分分布布归归结结为为负负指指数数分分布布，当当k增增大大时时，图图形形逐逐渐渐变变为为对对称称的的，当当k30时时，近近似似于于正正态态分分布布，当当k，由由D(T)=0可可知知,爱爱尔尔朗朗分分布布归归结结为为定定长长分分布布(顾顾客客接接受受服服务务的的时间是一个确定的常数时间是一个确定的常数)。因因此此，爱爱尔尔朗朗分分布布类类可可以以看看成成完完全全随随机机（k=1）与与完完全全确确定定(k=)的的中中间间型

13、型，能能对对现实问题提供更广泛的模型类。现实问题提供更广泛的模型类。k=k=k=k=3 3 3 3k=2k=2k=1k=1（三)排队系统的符号表述描述符号描述符号：/各符号的意各符号的意义义：表示顾客相继到达间隔时间分布，常用下列符号：M表示到达的过程为泊松过程或负指数分布；D表示定长输入；EK表示K阶爱尔朗分布；G表示一般相互独立的随机分布。表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。表示服务台(员)个数：“1”表示单个服务台，“s”(s1)表示多个服务台。表示系统中顾客容量限额，或称等待空间容量。如系统有K个等待位子，则，0K1)个服务台；系统等待空间容量无限(等待制)；顾客

14、源无限，采用先到先服务规则。某些情况下，排队问题仅用上述表达形式中的前3个符号。例如，某排队问题为MMS，如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统。常用常用符号表示符号表示排队论模型的记号是排队论模型的记号是2020世纪世纪5050年代初由年代初由D.G.Kendall(D.G.Kendall(肯肯达尔达尔)引入的，通常由引入的，通常由3 35 5个英文字母组成，其形式为个英文字母组成，其形式为其中其中A表示输入过程，表示输入过程，B表示服务时间，表示服务时间，C表示服务台数目，表示服务台数目，n表示系统空间数。例如表示系统空间数。例如:(1)M

15、/M/S/表示输入过程是表示输入过程是Poisson流流,服务时间服从负服务时间服从负(2)指数分布指数分布,系统有系统有S个服务台平行服务个服务台平行服务,系统容量为无系统容量为无穷的穷的(3)等待制排队系统等待制排队系统.(2)M/G/1/表示输入过程是表示输入过程是Poisson流，顾客所需的服务流，顾客所需的服务时间为独立、服从一般概率分布，系统中只有一个服务时间为独立、服从一般概率分布，系统中只有一个服务台，容量为无穷的等待制系统台，容量为无穷的等待制系统.(3)GI/M/1/表示输入过程为顾客独立到达且相继到达的间表示输入过程为顾客独立到达且相继到达的间(4)隔时间服从一船概率分布

16、，服务时间是相互独立、服从隔时间服从一船概率分布，服务时间是相互独立、服从负指负指(5)数分布，系统中只有一个服务台，容量为无穷的等待制数分布，系统中只有一个服务台，容量为无穷的等待制系统系统符号表示（续）符号表示（续）(4)Ek/G/1/K表示相继到达的间隔时间独立、服从表示相继到达的间隔时间独立、服从k阶阶Erlang分布，服务时间为独立、服从一般概率分布，系统中只有一分布，服务时间为独立、服从一般概率分布，系统中只有一个服务台，容量为个服务台，容量为K的混合制系统的混合制系统.(5)D/M/S/K表示相继到达的间隔时间独立、服从定长分布、表示相继到达的间隔时间独立、服从定长分布、服务时间

17、相互独立、服从负指数分布，系统中有服务时间相互独立、服从负指数分布，系统中有S个服务台个服务台平行服务，容量为平行服务，容量为K的混合制系统的混合制系统.描述排队系统的主要数量指标描述排队系统的主要数量指标队长与等待队长队长与等待队长队长队长(通常记为通常记为LS)是指在系统中的顾客的平均数是指在系统中的顾客的平均数(包包括正在接受服务的顾客括正在接受服务的顾客),而等待队长而等待队长(通常记为通常记为Lq)是是指系统中排队等待的顾客的平均数，它们是顾客和服指系统中排队等待的顾客的平均数，它们是顾客和服务机构双方都十分关心的数量指标。显然队长等于等务机构双方都十分关心的数量指标。显然队长等于等

18、待队长加上正在被服务的顾客数待队长加上正在被服务的顾客数.顾客的平均等待时间与平均逗留时间顾客的平均等待时间与平均逗留时间顾客的平均等待时间顾客的平均等待时间(通常记为通常记为W Wq q)是指从顾客进入系是指从顾客进入系统的时刻起直到开始接受服务止的平均时间。平均逗统的时刻起直到开始接受服务止的平均时间。平均逗留时间留时间(通常记为通常记为W Ws s)是指顾客在系统中的平均等待时是指顾客在系统中的平均等待时间与平均服务时间之和。平均等待时间与平均服务时间与平均服务时间之和。平均等待时间与平均服务时间是顾客最关心的数量指标间是顾客最关心的数量指标.系统的忙期与闲期系统的忙期与闲期从顾客到达空

19、闲的系统，服务立即开始，直到系统再从顾客到达空闲的系统，服务立即开始，直到系统再次变为空闲，这段时间是系统连续繁忙的时间，我们称次变为空闲，这段时间是系统连续繁忙的时间，我们称为系统的忙期，它反映了系统中服务机构的工作强度，为系统的忙期，它反映了系统中服务机构的工作强度，是衡量服务机构利用效率的指标，即是衡量服务机构利用效率的指标，即与忙期对应的是系统的闲期，即系统连续保持空闲的时与忙期对应的是系统的闲期，即系统连续保持空闲的时间长度间长度.服务机构服务机构工作强度工作强度用于服务顾客的时间用于服务顾客的时间服务设施总的服务时间服务设施总的服务时间（四）（四）描述排队系统的主要数量指标描述排队

20、系统的主要数量指标数量指标的常用记号数量指标的常用记号L平均队长，即稳态系统任一时刻的所有顾客数的期望值；Lq平均等待队长，即稳态系统任一时刻等待服务的顾客数的期望值；W平均逗留时间，即(在任意时刻)进入稳态系统的顾客逗留时间的期望值；Wq平均等待时间，即(在任意时刻)进入稳态系统的顾客等待时间的期望值。（三）（三）描述排队系统的主要数量指标描述排队系统的主要数量指标其他常用数量指标其他常用数量指标 s系统中并联服务台的数目；平均到达率；1平均到达间隔；平均服务率；1/平均服务时间；N 稳态系统任一时刻的状态（即系统中所有顾客数）；U 任一顾客在稳态系统中的逗留时间；Q 任一顾客在稳态系统中的

21、等待时间；Little（利特尔）公式（利特尔）公式用用表示单位时间内顾客到达表示单位时间内顾客到达的平均数的平均数,表示单位时间内表示单位时间内被服务完毕离去的平均顾客数，被服务完毕离去的平均顾客数，因此因此1/表示相邻两顾客到表示相邻两顾客到达的平均时间，达的平均时间，1/表示对每个顾客的平均服务时间表示对每个顾客的平均服务时间.J.D.C.Little给出了如下公式给出了如下公式：排队系统运行情况的分析 排队系统运行情况的分析，就是在给定输入与服务条件下，通过求解系统状态为n(有n个顾客)的概率Pn，再进行计算其主要的运行指标：系统中顾客数(队长)的期望值L；排队等待的顾客数(排队长)的期

22、望值Lq；顾客在系统中全部时间(逗留时间)的期望值W；顾客排队等待时间的期望值Wq。第三节第三节 M MM M1 1模型模型模型的条件是：1、输入过程顾客源是无限的，顾客到达完全是随机的，单个到来，到达过程服从普阿松分布，且是平稳的；2、排队规则单队，且队长没有限制，先到先服务；3、服务机构单服务台，服务时间的长短是随机的，服从相同的指数分布。对于对于M MM M1 1模型有如下公式：模型有如下公式：例例1 某某医医院院急急诊诊室室同同时时只只能能诊诊治治一一个个病病人人，诊诊治治时时间间服服从从指指数数分分布布，每每个个病病人人平平均均需需要要1515分分钟钟。病病人人按按泊泊松松分分布布到

23、到达达，平平均均每每小小时时到到达达3 3人人。试试对此排队队系统进行分析。对此排队队系统进行分析。解解 对此排队队系统分析如下：对此排队队系统分析如下：（1 1）先确定参数值先确定参数值：这是单服务台系统，有：这是单服务台系统，有：故服务强度为：故服务强度为：（2）计算稳态概率计算稳态概率：这就是急诊室空闲的概率，也是病人不这就是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。必等待立即就能就诊的概率。而病人需要等待的概率则为：而病人需要等待的概率则为：这这也是急也是急诊诊室繁忙的概率。室繁忙的概率。（3）计算系统主要工作指标计算系统主要工作指标：急诊室内外的病人平均数：急诊室内外的病

24、人平均数：急急诊诊室外排室外排队队等待的病人平均数：等待的病人平均数：病人在急病人在急诊诊室内外平均逗留室内外平均逗留时间时间：病人平均等候病人平均等候时间时间：（4）为使病人平均逗留时间不超过半为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？小时，那么平均服务时间应减少多少？由于由于代入代入=3=3，解得解得55，平均服平均服务时间务时间为为：151512123min3min即平均服即平均服务时间务时间至少至少应应减少减少3min3min(5)(5)若医院希望候诊的病人若医院希望候诊的病人90%90%以上都能有以上都能有座位座位,则候诊室至少应安置多少座位则候诊室至少应安置多少

25、座位?设应该设应该安置安置个座位个座位,加上急加上急诊诊室的一个室的一个座位座位,共有共有+1+1个。要使个。要使90%90%以上的候以上的候诊诊病病人有座位，相当于使人有座位，相当于使“来来诊诊的病人数不多于的病人数不多于+1+1个个”的概率不少于的概率不少于90%90%，即，即两两边边取取对对数数（x x2 2）lglg lg0.1lg0.1因因 1 1，故故所以所以 66即候诊室至少应安置即候诊室至少应安置6 6个座位。个座位。第四节第四节M/M/S模型模型l此模型与M/M/1模型不同之处在于有S个服务台，各服务台的工作相互独立，服务率相等，如果顾客到达时，S个服务台都忙着，则排成一队等

26、待，先到先服务的单队模型。l整个系统的平均服务率为s，*/s，（*0Q0）0.750.750 02020L Lq q2.252.25人人0 01212人人L L3 3人人0 08787人人W W60min60min17174min4minW Wq q45min45min2 24min4min例例3某医院挂号室有三个窗口，就诊者的到某医院挂号室有三个窗口，就诊者的到达服从泊松分布，平均到达率为每分钟达服从泊松分布，平均到达率为每分钟0.9人，挂人，挂号员服务时间服从指数分布，平均服务率每分钟号员服务时间服从指数分布，平均服务率每分钟0.4人，现假设就诊者到达后排成一队，依次向空人，现假设就诊者到

27、达后排成一队，依次向空闲的窗口挂号，显然系统的容量和顾客源是不限闲的窗口挂号，显然系统的容量和顾客源是不限的，属于的，属于M/M/1M/M/1型的排队服务模型。求：该系统型的排队服务模型。求：该系统的运行指标的运行指标解解 如果在例如果在例3 3中，就诊者到达后在每个挂中，就诊者到达后在每个挂号窗口各自排成一队，即排成号窗口各自排成一队，即排成3 3队，且进入队，且进入队列后不离开，各列间也互不串换，这就队列后不离开，各列间也互不串换，这就形成形成3 3个队列，而例个队列，而例3 3中的其它条件不变。中的其它条件不变。假设每个队列平均到达率相等且为：假设每个队列平均到达率相等且为：1 12 2

28、3 30.9/30.9/30.30.3（人人/分钟）分钟）这样，原来的这样，原来的M/M/3M/M/3系统就变成了系统就变成了3 3个个M/M/1M/M/1型的子系统。型的子系统。现按现按M/M/1M/M/1型计算主要运行指标，并与型计算主要运行指标，并与上面的例子进行对比分析，结果见表上面的例子进行对比分析，结果见表6 62 2 表表2 2 两个模型的比较两个模型的比较指标指标（1 1）M/M/3M/M/3型型（2 2）M/M/1M/M/1型型挂号间空闲挂号间空闲的概率的概率0.07480.07480.250.25（各子系统）（各子系统）就诊者必须等待就诊者必须等待的概率的概率P(N3)=0

29、.57P(N3)=0.570.750.75平均队列长平均队列长1.71.7（人）（人）2.252.25（人）（人）（各子系统）（各子系统）平均队长平均队长3.953.95（人）（人）9 9（人）（人）（整个系统）（整个系统）平均逗留时间平均逗留时间4.394.39（分钟）（分钟）1010（分钟）（分钟）平均等待时间平均等待时间1.891.89（分钟）（分钟）7.57.5（分钟）（分钟）练练 习习 1思考题（1）排队论主要研究的问题是什么？（2）试述排队系统的基本组成部分。（3）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念。（4）试述队长和排队长、等待时间和逗留时间、忙期和闲

30、期等概念。练练 习习 2设有一个医院门诊，只有一个值班医生。病人的到达过程为泊松流，平均到达时间间隔为20min，诊断时间服从负指数分布，平均需12min，求：(1)病人到来不用等待的概率；(2)门诊部内顾客的平均数；(3)病人在门诊部的平均逗留时间；(4)若病人在门诊部内的平均逗留时间超过1h，则院方将考虑增加值班医生。问病人平均到达率为多少时，医院才会增加医生?练练 习习 3某售票处有3个售票口，顾客的到达服从泊松分布，平均每分钟到达=09人，3个窗口售票的时间都服从负指数分布，平均每分钟卖给=0.4人，设可以归纳为MM3模型，试求：(1)整个售票处空闲的概率；(2)平均队长；(3)平均逗留时间；(4)平均等待时间；(5)顾客到达后的等待概率。