排队论简要知识

1、排队论简要知识l排队系统描述l根本概念 lM / M / 1 模型lM / M / S 模型l顾客要求效劳的对象统称为“顾客l效劳台把提供效劳的人或机构称为“效劳台或“效劳员l l 面对拥挤现象，人们通常的做法是增加效劳设施，但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果效劳设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。如何做到既保证一定的效劳质量指标，又使效劳设施费用经济合理，恰当地解决顾客排队时间与效劳设施费用大小这对矛盾，就是随机效劳系统理论排队论所要研究解决的问题。 一、排队系统的描述 二、排队系统的主要数量指标l (一)系统特征和根本排队过程l

2、 (二)排队系统的根本组成局部l三)排队系统的描述符号l相似的特征及数学抽象：相似的特征及数学抽象： l (1)(1)请求效劳的人或者物请求效劳的人或者物顾客；顾客； l (2)(2)有为顾客效劳的人或者物，即效劳有为顾客效劳的人或者物，即效劳员或效劳台；员或效劳台；l (3)(3)顾客到达系统的时刻是随机的，为顾客到达系统的时刻是随机的，为每一位顾客提供效劳的时间是随机的，每一位顾客提供效劳的时间是随机的，因而整个排队系统的状态也是随机的。因而整个排队系统的状态也是随机的。l根本排队过程根本排队过程l 可以用图可以用图6666表示。从图表示。从图6666可知，每个顾客由顾客源按一定方可知，每

3、个顾客由顾客源按一定方式到达效劳系统，首先参加队列排式到达效劳系统，首先参加队列排队等待承受效劳，然后效劳台按一队等待承受效劳，然后效劳台按一定规那么从队列中选择顾客进展效定规那么从队列中选择顾客进展效劳，获得效劳的顾客立即离开。劳，获得效劳的顾客立即离开。 排队系统由3个局部组成 1、输入过程 2、效劳规那么 3、效劳台 这是指要求效劳的顾客是按怎样的规律到达排队这是指要求效劳的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流。一般可以从系统的过程，有时也把它称为顾客流。一般可以从3 3个方面来描述个方面来描述个输入过程。个输入过程。 (1)(1)顾客总体数，又称顾客源、输入源。这

4、是指顾客的顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。来源。顾客源可以是有限的，也可以是无限的。 (2)(2)顾客到达方式。这是描述顾客是怎样来到系统的，顾客到达方式。这是描述顾客是怎样来到系统的，是单个到达，还是成批到达。是单个到达，还是成批到达。 (3)(3)顾客流的概率分布，或称相继顾客到达的时间间隔顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。顾客流的概率分布一般有定长分先需要确定的指标。顾客流的概率分布一般有定长分布、二项分布、泊松流布

5、、二项分布、泊松流( (最简单流最简单流) )、爱尔朗分布等假、爱尔朗分布等假设干种。设干种。 这是指效劳台从队列中选取顾客进展效劳的顺序。一般可以分为损失制、等待制和混合制等3大类。 (1)损失制。这是指如果顾客到达排队系统时，所有效劳台都被先到的顾客占用，那么他们就自动离开系统永不再来。 (2)等待制 这是指当顾客来到系统时，所有效劳台都不空，顾客参加排队行列等待效劳。等待制中，效劳台在选择顾客进展效劳时常有如下四种规那么： 1)先到先效劳。按顾客到达的先后顺序对顾客进展效劳。 2)后到先效劳。 3)随机效劳。即当效劳台空闲时，不按照排队序列而随意指定某个顾客承受效劳。 4)优先权效劳。

6、(3)混合制 这是等待制与损失制相结合的一种效劳规那么，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： 1)队长有限。当排队等待效劳的顾客人数超过规定数量时，后来的顾客就自动离去，另求效劳，即系统的等待空间是有限的。 2)等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。 3)逗留时间(等待时间与效劳时间之和)有限。 l (1)效劳台数量及构成形式。从数量上说，效劳台有单效劳台和多效劳台之分。从构成形式上看，效劳台有：单队单效劳台式；单队-多效劳台并联式;多队多效劳台并联式；单队多效劳台串联式；单队多效劳台并串联混

7、合式，以及多队多效劳台并串联混合式等等。l (2)效劳方式。这是指在某一时刻承受效劳的顾客数，它有单个效劳和成批效劳两种。l (3)效劳时间的分布。在多数情况下，对每一个顾客的效劳时间是一随机变量。描述符号：描述符号：/ 各符号的意义：各符号的意义： 表示顾客相继到达间隔时间分布，常用以表示顾客相继到达间隔时间分布，常用以下符号：下符号： M表示到达的过程为泊松过程或负指数表示到达的过程为泊松过程或负指数分布；分布； D表示定长输入；表示定长输入； EK表示表示K阶爱尔朗分布；阶爱尔朗分布； G表示一般相互独立的随机分布。表示一般相互独立的随机分布。 表示效劳时间分布，所用符号与表示顾客到达间

8、隔时间分布一样。表示效劳台(员)个数：“1表示单个效劳台，“s(s1)表示多个效劳台。 表示系统中顾客容量限额，或称等待空间容量。如系统有K个等待位子，那么，0K1)个效劳台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先效劳规那么。 某些情况下，排队问题仅用上述表达形式中的前3个符号。例如，某排队问题为MMS， 如不特别说明那么均理解为系统等待空间容量无限；顾客源无限，先到先效劳，单个效劳的等待制系统。 描述一个排队系统运行状况的主要数量指标有： 1队长和排队长(队列长) 队长是指系统中的顾客数(排队等待的顾客数与正在承受效劳的顾客数之和)；排队长是指系统中正在排队等待效劳的顾客数。

