运筹学 100排队论

《运筹学》讲稿：排队论 1

第10章 排队论

第一节 排队服务系统的基本概念

一、排队系统的特性

排队问题的实例：超市付款，自动取款机取款，医院门诊，乘公交车，设备修理。

排队服务系统的要素：顾客源，等待队列，服务机构。

服务系统顾客源输入等待队列服务机构输出

要素的特性： 1. 顾客源

顾客到达的间隔时间：确定、随机(分布类型)； 一次到达人数：单个到达，成批到达； 顾客源：数量无限，数量有限。 2. 等待队列

等待规则：损失制，等待制，混合制；

接受服务顺序：先到先服务，后到先服务，按优先权服务，随机服务。 3. 服务机构

服务台数量：单个，多个；

排列方式：串联、并联、混合排列。 服务时间：固定，随机(分布类型)； 一次服务人数：单人，成批。

三、排队服务系统的分类

按上面所讨论的排队系统各项的特性，可对排队系统作出分类。 通常按如下6方面的特性对排队系统进行分类：

(a／b／c) : (d／e／f)

每个字母代表一个特征，它们分别是： a：顾客到达间隔的分布，有：

M──负指数分布； D──确定型；

《运筹学》讲稿：排队论 2

Ek──k阶爱尔郎分布； GI──一般相互独立的分布。 有：M、D、Ek、G

b：服务时间的分布

c：系统中并联的服务台数，记为S d：系统中最多可容纳的顾客数，1~? e：顾客源总数，为1~? f：排队服务规则

FCFS──先到先服务 LCFS──后到先服务 M／M／1／10／∞／FCFS

用这6个参数我们可以表示出某种类型的排队系统，如： 其中后三项可以省略，这时表示的是：a／b／c／∞／∞／FCFS

三、排队系统的状态及参数

系统状态N(t)——排队系统中的顾客数，包括等待的和正在被服务的。其与系统运行的时刻t相关，且是一个随机变量。

稳定状态——当系统状态与时刻t无关时，称系统处于稳定状态。在系统开始运行的一段时间内，系统状态随时间而变化，在运行一段时间之后，系统的状态将不随时间变化，此时系统即进入稳定状态。排队论主要研究系统处于稳定状态的工作情况，以下参数也都针对于稳定状态进行定义。

系统状态N——系统处于稳定状态时，系统中的顾客数，其是一个随机变量，不随时间变化。

状态概率Pn——系统状态等于n的概率，即P{N?n}。P0,P1,??即构成了随机变量N的概率分布。当系统达到稳定状态时，N的取值仍会发生变化，但N的规律分布将保持不变。

队长——系统中等待服务的顾客数，其等于系统状态减去正在被服务的顾客数，是一个随机变量。

顾客平均到达率?——单位时间内平均到达的顾客数，其为常数。

顾客平均达到间隔1?——相邻两个顾客到达的间隔时间的平均值，也即平均隔多长时间到达一个顾客。

如，顾客的平均达到率??3人/小时，则顾客的平均到达间隔

1??1/3小时?20分钟。

平均服务时间1?——对每个顾客进行服务的时间的平均值，其为常数。 平均服务率?——单个服务台单位时间内平均可服务完的顾客数。

《运筹学》讲稿：排队论 3

如，平均服务时间1??15分钟/人?14小时/人，则平均服务率??4人/小时。

四、排队系统的指标

平均逗留时间Ws——顾客从到达系统到离开系统所经历时间的平均值，逗留时间包括等待时间和服务时间。

平均等待时间Wq——顾客在系统中处于等待状态的时间的平均值。等待时间等于逗留时间减去服务时间。

平均顾客数Ls——系统中顾客人数的平均值，即系统状态的均值

平均队长Lq——系统中处于等待状态的顾客人数的平均值，即队长的均值。 服务强度?——每个服务台处于工作状态的时间占全部时间的比例，也称服务机构的利用率。

五、指标及参数间的关系

(1) LS??nPn

