[企业管理]三2010暑期培训排队论.ppt

《[企业管理]三2010暑期培训排队论.ppt》由会员分享，可在线阅读，更多相关《[企业管理]三2010暑期培训排队论.ppt（188页珍藏版）》请在三一文库上搜索。

1、董 珺,排队论 （ Queuing theory）,排队论,一.概率论及随机过程回顾 二.排队论的基本知识 三.单服务台负指数分布排队系统分析 四.多服务台负指数分布排队系统分析 五.一般服务时间M/G/1模型分析 六.经济分析_排队系统的最优化,一、概率论及随机过程回顾,随机变量 离散型随机变量 概率分布和概率分布图 数学期望和方差 常见离散型随机变量的概率分布 二点分布? 二项式分布? Poisson分布?,1.1、随机变量与概率分布,一、概率论及随机过程复习,随机变量 离散型随机变量 概率分布和概率分布图 数学期望和方差 常见离散型随机变量的概率分布 二点分布? 二项式分布? Poiss

2、on分布?,一、随机变量与概率分布,随机变量 连续型随机变量 概率密度函数 概率分布函数 数学期望和方差 常见连续型随机变量的概率分布 均匀分布 指数分布？ 正态分布？ k阶爱尔朗分布？,一、随机变量与概率分布,? 爱尔朗分布,为k个相互独立的随机变量； 服从相同参数 的负指数分布；,设 ，则T的密度函数为,如k个服务台串联（k个服务阶段）， 一个顾客接受k个服务共需的服务时间T， T爱尔朗分布。,若顾客连续接受串联的k个服务台的服务，各服务台的服务时间相互独立，且均服从负指数分布，则顾客接受k个服务共需的服务时间Tk阶爱尔朗分布。,1.2 随机过程的有关概念,随机过程(Random proc

3、ess)的定义,设 ，是一族随机变量， T是一个实数集，对 是一个 随机变量，则称 为随机过程。,T：参数集合 当T=0,1,n,时，称为随机序列 ：随机过程的一个状态 状态空间E=X(t)全体可能取值， ,随机过程的基本类型 二阶矩过程 平稳过程 平稳独立增量过程 常见随机过程 马尔可夫过程？ Poisson过程？ 生灭过程？,1.2 随机过程的有关概念,定义： 若满足如下性质： 对任意非负整数 ，只要 就有 则称 具有马尔可夫性，或无后效性。,马尔可夫过程 马尔可夫链,现在,将来,“将来”的情况与“过去”无关， 只是通过“现在”与“过去”发生联系，若 “现在”已知，“将来”与“过去”无关。

4、,时齐的马氏链：马氏链 若满足： 则称 为时齐马尔可夫链, 系统由状态i经过m 个时间间隔 （或m 步）转移到状态j 的转移概率,其中Poisson过程是应用最为广泛的一类随机过程，常用来描述派对系统中顾客到达的过程、城市中的交通事故、保险公司的理赔次数等。,Poisson过程,定义：设 为时间 内到达系统的顾客数，若满足下面三个条件： 独立性：在任意两个不相交的区间内顾客到 达的情况相互独立； 平稳性：在 内有一个顾客到达的 概率为 普通性：在 内多于一个顾客到达 的率为 。 则称 为Poisson过程。且N(t)服从Poisson分布。,（1）只与区间长度与 起点无关。 （2）单位时间内一

5、个 顾客到达的概率 为 。,Poisson过程与Poisson分布,数理统计方法 容易初步判断:期望=方差,Poisson过程与负指数分布,负指数分布的性质:,马尔可夫性，或无后效性,对于Poisson流： 单位时间平均到达的顾客数 顾客相继到达的平均间隔时间,定义：设 为一个随机过程，若N(t)的概率分布具有以下性质： (1)假设N(t)=n，则从时刻到下一个顾客到达时刻止的时间服从参数为 的负指数分布； (2)假设N(t)=n，则从时刻到下一个顾客离开时刻止的时间服从参数为 的负指数分布； (3)同一时刻是只有一个 顾客到达或离去。 则称 为一个生灭过程。,生灭过程,平稳生灭过程系统状态n

