第六章 排 队 论

《第六章 排 队 论》由会员分享，可在线阅读，更多相关《第六章 排 队 论（54页珍藏版）》请在金锄头文库上搜索。

1、第六章 排 队 论随机服务系统理论 第六章 排 队 论l排队系统描述l基本概念 lM / M / 1 模型lM / M / S 模型第一节 排队系统描述l顾客要求服务的对象统称为“顾 客”l服务台把提供服务的人或机构称 为“服务台”或“服务员”各种形式的排队系统各种形式的排队系统各种形式的排队系统各种形式的排队系统各种形式的排队系统随机服务系统排队论所要研究解决的问题 l 面对拥挤现象，人们通常的做法是增加服务 设施，但是增加的数量越多，人力、物力的支出 就越大，甚至会出现空闲浪费，如果服务设施太 少，顾客排队等待的时间就会很长，这样对顾客 会带来不良影响。如何做到既保证一定的服务质 量指标，

2、又使服务设施费用经济合理，恰当地解 决顾客排队时间与服务设施费用大小这对矛盾， 就是随机服务系统理论排队论所要研究解决 的问题。第一节 基本概念； 一、排队系统的描述二、排队系统的主要数量指标一、排队系统的描述l (一)系统特征和基本排队过程l (二)排队系统的基本组成部分l（三)排队系统的描述符号(一)系统特征和基本排队过程l共同特征： (1)请求服务的人或者物顾客； (2)有为顾客服务的人或者物，即服务员或服 务台；(3)顾客到达系统的时刻是随机的，为每一位 顾客提供服务的时间是随机的，因而整个排 队系统的状态也是随机的。(一)系统特征和基本排队过程l基本排队过程可以用图66表示。从图66

3、可知， 每个顾客由顾客源按一定方式到达服务 系统，首先加入队列排队等待接受服务 ，然后服务台按一定规则从队列中选择 顾客进行服务，获得服务的顾客立即离 开。(二)排队系统的基本组成部分排队系统由3个部分组成1、输入过程2、服务规则3、服务台1输入过程这是指要求服务的顾客是按怎样的规律到达排队系 统的过程，有时也把它称为顾客流。一般可以从3个方 面来描述个输入过程。(1)顾客总体数，又称顾客源、输入源。这是指顾客的 来源。顾客源可以是有限的，也可以是无限的。(2)顾客到达方式。这是描述顾客是怎样来到系统的， 是单个到达，还是成批到达。 (3)顾客流的概率分布，或称相继顾客到达的时间间隔 的分布。

4、这是求解排队系统有关运行指标问题时，首 先需要确定的指标。顾客流的概率分布一般有定长分 布、二项分布、泊松流(最简单流)、爱尔朗分布等若 干种。2服务规则这是指服务台从队列中选取顾客进行 服务的顺序。一般可以分为损失制、等 待制和混合制等3大类。(1)损失制。这是指如果顾客到达排队系 统时，所有服务台都被先到的顾客占用 ，那么他们就自动离开系统永不再来。2服务规则(2)等待制 这是指当顾客来到系统时，所有服务台 都不空，顾客加入排队行列等待服务。等待制中，服务 台在选择顾客进行服务时常有如下四种规则：1)先到先服务。按顾客到达的先后顺序对顾客进行服 务。 2)后到先服务。3)随机服务。即当服务

5、台空闲时，不按照排队序列而 随意指定某个顾客接受服务。4)优先权服务。 2服务规则(3)混合制 这是等待制与损失制相结合的一 种服务规则，一般是指允许排队，但又不允许 队列无限长下去。具体说来，大致有三种：1)队长 有限。当排队等待服务的顾客人数超过 规定数量时，后来的顾客就自动离去，另求服 务，即系统的等待空间是有限的。 2)等待时间有限。即顾客在系统中的等待时间 不超过某一给定的长度T，当等待时间超过T时 ，顾客将自动离去，并不再回来。3)逗留时间 (等待时间 与服务时间 之和)有限。 3服务台l (1)服务台数量及构成形式。从数量上说，服 务台有单服务台和多服务台之分。从构成形式 上看，

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

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

8、长是指系统中正在排队等待服务的 顾客数。队长和排队长一般都是随机变 量。二、排队系统的主要数量指标2等待时间和逗留时间从顾客到达时刻起到他开始接受服务止这段时间称 为等待时间。等待时间是个随机变量。从顾客到达时刻 起到他接受服务完成止这段时间称为逗留时间，也是随 机变量。3. 忙期和闲闲期 忙期是指从顾客到达空闲着的服务机构起，到服务 机构再次成为空闲止的这段时间，即服务机构连续忙 的时间。这是个随机变量，是服务员最为关心的指标 ，因为它关系到服务员的服务强度。与忙期相对的是 闲期,即服务机构连续保持空闲的时间。在排队系统 中，忙期和闲期总是交替出现的。二、排队系统的主要数量指标4数量指标的常

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

10、即每个服务台单位时间内的平 均服务时间，般有=(s)，这是衡量 排队系统繁忙程度的重要尺度，当趋近于0时 ，表明对期望服务的数量来说，服务能力相对 地说是很大的。这时，等待时间一定很短，服 务台有大量的空闲时间；如服务强度趋近于1 ，那么服务台空闲时间较少而顾客等待时间较 多。我们一般都假定平均服务率大于平均到 达率，即/0）0.75020Lq2.25人012人L3人087人W60min174minWq45min24min例3 某医院挂号室有三个窗口，就诊者的到 达服从泊松分布，平均到达率为每分钟0.9人，挂 号员服务时间服从指数分布，平均服务率每分钟 04人，现假设就诊者到达后排成一队，依次

11、向空 闲的窗口挂号，显然系统的容量和顾客源是不限 的，属于M/M/1型的排队服务模型。求：该系统 的运行指标解如果在例3中，就诊者到达后在每个挂 号窗口各自排成一队，即排成3队，且进入 队列后不离开，各列间也互不串换，这就 形成3个队列，而例3中的其它条件不变。 假设每个队列平均到达率相等且为： 1230.9/30.3（人/分钟） 这样，原来的M/M/3系统就变成了3个M/M/1 型的子系统。现按M/M/1型计算主要运行指标，并与 上面的例子进行对比分析，结果见表62表62 两个模型的比较指标（1）M/M/3型（2）M/M/1型挂号间空闲 的概率0.07480.25（各子系统 ） 就诊者必须等

12、待 的概率P(N3)= 0.570.75平均队列长1.7（人）2.25（人） （各子系统） 平均队长3.95（人）9（人） （整个系统） 平均逗留时间4.39（分钟）10（分钟）平均等待时间1.89（分钟）7.5（分钟）练 习 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)顾客到达后的等待概率。