9、队长和排队长一般都是随机变量。 2等待时间和逗留时间 从顾客到达时刻起到他开场承受效劳止这段时间称为等待时间。等待时间是个随机变量。从顾客到达时刻起到他承受效劳完成止这段时间称为逗留时间，也是随机变量。 3. 忙期和闲期 忙期是指从顾客到达空闲着的效劳机构起，到效劳机构再次成为空闲止的这段时间，即效劳机构连续忙的时间。这是个随机变量，是效劳员最为关心的指标，因为它关系到效劳员的效劳强度。与忙期相对的是闲期,即效劳机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。 4数量指标的常用记号 (1)主要数量指标L平均队长，即稳态系统任一时刻的所有顾客数 的期望值；Lq平均等待队长，即稳态

10、系统任一时刻等待效劳的顾客数的期望值；W平均逗留时间，即(在任意时刻)进入稳态系统的顾客逗留时间的期望值；Wq平均等待时间，即(在任意时刻)进入稳态系统的顾客等待时间的期望值。 (2)其他常用数量指标 s系统中并联效劳台的数目； 平均到达率；1平均到达间隔； 平均效劳率；1/平均效劳时间；N稳态系统任一时刻的状态即系统中所有顾客数；U任一顾客在稳态系统中的逗留时间；Q任一顾客在稳态系统中的等待时间； 全部空闲的概率；即稳态系统所有服务台），时（系统中顾客数为特别当的概率；为稳态系统任一时刻状态000nn:PnNPPn效劳强度，即每个效劳台单位时间内的平均效劳时间，般有=(s)，这是衡量排队系统

11、繁忙程度的重要尺度，当趋近于0时，说明对期望效劳的数量来说，效劳能力相对地说是很大的。这时，等待时间一定很短，效劳台有大量的空闲时间；如效劳强度趋近于1，那么效劳台空闲时间较少而顾客等待时间较多。我们一般都假定平均效劳率大于平均到达率，即/1,否那么排队的人数会越来越多，以后总是保持这个假设而不再声明。l 在系统到达稳态时，假定平均到达率为常数，平均效劳时间为常数1/，那么有下面的李特尔公式：l L= W l Lq= Wq l W= Wq +1/l L= Lq +/ 排队系统运行情况的分析，就是在给定输人与效劳条件下，通过求解系统状态为n(有n个顾客)的概率Pn，再进展计算其主要的运行指标：

12、系统中顾客数(队长)的期望值L； 排队等待的顾客数(排队长)的期望值Lq； 顾客在系统中全部时间(逗留时间)的期望值W； 顾客排队等待时间的期望值Wq。模型的条件是：1、输入过程顾客源是无限的，顾客到达完全是随机的，单个到来，到达过程服从普阿松分布，且是平稳的；2、排队规那么单队，且队长没有限制，先到先效劳；3、效劳机构单效劳台，效劳时间的长短是随机的，服从一样的指数分布 。 10P)1 (nnP1LLLq1)(221WWWq)(1)(kkNP 某医院急诊室同时只能诊治一个病人，诊某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要治时间服从指数分布，每个病人平均需要151

13、5分钟。分钟。病人按泊松分布到达，平均每小时到达病人按泊松分布到达，平均每小时到达3 3人。试人。试对此排队队系统进展分析。对此排队队系统进展分析。解解 对此排队队系统分析如下：对此排队队系统分析如下：1 1先确定参数值：这是单效劳台系统，有：先确定参数值：这是单效劳台系统，有： 故效劳强度为：故效劳强度为：hhh/4/1560,/3人人人75. 04375. 010P25. 075. 0110P人人3343L人人25. 275. 03LLqmin6013411hhWmin4575. 075. 01hhWWq211Wmin12511h9 . 0) 1(1) 1(xNPxNP1 . 0) 1(

14、xNP1 . 021)1(xx1 . 021)1(xx875. 0lg1lg1 . 0lg2xl此模型与M/M/1模型不同之处在于有S个效劳台，各效劳台的工作相互独立，效劳率相等，如果顾客到达时，S个效劳台都忙着，那么排成一队等待，先到先效劳的单队模型。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,qq0NPWWLLP，1430.93，SS 0748

15、. 03/2.251132.2522.2512.2502.251132100！整个挂号间空闲的概率P 人称队列长等待挂号的平均人数或7 . 10748. 0!34/32.2523qL 人称队长挂号间平均逗留人数或95. 325. 27 . 13qLL 分钟在挂号间平均逗留时间分钟等候挂号的平均时间4.390.411.89589.19 .07 .14WWq 57. 00748. 04/132.253363！闲）的概率人或各挂号员都没有空者不少于（即系统中就诊就诊者到达后必须等待NP 表表6 62 2 两个模型的比较两个模型的比较指标指标（1 1）M/M/3M/M/3型型（2 2）M/M/1M/M

16、/1型型挂号间空闲挂号间空闲的概率的概率0.07480.07480.250.25（各子系统）（各子系统）就诊者必须等待就诊者必须等待的概率的概率P(N3)= 0.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试述队长和排队长、等待时间和逗留时间、忙期和闲期等概念。2设有一个医院门诊，只有一个值班医生。病人的到达过程为泊松流，平均到达时间间隔为20min，诊断时间服从负指数分布，平均需12min，求：