6、 平衡方程：“流入=流出”,系统达到平稳状态时：,的分布,系统达到平稳状态时：,平衡方程：,当 时才有意义,现实生活中的排队模型,Bank Airport Hospital Road Manufacturing Hotel Restaurant WC ,运筹学 排队模型,二、排队论的基本知识,2.1 排队模型 2.2 排队系统的组成和特征,什么是排队论,什么是 排队论?,什么是排队论,排队论是研究排队系 统的理论，又称随机服 务系统理论，它提供了 很多不同的排队模型， 通过这些排队模型能够 找到服务成本和服务水 平之间较好的平衡。,排队系统的描述,涉及的要素 顾客 队列 服务台 到达间隔时间

7、服务时间 排队规则,运筹学 排队模型,排队系统的描述,绩效测度 等待顾客数 顾客等待时间 服务台忙期 服务台闲期 服务台利用率,运筹学 排队模型,排队模型存在的问题,如何以最经济的方式控制排队系统，使其达到特定的要求？ 提供过多的服务能力来控制排队系统将会造成过量的成本 提供的服务能力不足将会导致过多的等待，降低顾客满意度并造成顾客流失，减少收益,2.1、排队模型,排队系统的的一般表示 （A Basic Queuing System）,下图 就是排队过程的一般模型 。 各个顾客由顾客源（总体）出发，到达服务机构（服务台、服务员）前排队等侯接受服务，服务完了后就离开。 排队结构指队列的数目和排列

8、方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。 我们所说的排队系统就指图中虚线所包括的部分。,在现实中的排队现象是多种多样的,在现实中的排队现象是多种多样的，对上面所说的“顾客”和“服务员”，要作广泛地理解，它现可以是人，也可以是非生物； 队列可以是具体地排列，也可以是无形的（例如向电话交换台要求通话的呼唤）； 顾客可以走向服务机构，也可以相反（如送货上门）。 下面举一些例子说明实现中形形色色的排队系统,服务机构,(a) 一个队列、单服务台（阶段）,(b) 一个队列、s个服务阶段,服务机构,服务机构,(c) 一个队列、s个服务台 一个服务阶段,服务机构,(d) s

9、个队列、s个服务阶段,服务机构,(e)混合型,排队结构,(f) 一个队列,(g) s个队列,排队系统的组成和特征,一般的排队系统都有三个基本组成部分 1.输入过程； 2.排队规则； 3.服务机构。,现在分别说明各部分的特征： （1）输入过程：输入即指顾客到达排队系统。可能有下列各种不同情况，当然这些情况并不是彼此排斥的。 （a）顾客的总体（称为顾客源）的组成可能是有限的，也可能是无限的。工厂内停机待修的机器显然是有限的总体。 （b）顾客到来的方式可能是一个一个的，也可能是成批的。例如到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客，我们将只研究单个至来的情形。,（c）顾客相继到达的间隔

10、时间可以是确定型的，也可以是随机型的。 如在自动装配线上装配的各部件就必须按确定的时间间隔到达装配点，定期运行的班车、班轮、班机的到达也都是确定型的。 但一般到商店购物的顾客、到医院诊病的病人、通过路口的车辆等，它们的到达都是随机型的。 对于随机型的情形，要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布（下图）,顾客到达,时间,ti-1,ti,ti+1,输入过程,(d)顾客的到达可以是相互独立的。 就是说，以前的到达情况对以后顾客的到来没有影响，否则不是有关联的。 例如，工厂内的机器在一个短的时间内出现停机（顾客到达）的概率就受已经待修或被修理的机器数目的影响。 我们主要讨论的是相互

11、独立的情形。,输入过程,（e）输入过程可以是平衡的，或称对时间是齐次的，是指描述相继到达间隔时间分布和所含参数（如期望值、方差等）都是与时间无关的，否则称为非平衡的，非平稳情形的数学处理是很困难的。,顾客到达时间间隔的分布:,：第n个顾客与第n-1个顾客到达的时间间隔；,顾客到达时间间隔的分布:,假定 是独立同分布，分布函数为 ， 排队论中常用的有两种：,（2）最简流（即Poisson流）（M）： 顾客到达时间间隔 为独立的， 服从负指数分布，其密度函数为,（1）定长分布（D）：顾客到达时间间隔为确定的。,因为负指数分布 具有无后效性 （即Markov性）,大多数排队模型假设到达间隔时间的概率

