资源描述
随机服务系统理论,排队论及其应用,排队论,排队系统描述基本概念M/M/1模型M/M/S模型,第一节排队系统描述,顾客要求服务的对象统称为“顾客”服务台把提供服务的人或机构称为“服务台”或“服务员”,一些排队系统的例子排队系统顾客服务台服务电话系统电话呼叫电话总机接通呼叫或取消呼叫售票系统购票旅客售票窗口收款、售票设备维修出故障的设备修理工排除设备故障防空系统进入阵地的敌机高射炮瞄准、射击，敌机被击落或离开排队的过程可表示为：,排队,服务机构服务,服务后顾客离去,排队系统,顾客到达,各种形式的排队系统,随机服务系统,排队论所要研究解决的问题,面对拥挤现象，人们通常的做法是增加服务设施，但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，就是随机服务系统理论排队论所要研究解决的问题。,第二节基本概念,一、排队系统的描述二、排队系统的主要数量指标,一、排队系统的描述,(一)系统特征和基本排队过程(二)排队系统的基本组成部分（三)排队系统的描述符号,(一)系统特征和基本排队过程,相似的特征及数学抽象：(1)请求服务的人或者物顾客；(2)有为顾客服务的人或者物，即服务员或服务台；(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。,基本排队过程可以用图6表示。从图6可知，每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。,(二)排队系统的基本组成部分,排队系统由3个部分组成1、输入过程2、服务规则3、服务台,1输入过程,这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流。一般可以从3个方面来描述一个输入过程。(1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。(2)顾客到达方式。这是描述顾客是怎样来到系统的，是单个到达，还是成批到达。(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。,2服务规则,这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。(1)损失制。这是指如果顾客到达排队系统时，所有服务台都被先到的顾客占用，那么他们就自动离开系统永不再来。,(2)等待制这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。等待制中，服务台在选择顾客进行服务时常有如下四种规则：1)先到先服务。按顾客到达的先后顺序对顾客进行服务。2)后到先服务。3)随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客接受服务。4)优先权服务。,(3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：1)队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。2)等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。3)逗留时间(等待时间与服务时间之和)有限。,3服务台,(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：单队单服务台式；单队-多服务台并联式;多队多服务台并联式；单队多服务台串联式；单队多服务台并串联混合式，以及多队多服务台并串联混合式等等。(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。(3)服务时间的分布。在多数情况下，对每一个顾客的服务时间是一随机变量。,1、泊松分布（Poisson）也称为泊松流，在排队论中常称为最简单流。概率分布：,其中，0为一常数，t0。求N(t)的数学期望得:,则=EN(t)/t。因此，表示单位时间内到达系统的平均顾客数,又称平均到达率。,附：排队系统中常见的几种典型理论分布,最简单流的4个基本性质：平稳性：在时间段t内，恰有n个顾客到达系统的概率PN(t)=n仅与t的长短有关,而与该时间段的起始时刻无关；无后效性：在不相交的时间区间内到达的顾客数是相互独立的。如：在a，a+t时段内到达K个顾客的概率与时刻a之前到达多少顾客无关；,普通性：在充分小的间隔时间内至少到达两个顾客的概率(t)=o(t),t0,即,有限性：在任意有限的时间区间内，到达有限个顾客的概率为1，即,泊松流在排队论中的意义：实际问题中最常见；数字处理简单；当实际流与泊松流有较大出入时，经过一定的变换，结果也可达到一定的精度；,数学期望和方差：,定理顾客到达服从参数为的泊松分布等价于顾客相继到达的间隔时间是独立的且同为负指数分布。,参数0表示单位时间内完成服务的顾客平均数,称为平均服务率。,2、负指数分布密度函数和分布函数：,3、爱尔朗分布当顾客在系统内所接受的服务可以分为K个阶段，每个阶段的服务时间T1，T2，Tk为服从同一分布（参数为k的负指数分布）的k个相互独立的随机变量，顾客在完成全部服务内容并离开系统后，另一个顾客才能进入服务系统，则顾客在系统内接受服务时间之和T=T1+T2+Tk服从k阶爱尔朗分布Ek，其分布密度函数为：,相应的数学期望和方差为：,当k=1时，爱尔朗分布归结为负指数分布，当k增大时，图形逐渐变为对称的，当k30时，近似于正态分布，当k，由D(T)=0可知,爱尔朗分布归结为定长分布(顾客接受服务的时间是一个确定的常数)。,因此，爱尔朗分布类可以看成完全随机（k=1）与完全确定(k=)的中间型，能对现实问题提供更广泛的模型类。,（三)排队系统的符号表述,描述符号：/各符号的意义：表示顾客相继到达间隔时间分布，常用下列符号：M表示到达的过程为泊松过程或负指数分布；D表示定长输入；EK表示K阶爱尔朗分布；G表示一般相互独立的随机分布。,表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。表示服务台(员)个数：“1”表示单个服务台，“s”(s1)表示多个服务台。表示系统中顾客容量限额，或称等待空间容量。如系统有K个等待位子，则，0K1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。某些情况下，排队问题仅用上述表达形式中的前3个符号。例如，某排队问题为MMS，如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统。,常用符号表示,排队论模型的记号是20世纪50年代初由D.G.Kendall(肯达尔)引入的，通常由35个英文字母组成，其形式为,其中A表示输入过程，B表示服务时间，C表示服务台数目，n表示系统空间数。例如:,M/M/S/表示输入过程是Poisson流,服务时间服从负指数分布,系统有S个服务台平行服务,系统容量为无穷的等待制排队系统.,(2)M/G/1/表示输入过程是Poisson流，顾客所需的服务时间为独立、服从一般概率分布，系统中只有一个服务台，容量为无穷的等待制系统.,GI/M/1/表示输入过程为顾客独立到达且相继到达的间隔时间服从一船概率分布，服务时间是相互独立、服从负指数分布，系统中只有一个服务台，容量为无穷的等待制系统,符号表示（续）,(4)Ek/G/1/K表示相继到达的间隔时间独立、服从k阶Erlang分布，服务时间为独立、服从一般概率分布，系统中只有一个服务台，容量为K的混合制系统.,(5)D/M/S/K表示相继到达的间隔时间独立、服从定长分布、服务时间相互独立、服从负指数分布，系统中有S个服务台平行服务，容量为K的混合制系统.,描述排队系统的主要数量指标,队长与等待队长,队长(通常记为LS)是指在系统中的顾客的平均数(包括正在接受服务的顾客),而等待队长(通常记为Lq)是指系统中排队等待的顾客的平均数，它们是顾客和服务机构双方都十分关心的数量指标。显然队长等于等待队长加上正在被服务的顾客数.,顾客的平均等待时间与平均逗留时间,顾客的平均等待时间(通常记为Wq)是指从顾客进入系统的时刻起直到开始接受服务止的平均时间。平均逗留时间(通常记为Ws)是指顾客在系统中的平均等待时间与平均服务时间之和。平均等待时间与平均服务时间是顾客最关心的数量指标.,系统的忙期与闲期,从顾客到达空闲的系统，服务立即开始，直到系统再次变为空闲，这段时间是系统连续繁忙的时间，我们称为系统的忙期，它反映了系统中服务机构的工作强度，是衡量服务机构利用效率的指标，即,与忙期对应的是系统的闲期，即系统连续保持空闲的时间长度.,服务机构工作强度,用于服务顾客的时间服务设施总的服务时间,（四）描述排队系统的主要数量指标,数量指标的常用记号L平均队长，即稳态系统任一时刻的所有顾客数的期望值；Lq平均等待队长，即稳态系统任一时刻等待服务的顾客数的期望值；W平均逗留时间，即(在任意时刻)进入稳态系统的顾客逗留时间的期望值；Wq平均等待时间，即(在任意时刻)进入稳态系统的顾客等待时间的期望值。,（三）描述排队系统的主要数量指标,其他常用数量指标s系统中并联服务台的数目；平均到达率；1平均到达间隔；平均服务率；1/平均服务时间；N稳态系统任一时刻的状态（即系统中所有顾客数）；U任一顾客在稳态系统中的逗留时间；Q任一顾客在稳态系统中的等待时间；,Little（利特尔）公式,用表示单位时间内顾客到达的平均数,表示单位时间内被服务完毕离去的平均顾客数，因此1/表示相邻两顾客到达的平均时间，1/表示对每个顾客的平均服务时间.J.D.C.Little给出了如下公式：,排队系统运行情况的分析,排队系统运行情况的分析，就是在给定输入与服务条件下，通过求解系统状态为n(有n个顾客)的概率Pn，再进行计算其主要的运行指标：系统中顾客数(队长)的期望值L；排队等待的顾客数(排队长)的期望值Lq；顾客在系统中全部时间(逗留时间)的期望值W；顾客排队等待时间的期望值Wq。,第三节MM1模型,模型的条件是：1、输入过程顾客源是无限的，顾客到达完全是随机的，单个到来，到达过程服从普阿松分布，且是平稳的；2、排队规则单队，且队长没有限制，先到先服务；3、服务机构单服务台，服务时间的长短是随机的，服从相同的指数分布。,对于MM1模型有如下公式：,例1,某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。试对此排队队系统进行分析。解对此排队队系统分析如下：（1）先确定参数值：这是单服务台系统，有：故服务强度为：,（2）计算稳态概率：这就是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。而病人需要等待的概率则为：这也是急诊室繁忙的概率。,（3）计算系统主要工作指标：急诊室内外的病人平均数：急诊室外排队等待的病人平均数：病人在急诊室内外平均逗留时间：病人平均等候时间：,（4）为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？由于代入=3，解得5，平均服务时间为：15123min即平均服务时间至少应减少3min,(5)若医院希望候诊的病人90%以上都能有座位,则候诊室至少应安置多少座位?设应该安置个座位,加上急诊室的一个座位,共有+1个。要使90%以上的候诊病人有座位，相当于使“来诊的病人数不多于+1个”的概率不少于90%，即,两边取对数（x2）lglg0.1因1，故所以6即候诊室至少应安置6个座位。,第四节M/M/S模型,此模型与M/M/1模型不同之处在于有S个服务台，各服务台的工作相互独立，服务率相等，如果顾客到达时，S个服务台都忙着，则排成一队等待，先到先服务的单队模型。整个系统的平均服务率为s，*/s，（*1）为该系统的服务强度。,1、状态概率,2、主要运行指标3、系统状态NS的概率,例2承接例1，假设医院增强急诊室的服务能力，使其同时能诊治两个病人，且平均服务率相同，试分析该系统工作情况，并且，例1、例2的结果进行比较。,解这相当于增加了一个服务台，故有：S=2,=3人/h，=4人/h,病人必须等候的概率,即系统状态N2的概率：,表1两个系统的比较,例3某医院挂号室有三个窗口，就诊者的到达服从泊松分布，平均到达率为每分钟0.9人，挂号员服务时间服从指数分布，平均服务率每分钟0.4人，现假设就诊者到达后排成一队，依次向空闲的窗口挂号，显然系统的容量和顾客源是不限的，属于M/M/1型的排队服务模型。求：该系统的运行指标解,如果在例3中，就诊者到达后在每个挂号窗口各自排成一队，即排成3队，且进入队列后不离开，各列间也互不串换，这就形成3个队列，而例3中的其它条件不变。假设每个队列平均到达率相等且为：1230.9/30.3（人/分钟）这样，原来的M/M/3系统就变成了3个M/M/1型的子系统。现按M/M/1型计算主要运行指标，并与上面的例子进行对比分析，结果见表62,表2两个模型的比较,练习,1思考题（1）排队论主要研究的问题是什么？（2）试述排队系统的基本组成部分。（3）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念。（4）试述队长和排队长、等待时间和逗留时间、忙期和闲期等概念。,练习,2设有一个医院门诊，只有一个值班医生。病人的到达过程为泊松流，平均到达时间间隔为20min，诊断时间服从负指数分布，平均需12min，求：(1)病人到来不用等待的概率；(2)门诊部内顾客的平均数；(3)病人在门诊部的平均逗留时间；(4)若病人在门诊部内的平均逗留时间超过1h，则院方将考虑增加值班医生。问病人平均到达率为多少时，医院才会增加医生?,练习,3某售票处有3个售票口，顾客的到达服从泊松分布，平均每分钟到达=09人，3个窗口售票的时间都服从负指数分布，平均每分钟卖给=0.4人，设可以归纳为MM3模型，试求：(1)整个售票处空闲的概率；(2)平均队长；(3)平均逗留时间；(4)平均等待时间；(5)顾客到达后的等待概率。,
展开阅读全文