n?1?LS是系统状态N的均值，N是离散型随机变量其分布律为：

N P ?0 P0 1 P1 2 P2 … … n Pn … … 按离散型随机变量均值的计算方法可得该关系。 (2) Lq?n?S?1?(n?S)Pn

Lq是队长的均值。队长等于系统状态减去正在被服务的顾客数，而系统中正在被服务的顾客数总是小于等于服务台的数量S，因而有：

?N?S队长???00 0 P0 1 0 P1 N?S N?S… … … S 0 PS S+1 1 PS+1 … … n n-S Pn … … 可得系统状态的分布律与队长的分布律的对应关系如下： N 队长 P (3) LS??WS

如，一个确定性系统，每分钟到达1人，每人逗留3分钟，则各时刻系统中的顾客数为：

时刻 人数 1 1 2 2 3 3

4 3 5 3 … 3 也即在稳定状态下，系统中始终保持为3人。其符合上述关系式。 《运筹学》讲稿：排队论 4

由该式可得：WS?(4) Lq??Wq

LS?

该式的直观解释与上式类似。可得，Wq?(5) Ws?Wq?1Lq?

?

该式的含义为，平均逗留时间＝平均等待时间＋平均服务时间 将(3)、(4)两式代入(5)可得，Lq?Ls?? ?例一 一个单服务台的排队系统，系统最多容纳4名顾客。当系统处于稳定状态时，系统状态N的分布律为：

N P 0 1/12 1 2/12 2 5/12 3 2/12 4 2/12 求：平均顾客数，平均队长，正在被服务顾客的平均数； 设顾客平均到达率??3人/小时。

求：平均逗留时间，平均等待时间，平均服务时间，平均服务率。 解：平均顾客数LS??nPn?1?n?1??252226?2??3??4???2.17人 121212121252215平均队长Lq?n?S?1?(n?S)Pn?1?12?2?12?3?12?12?1.25人

261511???0.92人 121212正在被服务顾客的平均数?Ls?Lq?若顾客平均到达率??3人/小时，则： 平均逗留时间WS?平均等待时间Wq?LS?Lq?26/1213??0.72小时 318??15/125??0.42小时 31213511???0.3小时 181236平均服务时间1??WS?Wq?平均服务率??36?3.27人/小时 11作业14：P286，10.6，10.1

《运筹学》讲稿：排队论 5

第2节 到达与服务时间的分布

一、顾客到达的分布

顾客的到达过程是一个随机事件流，称为顾客达到流。 顾客达到流一般可视为一个最简单流，亦称泊松流。 最简单流的条件：

(1)平稳性。到达k个顾客的概率仅与时间段的长度t有关，与时间段的起始时刻无关。

(2)无后效性。在不相交的各时间段内达到的顾客数相互独立。

(3)普通性。在足够小的时间段内只能有一个顾客到达，有2个或2个以上顾客同时到达的概率为0。

顾客到达最简单流的性质：

(1) 在时间段t内到达的顾客数服从参数为?t泊松分布，即在时间段t内到达k个顾客的概率为：

vk(t)?e??t(?t)k (k?0,1,2,?) k!其中，?——单位时间内平均达到的顾客数，即顾客平均到达率。 (2) 单位时间内到达的顾客数服从参数为?的泊松分布，即：

vk(1)?e???kk! (k?0,1,2,?)

(3) 顾客到达的间隔时间服从参数为?的指数分布。

概率密度为：f(t)??e??t 分布函数为：F(t)?1?e??t

1?为顾客平均到达间隔时间。

(4) 当?t?0时，有：

v0(?t)?1???t

v1(?t)???tvk(?t)?0(k?2,3,?)

二、服务时间的分布

服务机构对每个顾客的服务时间可认为服从指数分布，

概率密度为：f(t)??e??t 分布函数为：F(t)?1?e??t

指数分布的性质：

(1) 1?为对每个顾客的平均服务时间。

本文来源：https://www.bwwdw.com/article/yjah.html