12、分布形式是指数分布 小间隔时间出现的可能性很大，而大间隔时间出现的机会则很小，这个间隔时间的特征能在实践中观察到,负指数分布,随机变量T的概率密度若是 则称T服从负指数分布，它的分布函数是 数学期望ET= ,方差DT= ， 标准差T= 。,负指数分布有下列性质： （1）由条件概率公式容易证明 这性质称为无记忆性或马尔柯夫性，若T表示排队系统中顾客到达的间隔时间，那么这个性质说明一个顾客到来所需的时间与过去一个顾客到来所需时间s无关，所以说这情形下的顾客到达是纯随机的。,（2）当输入过程是普阿松流时，那么顾客相继到达的间隔时间T必服从负指数分布。这时因为对于普阿松流，在0,t)区间内至少有1个顾

13、客到达的概率是： 而这概率又可表示为,对于普阿松流，表示单位时间平均到达的顾客数，所以1就表示相继顾客到达平均间隔时间，而这正和ET的意义相符。,（2）排队规则,（a）顾客到达时，如所有服务台都正被占用，在这种情形下顾客可以随即离去，也可以排队等侯。 随即离去的称为即时制或称损失制，因为这将失掉许多顾客； 排队等侯的称为等待制。 普通市内电话的呼唤属于前者，而登记市外长途电话的呼唤属于后者。,排队规则,对于等待制，为顾客进行服务的次序可以采用下列各种规则： 先到先服务，后到先服务，随机服务，有优先权的服务等。 先到先服务(FCFS)，即按到达次序接受服务，这是通常的情形。 后到先服务(LCFS

14、)，如乘用电梯的顾客常是后人先出的。仓库中存放的厚钢板也是如此。在情报系统中，最后到达的信息往往是最有价值的，因而常采用后到先服务（指被采用）的规则。,排队规则,随机服务(SIRO) ，指服务员从等待的顾客中随机地选取其一进行服务，而不管到达的先后，如电话交换台接通呼唤的电话就是如此。 有优先权的服务(PR) ，如医院对于病情严重的患者将给予优先治疗。 （b）从占有的空间来看，队列可以排在具体的处所（如售票处、候诊室等），也可以是抽象的（如向电话交换台要求通话的呼唤）。 由于空间的限制或其它原因，有的系统要规定容量（即允许进入排队系统的顾客数）的最大限；有的没有这种限制（即认为容量可以是无限的

15、）。,排队规则,（c）从队列的数目看，可以是单列，也可以是多列。 在多列的情形，各列间的顾客有的可以互相转移，有的不能（如用绳子或栏杆隔开）。 有的排队顾客因等候时间过长而中途退出，有的不能退出（如高速公路上的汽车流），必须坚持到被服务为止。 我们将只讨论各列间不能互相转移、也不能中途退出的情形。,3）服务机构,从服务机构的形式和工作情况来看有以下几种情况。 （a）服务机构可以没有服务员，也可以有一个或多个服务员（服务台、通道、窗口等）. 例如，在敞架售书的书店，顾客选书时就没有服务员，但交款时可能有多个服务员。,服务机构,（b）在有多个服务台的情形中，它们可以是平行排列（并列）的，可以是前后

16、排列（串列）的，也可以是混合的。下图说明这些情形。 图a是单队单服务台，图b是多队多服务台， 图c是单队多服务台（并列）的情形，图d是多服务台（串列）的情形，图e是多服务台（混合）的情形。,1,1,2,c,c,1,2,1,2,c,a,b,c,d,1,1,1,e,服务机构,(d) 服务方式可以对单个顾客进行，也可以对成批顾客进行，公共汽车对站台等候的顾客就成批进行服务，我们将只研究单个单个地服务方式。 （e）和输入过程一样，服务时间也分确定型的和随机型的。自动冲洗（服务）的时间就是确定 ，但大多数情形的服务时间是随机型的。对于随机型的服务时间，需要知道它的概率分布。 （f）和输入过程一样，服务时

17、间的分布我们总假定是平稳的，即分布的期望值、方差等参数都不受时间的影响。,服务时间分布:,设某服务台的服务时间为V，其密度函数为b（t），常见的分布有：,（1）定长分布（D）：每个顾客接受服务的时间 是一个确定的常数。 （2）负指数分布（M）：每个顾客接受服务时间 相互独立，具有相互的负指数分布： 其中 ，为一常数。,- 单位时间平均服务完成的顾客数 1/ - 每个顾客的平均服务时间,服务时间分布:,（3）k阶爱尔朗（Erlang）分布：每个顾客接受服务 时间服从k阶爱尔朗分布，其密度函数为：,Erlang Distribution (爱尔朗分布) 服务时间的波动量介于指数分布和常量之间 有一

