第2章排队现象建模

第2章排队现象建模2.1排队现象分析2.2排队系统基本构成2.3排队系统的分类与符号2.4排队系统的特性指标2.5

Little公式概要

2.1排队现象分析

排队现象并不仅限于上述电话系统，许多系统的设计中都存在类似的问题。表2.1列举了一些排队现象。

2.2排队系统基本构成

各类服务系统，尽管形式和内容不同，其排队系统都是由顾客到达、在队列排队和服务员服务三部分组成(或又称为：输入过程(arrivalprocess)、排队规则(queuediscipline)和服务规则(servicediscipline))。典型排队系统如图2.1所示，这里使用的“顾客源”和“服务窗”要作广义理解。下面将分别给予介绍。图2.1典型排队系统模型

1.输入过程

输入过程通常可以用如下的三种随机过程来描述，这三者的含义与各自的关系分别如表2.2和图2.2所示。图2.2输入过程的三种随机过程示意图为了便于研究，人们根据到达过程的不同概率特性将其分为如下几类，并给予不同的符号以示区别。

·定长输入(D)：这种输入是指顾客规则的等间隔到达，即每隔时间c到达一个顾客，即tn≡c。显然tn的分布函数为

·Poisson流输入(M)：系统的输入过程{M(t)，t≥0}为Poisson流是指其满足如下四个条件：

①M(t)取值为非负整数，即为计数过程；

②P(M(0)=0)=1，即时间间隔为0时到达系统的人数为0；

③对于任意的0≤a<t+a，每一个增量M(a+t)－M(a)非负，且服从参数为lt(l≥0)的泊松分布，即

k=0，1，2，…

④过程{M(t)，t≥0}具有平稳独立增量性。

·k阶Erlang输入(Ek)：顾客的到达过程{tn，n=1,2,…}是独立同分布的随机变量序列，且tn的概率密度函数为

其中，k称为相位。一般独立输入(G)：也称通用独立输入，顾客的到达过程{tn，n=1，2，…}是独立同分布的非负随机变量序列，其分布函数可以为任意函数，但是其均值有限，且方差存在。

成批到达：顾客一批接一批的相继到达系统，每批顾客的个数可以是常数(通常是正整数)，也可以是一个离散型(通常取非负整数)随机变量，而各批相继到达的时间间隔可以为上述各种分布之一。

2.排队与服务规则

顾客进入排队系统后的排队规则通常有损失制、等待制和混合制三种。

·损失制(无排队队列)：顾客到达时，所有服务台均被占用，则该顾客就离去，永不再来。例如电话系统就属于损失制，当一次呼叫不通，则此次呼叫作废，这次呼叫永远消失(注意：如果再次呼叫被认为与上次呼叫无关)。

·排队制(等待制)：当顾客到达时，所有服务台均被占用，他们就排队等待服务，其排队方式有以下几种。

①单服务台：

√先到先服务，例如数据结构中的队列；

√后到先服务，例如数据结构中的堆栈；

√随机服务，例如摇号抽奖；

√优先权服务，例如银行VIP会员。

②多服务台：常见的是在每个服务台前排成一队或排成公共一队。当服务台有空时，按顺序进行服务。

·混合制：可分为如下三种。

①排队长度(队长)有限：当顾客到达时，若队长已等于规定长度时，顾客离去；若小于规定长度时，则排队。系统不存在超过队长的状态。如医院专家号挂号已满，就不再排队了。

②等待时间有限：顾客在队中排队超过某个时间间隔时，则离去。例如医院血库的血浆、生物制剂等。

③逗留时间(等待时间与服务时间之和)有限，顾客在系统中的逗留时间不得超过确定的时间，例如药品的有效期。

3.服务机构

服务机构通常包括：服务员的个数、服务机构的结构形式(如串联、并联、混联或网络等结构形式)、服务过程等。