18、个形状参数k决定其标准差,Erlang Distribution (爱尔朗分布),例如串列的k个服务台，每台服务时间相互独立，服从相同的负指数分布（参数ku），那么一顾客走完k个服务台总共所需要服务时间就服从上述的k阶爱朗分布。,注意：爱尔朗分布族提供更为广泛的模型类。比指数分布有更大的适应性。事实上，当k=1时，爱尔朗分布化为负指数分布，这可看成是完全随机时；当k增大时，爱尔朗分布的图形逐渐变为对称为；当k30时爱尔朗分布近似于正态分布；k时；由看出VarT0，因此这时爱尔朗分布化为确定型分布,所以一般k阶爱尔朗分布可看成完全随机与完全确定的中间型，能对现实世界提供更为广泛的适应性。,排队系

19、统的分类,D.G.Kendall在1953年提出一个分类方法，按照上述各部分的特征中最主要的、影响最大的三个，即 1相继顾客到达间隔时间的分布； 2服务时间的分布； 3服务台个数。,排队系统的分类,按照这三个特征分类，并用一定符号表示，称为Kendall记号。这只对并列的服务台（如果服务台是多于一个的话）的情形，他用的符号形式是： X/Y/Z 其中X处填写表示相继到达间隔时间的分布， Y处填写表示服务时间的分布， Z处填写并列的服务台数目。,排队系统的分类,表示相继到达间隔时间和服务时间的各种分布的符号是： M负指数分布（M是Markov的字头，因为负指数分布具有无记忆性，即Markov性）

20、D确定定型（Deterministic） Ekk阶爱尔朗(Erlang)分布 GI般相互独立（General Independent）的时间间隔的分布 G一般（General）服务时间的分布,排队系统的分类,例如： MM1表示相继到达间隔时间为负指数分布、服务时间负指数分布、单服务台的模型； DMc表示确定的到达间隔、服务时间为负指数分布、c个平行服务台（但顾客是一队）的模型。,排队系统的分类,以后，在1971年一次关于排队论符号标准化会议上决定，将Kendall符号扩充成为： XYZABC 形式，其中前三项意义不变， A处填写系统容量限制N， B处填写顾客源数目m， C处填写服务规则，如先到

21、服务FCFS，后到先服务LCFS 等。 并约定，如略去后三项，即指XYZFCFS的情形。在本节中，因只讨论先到先服务FCFS的情形，所以略去第六项。,例：M/M/s/K表示？,M/M/s/K表示相继到达间隔时间为负指数分布、服务时间负指数分布、s个服务台、系统容量为K的模型,例如 M / M / 1 / / 表示顾客到达过程服从负指数分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。,其他模型,M/M/c/K/K 顾客来源是有限的服务系统. 例如： 一个饭店有 X 张桌子和 Y个服务生服务来源有限的顾客. M/D/1 服务时间不变的服务系统. D/M/1 确定性到达

22、模式, 及指数分布服务时间. 例如：医生赴约治病的时间表. M/E k/1 服务服从 Erlang 分布. 例如：用相同平均时间去完成一些程序。,排队问题的求解,一个实际问题作为排队问题求解时，首先要研究它属于哪个模型，其中只有顾客到达的间隔时间分布和服务时间的分布需要实测的数据来确定，其它因素都是在问题提出时给定的。解决排队问题首先要根据原始资料做出顾客到达间隔和服务时间的经验分布，然后按照统计学的方法（例如x2检验法）以确定合于那种理论分布，并估计它的参数值。,解排队问题的目的,解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理、研究设计

23、改进措施等。 所以必须确定用以判断系统运行优劣的基本数量指标，解排队问题就是首先求出这些数量指标的概率分布或特征数。,排队系统的指标,这些指标通常是： （1）队长，指在系统中的顾客数，它的期望值记作Ls； 排队长（队列长，指在系统中排队等待服务的顾客数，它的期望值记作Lq; Ls = Lq + 正在接受服务的顾客数 一般情形，Ls（或Lq）越大，说明服务率越低，排队成龙，是顾客最厌烦的。,排队系统的指标,（2）逗留时间，指一个顾客在系统中的停留时间，它的期望值记作Ws； （3）等待时间，指一个顾客在系统中排队等待的时间，它的期望值记作Wq， WS = Wq + 服务时间,排队系统的指标,在机器

24、故障问题中，无论是等待修理或正在修理都使工厂受到停工的损失，所以逗留时间（停工时间）是主要的；但一般购物、诊病等问题中仅仅等待时间常是顾客们所关心的。,排队系统的指标,此外，还有忙期(Busy Period)指从顾客到达空闲服务机构起到服务机构再次为空闲止这段时间长度，即服务机构连续繁忙的时间长度，它关系到服务员的工作强度，忙期和一个忙期中平均完成服务顾客都是衡量服务机构效率的指标。,排队系统的指标,在即时制或排队有限缺点情形，还有由于顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等，这些都是很重要的指标。,排队系统的状态,计算这些指标的基础是表达系统状态的概率，所谓系统的状态即

25、指系统中顾客数，如系统中有n个顾客就说系统的状态是n，它的可能值是 （1）队长没有限制时，n0，1，2 （2）队长有限制，最大数为N时，n0，1，2，N, （3）即时制，服务台个数是c时，n=0，1，2，c。 后者，状态n又表示正在工作（繁忙）的服务台数。,排队系统的状态,这些状态的概率一般是随时刻t 而变化，所以在时刻t、系统状态为n的概率用Pn（t）表示。 求状态概率Pn(t)的方法，首先要建立含Pn（t）的关系式,因t为是连续变量，而n只取非负整数，所以建立的Pn（t）的关系式一般是微分差分方程（关于t微分瞬态解是不容易的，一般地，即使求出也很难利用，因此我们常用它的极限（如果存在的话）

26、 称 为稳态（Steady state），或称统计平衡状态(Statistical Equilibrium State)的解。,排队系统的状态,稳态的物理含义是，当系统运行了无限长的时间之后，初始(t=0)出发状态的概率分布（Pn(0)，n0）的影响将消失，而且系统的状态概率分布不再随时间变化。当然，在实际应用中大多数问题，系统会很快趋于稳态，而无需等到t以后。但永远达不到稳态的情形也确实是存在的。 求稳态概率Pn时，并不一定求t时Pn（t）的极限，而只需令导数P/n=0即可，我们以下着重研究稳态的情形。,三.单服务台负指数分布 排队系统分析,3.1 M/M/1模型即(M/M/1/);,3.2

27、 M/M/1/N/ 模型(即系统的容量有限),3.3 M/M/1/ /m 模型（即顾客源为有限）,标准的/MM1模型（MM1/）,标准的M/M/1模型，是指适合下列条件的排队系统： （1）输入过程顾客源是无限的，顾客单个到来，相互独立，一定时间的到达数服从普阿松分布，到达过程已是平稳的。 （2）排队规则单队，且对队长没有限制，先到先服务。 （3）服务机构单服务台，各顾客的服务时间是相互独立的服从相同的负指数分布。,3.1 M/M/1模型,无限,输入过程服从 参数为 的 Poisson过程,单队 队长无限 先到先服务,服务时间服从 参数为 的 负指数分布,生灭过程,此外，还假定到达时间和服务时间

28、是相互独立的。 在分析标准的MM1模型时，首先要求出系统在任意时刻t的状态为n（系统中有n个顾客）的概率Pn(t)，它决定了系统运行的特征。,求解：,:系统达到平稳后，系统有n个顾客的概率。,平衡方程：,其中,排队系统的生灭过程与状态转移方程,一、排队系统的生灭过程,(一)生灭过程的背景与定义,设某系统具有状态集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)转移到“n+1”的概率为n(t ) ; (2) N(t+t)转移到“n-1”的概率为n(t ) ; (3)

29、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无 关; 与系统当前状态n有关，而与以前的状态无关； (3)系统灭亡一个的概率n(t )与t有关，而与t无 关; 与系统当前状态n有关，而与以前的状态无关；,马尔可夫性质,(三) 排队系统的生灭过程,顾客到达“生”； 顾客离开“灭”,顾客到达,顾