图2.3给出了单队列单服务员系统。图2.3单队列单服务员系统这个服务系统的服务方式是这样的。该系统的核心是一个服务员，它负责为顾客提供某种服务。从某顾客群体中到来的顾客来到这个系统要求服务。如果服务员空闲，顾客就立即得到服务，否则到达的顾客就进入等待队列。当服务员服务完一个顾客时，该顾客就离开服务系统。如果等待队列中有顾客，那么一个顾客就被交给服务员。图2.4多服务员队列与多个单服务员队列若以vn表示到达系统的第n个顾客在系统中接受服务的时间，则{vn，n=1，2，…}称为服务过程，可分为如下几类：

·定长服务分布(D)：每个顾客接受服务的时间为正常数c，其分布函数为

·负指数服务分布(M)：此时每个顾客的服务时间v1，

v2，…，vn，…相互独立，并具有相同的负指数分布，其分布函数为

·k阶Erlang服务分布(Ek)：此时每个顾客的服务时间v1，v2，…，vn，…相互独立，并有相同的k阶Erlang分布，其分布函数为

·一般独立服务分布(G)：也称通用独立服务分布，所有顾客接受服务的时间是独立同分布的非负随机变量序列，其分布函数可以为任意函数，但是其均值有限，且方差存在。

2.3排队系统的分类与符号

考虑到排队系统

通常可以由如下七个特征来决定：

(1)顾客的输入过程。

(2)对顾客的服务过程。

(3)服务员的个数。

(4)系统容量(系统内所能允许进入的最大顾客数)。

(5)顾客源的个数。

(6)服务规则。

(7)服务机构的结构形式。于是人们就根据这些特征来划分排队模型。目前通用的是1953年英国数学家D.G.肯达尔提出的“肯达尔模型”，我们称之为经典排队模型。该模型由A/B/C/D/E/F组成，各个符号的含义如图2.5所示。图2.5排队模型-肯达尔记号

例2.1

M/M/c/k排队系统，其含义为：该系统的输入过程{M(t)，t≥0}为Poisson流，因而其顾客源的个数为∞；对每个顾客的服务时间{vn，n=1，2，…}为独立同负指数分布；c个服务员；系统容量为k(k≥1)；顾客进入系统后排成一列，按照先来先服务的原则，由c个服务员并行服务。

例2.2

G/E3/2/∞排队系统，其含义为：该系统的输入过程{tn，n=1，2，…}为一般独立输入；对每个顾客的服务时间{vn，n=1，2，…}为独立同分布，其分布函数为3级Erlang分布；2个服务员；系统容量为∞；顾客进入系统后排成一列，按照先来先服务的原则，由2个服务员并行服务；顾客源的个数为无限。

2.4排队系统的特性指标

具体说来在排队系统的瞬态分析中，人们关心的系统特性指标及其符号如表2.3所示。由表2.3可得出

2.稳态特性指标

稳态分析较之瞬态分析要容易得多(在第3章大家将会看到)，故它是本章介绍的重点。具体说来在排队系统的稳态分析中，人们关心的系统特性指标及其符号如表2.4所示。由表2.4可得出当平稳状态存在时，系统的瞬态特性指标与稳态特性指标存在如下关系

图2.6以单服务员为例，对稳态特性指标进行了图示。图2.6单服务员队列稳态指标

2.5

Little公式概要

对一个排队系统，一般假定满足以下三个条件：

(1)排队系统能够进入统计平衡状态；

(2)服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；

(3)系统中任一顾客不会永远等待，系统也不会永无顾客到达。在上述假设成立时,Little公式(李特尔,JohnD.C.Little)成立，如下所示：当一个顾客到达时，它会发现在它前面排队等待以及系统中正在接受服务的顾客有L个。当它被服务完毕并离开系统时，在系统中排队和接受服务的顾客也有L个。这与系统中平均顾客数L是一致的。另外，已知这个顾客在系统中平均花费的时间是T，且顾客到达速率是