30、客离去,(1)生灭过程示意,若排队系统具有下列性质: (1) 顾客到达为泊松流，时间间隔服从参 数为n的负指数分布; (2) 顾客服务时间服从参数为 n的负指 数分布; 则排队系统的随机过程N(t),t=0具有马 尔可夫性质, 为一个生灭过程.,(2)生灭过程定义,二、排队系统的状态转移方程,(一) 排队系统状态的概率及其分布,(1)瞬态概率Pn(t) 表示时刻系统状态N(t)=n的概率; (2) 稳态概率Pn Pn= Pn(t) ;,一般，稳态概率Pn的分布，是分析计算 排队系统运行优劣的基础。,(二) 排队系统状态概率的微分差分方程,推导过程见后面,求解可得瞬态概率Pn(t),(三) 排队

31、系统状态转移方程,求解可得稳态概率Pn,令,则,排队系统状态转移方程,(四) 排队系统状态转移图,三、 排队系统稳态概率Pn的求解,对一般排队系统，均有下式成立,其中有效到达率为,四、 排队系统性能参数的一般关系 Little 公式,因已知到达规律服从参数为的Poisson过程，服务时间服从参数为的负指数分布，所以在t,t+t）时间区间内分为： （1）有1个顾客到达的概率为to（t）；没有顾客到达的概率就是1-to（t） （2）当有顾客在接受服务时，1个顾客被服务完了（离去）的概率是1t+o(t). (3)多于一个顾客的到达或离去的概率是o(t)，可忽略。 在时刻t+t，系统中有n个顾客(n0

32、)存在下列四种情况（到达或离去是2个以上的没列入,可忽略）：,在时刻t+t，系统中有n个顾客(n0),表示发生（1个），表示没有发生 它们的概率分别是（略去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)tt,由于这四种情况是互不相容的，所以 Pn(t+t)应是这四项之和，即 （将关于t的高阶无穷小合成一项）：,令t0，得关于Pn(t)的微分差分方程 (12.15) 当n0，则只有上表中(A),（B）两种情况，即 类似地求得 (12.16) 这样系统状态(n)随时间变化过程是称为生灭过程的一个特

33、殊情形。,解方程（12.15）(12.16)是很麻烦的，求得的解(瞬态解)中因为含有修正的贝赛耳函数，也不便于应用，我们只研究稳态的情况，这时Pn(t)与t无关，可写成Pn，它的导数为0,由于(12.15),（12，16）式可得 这是关于Pn的差分方程。它表明了各状态间的转移关系。用图12-7表示。,由图12-7可见，状态0转移到状态1的转移率为P0，状态转移到状态0的转移率为P1，对状态0必须满足以下平衡方程 P0=P1 同样对任何n1的状态，可得到(12.18)的平衡方程。求解(12.17)得 P1（）P0 将它代入(12.18)，令n1, P1=（）（/）P0 P2（）2P0,同理依次推

34、得 今设 （否则队列将排至无限远），又由概率的性质知 正则性方程,将Pn的关系代入 得 （12.19） 这是系统状态为n的概率。,上式的有其实际意义。根据表达式的不同，可以有不同的解释， 当表达时，它是平均到达率与平均服务率之比；即在相同时区间内顾客到达的平均数与被服务的平均数之比。 若表示为（1/）/(1/)，它是为一个顾客的服务时间与到达间隔时间之比：称为服务强度（traffic intensity）。或称为话务强度。这是因为早期排队论是爱尔朗等人在研究电话理论时用的术语，一直沿用至今。,由(12.19)式，1P0，它刻划了服务机构的繁忙程度；所以又称服务机构的利用率。读者可考虑由于的大小

35、不同值，将会产生顾客与服务员之间、服务员与管理员之间怎样不同的反应或矛盾。,关于 的几点说明：,服务强度,即顾客的顾客平均到达率 小于顾客平均服务率时， 系统才能达到统计平稳。,系统中至少有一个顾客的概率； 服务台处于忙的状态的概率； 反映系统繁忙程度,计算有关指标,队长,队列长,计算有关指标,逗留时间: 可以证明, Ws服从参数为-的负指数分布. 则: 等待时间,计算有关指标,计算有关指标,Little公式（相互关系）,小 结,平均服务时间,平均在忙的服务台数/正在接受服务的顾客数,有效到达率,平均忙期 B , 忙期出现的概率 平均闲期 I , 闲期出现的概率 (1-),忙期 B : 闲期

36、I = : (1-),平均闲期 I = 1 / ,闲期的分布与顾客到达时间间隔的相同-服从参数为的负指数分布,计算有关指标,忙期与闲期,WHY ?,1-P0=,平均忙期 B , 忙期出现的概率 平均闲期 I , 闲期出现的概率 (1-),忙期 B : 闲期 I = : (1-),平均闲期 I = 1 / ,平均忙期 B = ( / (1-) / = 1/( - ),计算有关指标,忙期与闲期,与逗留时间Ws相同! ?,例：某医院手术室根据病人来诊和完成手术时间的记录，任意抽查100个工作小时，每小时来就诊的病人数n的出现次数如表，又任意抽查了100个院成手术的病历，所用时间出现的次数如表。,解：

37、,解：,取2.1，u2.5，可以通过统计检验的方法（例如x2检验法），认为病人到达数服从参数为2.1的普阿松分布，手术时间服从参数为2.5的负指数分布。 （3） 它说明服务机构（手术室）有84时间是繁忙(被利用)，有16%的时间是空闲的。,解：,不同的服务规则（先到先服务，后到先服务，随机服务）它们的不同点主要反映在等待时间的分布函数的不同，而一些期望值是相同的。我们上面讨论的各种指标，因为都是期望值，所以这些指标的计算公式对三种服务规则都适用（但对有优先权的规则不适用）。,2 单服务台泊松到达、负指数服务时间的排队模型,练习 某储蓄所只有一个服务窗口。根据统计分析，顾客的到达过程服从泊松分布

38、，平均每小时到达顾客36人；储蓄所的服务时间服从负指数分布，平均每小时能处理48位顾客的业务。试求这个排队系统的数量指标。,解 平均到达率 = 36/60 = 0.6， 平均服务率 = 48/60 = 0.8。 P0 =1 / = 10.6/0.8 = 0.25, Lq =2/( ) = (0.6)2 / 0.8(0.8 0.6) =2.25 (个顾客),Ls = Lq + / = 2.25+ 0.6/0.8 =3 (个顾客), Wq = Lq / = 2.25/0.6 = 3.75（分钟）, Ws = Wq+ 1/ = 3.75+1/0.8 =5 （分钟）, Pw = / = 0.6/0.8

39、 = 0.75, Pn =( /)n P0 = (0.75)n 0.25, n=1, 2, 。 通过计算，可知储蓄所的排队系统里有n个顾客的概率，见表14-1。,表14-1,通过计算数据与表中数据，可知储蓄所的排队系统并不尽如人意，到达储蓄所有75%的概率要排队等待，排队的长度平均为2.25个人，排队的平均时间为3.75分钟，是1.25分钟的3倍，而且储蓄所里有7个或更多的顾客的概率为13.35%，这个概率太高了。而要提高服务水平，减少顾客的平均排队时间和平均服务时间，一般可采用两种措施：第一，减少服务时间，提高服务率；第二，增加服务台即增加服务窗口。 如采取第一种方法，不增加服务窗口，而增加

40、新型点钞机，建立储户管理信息系统，可以缩短储蓄所每笔业务的服务时间，使每小时平均服务的顾客数目从原来的48人提高到60人，即每分钟平均服务的顾客数从0.8人提高到1人，这时 仍然为0.6， 为1，通过计算得到的结果如表14-2所示：,从上表我们可以看出由于把服务率从0.8提高到1，其排队系统有了很大的改进，顾客平均排队时间由3.75分钟减少到1.5分钟，顾客平均逗留时间从5分钟减少到2.5分钟，在系统里有7个或更多顾客的概率有大幅度的下降，从13.35%下降到2.79%。 如果采用第二种方法，再设一个服务窗口，排队的规则为每个窗口排一个队，先到先服务，并假设顾客一旦排了一个队，就不能再换到另一

41、个队上去（譬如，当把这个服务台设在另一个地点，上述假设就成立了）。这种处理方法就是把顾客分流，把一个排队系统分成两个排队系,表14-2,统，每个排队系统中有一个服务台，每个系统的服务率仍然为0.8，但到达率由于分流，只有原来的一半了， =0.3，这时我们可求得每一个排队系统的数量指标如下表所示：,我们比较上面两表，知道采用第二个方法的服务水平也使得原来的服务水平有了很大的提高，采用第二种方法顾客平均排队时间减少到了0.75分钟，顾客平均逗留时间减少到了2分钟，第二种排队系统为两个M/M/1排队系统。如果在第二种方法中把排队的规则变一下，在储蓄所里只排一个队，这样的排队系统就变成了 M/M/2排

42、队系统。,系统容量有限制的情形(M/M/1/N/FCFS）,这种模型我们记为M/M/1/N/，这个记法中的第四位字母K表示这个系统的最大容量为N，因为这是一个单服务台的情况，所以排队的顾客服务最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。 这个模型可简写为M/M/1/N。 由于所考虑的排队子系统中最多只能容纳N个顾客（等待位置只有N-1个），因而有:,系统容量有限制的情形(M/M/1/N/FCFS）,状态转移图 状态转移方程,求排队系统顾客数的分布状况,其中,求排队系统顾客数的分布状况,队长 队列长,计算有关指标,逗留时间 等待时间,计算有关指标,系统

43、已满顾客不能到达的概率-损失率,有6个椅子接待人们排队，超过6人顾客就离开，平均到达率3人/小时，理发需时平均15分钟。,7为系统中的最大顾客数。 平均到达率: 3人/小时 平均服务率: 4人/小时,举例：单人理发馆排队问题,顾客到达就能理发的概率 -相当于理发店内没有顾客 等待顾客数的期望值,求有效到达率 顾客在理发馆内逗留的期望时间,人/小时,可能的顾客中有百分之几不等待就离开 -即求系统中有7个顾客的概率,这也是理发馆的损失率。,设：m ：为顾客总体数， ： 每个顾客的到达率， m - Ls ：系统外顾客的平均数， e = （ m - Ls）：为系统有效到达率。,3.3 顾客源有限制的情

44、形 (M/M/1/m/FCFS）,含义与上节不同对顾客而言，而不是对系统,m,对系统而言,有一个顾客到达的概率,状 态 转 移 图,0,1,m,n-1,n,(m-n+1) ,(m-n),n+1,. . .,. . .,m-1,m,. . .,(m-1),2,状态转移方程,注意到 ，,求解状态转移方程得,有效到达率,求解顾客数概率分布,等待时间 正常运转的平均设备台数,计算有关指标,队长 队列长 逗留时间,计算有关指标,例. 某车间有5台机器，每台机器连续运转时间服从负指数分布，平均连续运转时间为15分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12分钟，求该排队系统的数量指标P0,L

45、q,Ls,Wq,Ws,以及P5。 解：这是一个M/M/1/ /5系统。其中，m=5, =1/15, =1/12,/ =0.8。 Lq=2.766 ; Ls=3.759；Wq=33.43 ; Ws=45.43P5=0.2870 机器停工时间过长，修理工几乎没有空闲时间，应当提高服务率减少修理时间或增加修理工人。,=0.0073,4.1 标准的 M/M/c 模型（ M/M/c / ） 4.2 标准的 M/M/c /N/ 型 4.3 标准的 M/M/c / m模型,四. 多服务台负指数分布排队系统分析,规定： 各服务台工作是相互独立的，且平均服务率相同，均为 。 整个服务机构的平均服务率为： c (

46、当n c )， n (当n c ); 记 = / , s= /c = /c 为服务系统的平均利用率 当 / c 1时，不会排成无限队列。单位时间顾客平均到达数,4.1 标准的 M/M/c 模型（ M/M/c / ）,1,2,c,.,服务台C个,系统人数n人,1,2,c,.,服务台C个,系统人数n人,n = c,1,2,c,.,服务台C个,系统人数n人,n c,状 态 转 移 图,0,1,n-1,n,n,(n+1),n+1,. . .,. . .,2,2,n-1,n,c,c,n+1,. . .,. . .,n = c,n c,在分析这排队系统时，仍从状态间的转移关系开始，可见图12-13。如状态1转移到状态0，即系统中有一名顾客被服务完了（离去）的转移率为up1。状态2转移到状态1时，这就是在两个服务台上被服务的顾客中有一个被服务完成而离去。因为不限哪一个，那么这时状态的转移率便是2up2。同时，再考虑状态n转移到n-1的情况。当nc个顾客在被服务，n=-c个顾客在等候，因此这时状态转移率为cuPn.,状态转移方程,4.1 标准的 M/M/c 模型（ M/M/c / ）,解差分方程，求得状态概率为,4.1 标准的 M/M/c 模型（ M/M/c / ）,顾客等候的概率,计算有关指标,平均正接受服务的顾客数=正忙的服务台数,队长 队列长