当前位置：文档库 › 第六部分排队论

第六部分排队论

第七部分排队论

第十九章排队论

排队论又称随机服务系统理论，它是通过对各种服务系统在排队等待现象中概率特性的研究，来解决服务系统最优设计与最优控制一门学科。目前，排队论已在计算机系统、计算机通信网络系统、电子对抗系统、交通运输系统、医疗卫生系统、库存管理系统、军事作战系统等方面有着重要的应用，并已成为工程技术人员、管理人员在系统分析与设计中的重要数学工具之一。

§1 排队系统的基本概念

在人们的日常生活中，一个服务系统在工作过程中由于拥挤而产生的排队等待现象是经常发生的.例如，顾客在理发店内等待理发（见图）、用户在电话机前等候通话、发生故障的机器等候工人修理、进入机场上空的飞机等候降落等等。如果我们把服务系统的含义再拓广一下，则进入雷达接收机的信号等待处理、通信系统的报文在缓冲器上等候传送、多微机系统的处理机等候访问公共内存、计算机网的用户等候使用某资源、进入水库的流水等待开闸泄放等等都可看作服务系统在运行过程中所产生的排队等候现象。我们就将这种具有排队等候现象的服务系统通称为排队系统。

任何一个服务系统总是由两个相辅相成的要素：顾客和服务员（或服务台）所构成。凡是要求接受服务的人与物统称为顾客；凡是给予顾客服务的人与物统称为服务员（或服务台）。

对于一个排队系统来说，如果顾客的到达时刻和对顾客的服务时间是固定的话，人们总可以适当安排或调整服务员个数、服务速率，从而使顾客到达后少排队甚至不排队而迅速进入服务，亦即容易达到供求之间的平衡关系，如通常情况下的火车调度就属于以上情况。然而由于客观环境的复杂多变以及种种随机因素的影响，使得在绝大数情况下，顾客到达服务系统的时刻以及对顾客的服务时间都是随机的，这就给服务系统造成了一系列供求之间的矛盾。例如，有时顾客到得多而服务跟不上（供不应求），而另一些时候则由于顾客少（或无顾客）而使服务员处于空闲状态（供过于求）。因此，排队论的主要任务就是：通过对排队系统概率规律性的探讨来寻求某些能达到供求平衡的手段与策略，这也就是排队系统的所谓最优设计与最优控制问题。

（一）排队系统的基本构成

考虑到任何一个顾客通过排队系统总要经过如下过程：即顾客到达、排队等待、接受服务、离去。因此，排队系统的概率规律性显然与如下三个因素有关，这就是：（1）顾客到达规律，（2）顾客排队与接受服务的规则，（3）服务机构的结构形式、服务员个数与服务速率。因此，人们就将上述三个因素称为排队系统的三个基本组成部分。下面将分别给予介绍。

1．输入过程

输入过程是用来刻画顾客到达规律的一种数学描述。通常可用如下的三种随机过程{}0),(≥t t M ，{}"1,2,,=n s n ，{}"1,2,,=n n τ来描述，其中)(t M 表示时间间隔(]t ,0内到达排队系统的顾客数；n s 表示第n 个到达系统的顾客的到达时刻；而0,,01=?=?s s s n n n τ它表示第n 个顾客与其前一顾客相继到达的时间间隔。n n s t M τ,),(之关系见图，并有

{}∑==≤=n i i

n n s t s n t M 1,:max )(τ

为了便于研究，人们根据到达过程的不同概率特性将其分成几类，并给予不同的符号以示区别。

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

???≥<=≤=c t c t t P t A n 1,0,)()(τ

b Poisson 流输入（M ）

：系统的输入过程{}0),(≥t t M 为Poisson 流。一个取非负整数值的随机过程{}0),(≥t t M 称为Poisson 流，是指其满足如下三个条件：

(a)()10(0)==M P

(b) 对于任何,0t s <≤增量)()(),(s M t M t s M ?=有参数为0 ),(>?λλs t 的Poisson 分布。即对于"0,1,2,=k 有

[])(!

)()),((s t k

e k s t k t s M P ???==λλ （1-1） (c) 过程0}),({≥t t M 具有独立增量性。

c k 阶Erlang 输入)(K E ：这种输入是指顾客的到达过程{}"1,2,=τn n 是独立同分布的随机变量序列，且n τ的分布函数为

k t t t e t A k t

1)!()(2!)(1![11)(1

2?λ++λ+λ+?=?λ?", 00,>λ≥t 或其密度函数为

00,,1)!

()()(1

>λ≥?λλ=λ??t e k t t a t k (1-2) d 一般独立输入)(GI ：顾客的到达过程{}"1,2,,=τn n 是独立同分布的非负随机变量序列,n τ分布函数为)(t A 。上面的所有输入都可看作一般独立输入的特例。

e 成批到达输入：顾客一批接一批地相继到达系统，设n s 表示第n 批顾客的到达时刻，1??=τn n n s s 表示各批相继到达的时间间隔。此时，每批顾客的个数L 可以是常数（通常是正整数），也可是一个离散型（通常取非负整数）随机变量，而各批相继到达的时间间隔n τ可为上述各种分布之一，则这种输入就称为成批到达输入。

2．排队与服务规则

排队系统内顾客的排队规则通常有等待制、损失制和混合制三种。当顾客到达时，若所有服务台均被占用，他们并不离去而是排队等待，直到接受服务为止，这种排队规则称为等待制。如通常的观众排队等待买票、乘客排队等候上车等；当顾客到达时，若所有的服务台均被占用，该顾客就自动离去，且永不再来，这种排队规则称为损失制（又称消失制）。如通常使用的损失制电话系统、雷达接收系统等；当顾客到达时，若排队系统的队长小于,N 则顾客就排队等待接受服务（系统内排队等待和正在接受服务的顾客总数称为系统队长）。若排队系统的队长等于,N 则顾客离去且永不再来，这种排队规则称为混合制（确切地说是队长有限混合制）。混合制的排队规则除上述外，还有逗留时间有限制和等待时间有限制等，如出炉的钢水未被及时浇铸将报废、库存的药品超过有效期将被销毁等就是后二种混合制的实例。

当顾客进入排队系统后，其接受服务的规则有先来先服务，后到先服务、优先权服务

和随机服务等。在具有优先权服务规则的排队系统中，进入系统的顾客均有不同的优先级，具有较高优先级的顾客可先于较低优先级的顾客得到服务，而不管他们到达的先后次序。优先级别可以有很多，但同一优先级的顾客若同时处于系统中排队等待时，则他们的服务规则又可以是先来先服务或其它服务规则。

优先权服务规则还可以分为强占型与非强占型两类。在具有强占型优先权服务规则的排队系统中，当新到的顾客其优先级高于正在接受服务的顾客优先级时，必须中断正在进行的服务，转而去给新到的顾客实施服务，只有当该顾客服务结束而系统中又无更高优先级的顾客时，方可再次对被迫中断的顾客进行服务。在具有非强占型优先权服务规则的排队系统中，当具有较高优先级的顾客到达时，正在接受服务的顾客尽管其优先级别较低，但仍需让其服务完成以后，方能从等待顾客中选取具有较高优先级的顾客进行服务。例如某些计算机系统或通信系统具有上述服务规则。

3．服务机构

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

若以n v 表示到达系统的第n 个顾客在系统中接受服务的时间，则{}"1,2 ,=n v n 称为服务过程。设n v 的分布函数为),(t B 服务过程可分成如下几类：

a 定常服务分布)(D ：此时每个顾客的服务时间为一正常数c ，即有分布函数

??≥<=≤=c t c t t v P t B n 当当1,0,)()( b 负指数服务分布)(M ：此时每个顾客的服务时间21,v v …n v …相互独立，并具有相同的负指数分布。其分布函数为

t n e t v P t B μ??=≤=1)()(，0,0>≥μt

c k 级Erlang 服务分布():k E 此时每个顾客的服务时间21,v v …,n v …相互独立，并有相同的k 级Erlang 分布，其分布函数为

00,)1)!

()(2!)(1!(11)(1

2>μ≥?μ++μ+μ+?=?μ?t k t k t k t k e t B k t k "" 其密度函数为

00,,1)!

()()(1

>μ≥?μμ=μ??t e k t k k t b t k k d 一般独立的服务分布)(G ：此时，所有顾客的服务时间相互独立，并有相同的分布函数)(t B 。前面所述的各种服务分布均可看作为一般独立的服务分布的特例。

（二）排队系统的分类与符号

一个排队系统通常可由如下的七个特征来决定：（1）顾客的输入过程，（2）对顾客的服务过程，（3）服务员的个数，（4）系统容量（系统内所能允许进入的最大顾客数）；（5）顾客源的个数，（6）服务规则，（7）服务机构的结构形式，于是人们就根据这些特征来划分排队模型。例如，对于具有多服务员并行服务结构的排队系统，D.G.Kendall 于1953年提出了如下分类符号方案，并得到了认可。该符号方案由F E D C B A /////组成，其中A 代表输入过程类别，B 代表服务时间类别，C 代表服务员的个数，D 代表系统容量（当C D =时，该系统即为损失制，当∞=D 时，该系统为等待制，当∞<

为队长有限混合制），E 代表顾客源的个数（若顾客源为无限源，则该项可以省略不写）

。F 为服务规则（当服务规则为先来先服务时可省略不写）。例如M/M/c/k 系统，其含义为：该系统的输入过程{}0),(≥t t M 为Poisson 流，因而顾客源的个数为∞；对每个顾客的服务时间""n v v v ,2,1为独立同负指数分布；c 个服务员；系统容量为)(c k k ≥；顾客进入系统后排成一列，按照先来先服务的原则，由c 个服务员并行服务。又如∞/2//3E GI 系统，其含义为：该系统的输入过程{}"1,2,,

=τn n 为一般独立输入；对每个顾客的服务

时间""n v v v ,,21为独立同分布，其分布函数为3级Erlang 分布；两个服务员；系统容量为∞；顾客到达后排成一列，按照先来服务的规则，接受两个服务员的并行服务；顾客源的个数无限。

（三）排队系统的特性指标

由于每一个特定的排队系统本质是一个物理系统，故排队系统的分析可采用一般物理系统（如电路系统、机械系统等）的常用分析思路，通常可分为瞬态分析与稳态分析两部分。

1、瞬态特性指标

在一个排队系统中，对于任一时刻t 的队长（系统内的顾客总数），等待队长（系统内等待接受服务的顾客数）以及每一顾客在系统中的等待时间，逗留时间（等待时间与接受服务时间的总和）和服务机构的忙期长度等，不论是顾客还是系统管理人员都是极为关心的。由于上述的系统特性指标绝大多数是随机变量或随机过程，因此人们往往关心它们的概率分布特性与期望特性。具体来说，在排队系统的瞬态分析中，人们关心的系统特性指标及其符号为

t t N :)(时刻系统的队长;

t t N q :)(时刻系统的等待队长;

t t c :)(时刻系统忙的服务员个数；

))(()(j t N P t P j ==：t 时刻系统队长为j 的概率;

[]t t N E t L :)()(=时刻系统的平均队长；

[]

t t N E t L q q :)()(=时刻系统的平均等待队长;

[]t t c E t c :)()(=时刻系统忙的服务员平均数；

t t T :)(时刻到达系统的顾客在系统中的逗留时间;

t t T q :)(时刻到达系统的顾客在系统中的等待时间;

t t V :)(时刻到达系统的顾客在系统中接受服务的时间;

)(:))((),(t T x t T P x t W ≤=的概率分布函数;

)(:))((),(t T x t T P x t W q q q ≤=的概率分布函数;

t t T E t W :)]([)(=时刻到达系统的顾客在系统中的平均逗留时间;

t t T E t W q q :)]([)(=时刻到达系统中的平均等待时间; 显然有

)()()(t c t N t N q +=； ))()(t c t L t L q +=

)()()(t V t T t T q +=； )]([)()(t V E t W t W q +=

此外，与上述特性指标有关的，还有

:)(t M 在(]t 0,内到达系统的顾客数;

:),(t t t M ?+在(]t t t ?+,时间间隔内到达系统的顾客数

:),(t t t V ?+在(]t t t ?+,时间间隔内,系统中服务结束的顾客数

n s 第n 个到达系统的顾客的到达时刻； 1??=n n n s s τ：相继到达时间间隔

:n v 对第n 个到达系统顾客的服务时间.

2、稳定性指标

一个排队系统，在其运行的初始阶段，各特性指标如)(t P i ，)(t L ，)(t c ，),(x t W ，),(x t W q ，)(t W ，)(t W q 等显然都与t 有关，而且一般来说初始条件的影响都比较显著，这一工作阶段称为系统运行的过渡阶段（又称瞬态阶段），但在经过足够长的运行时间后，一些系统的工作状态渐趋稳定，从而使上述各特性指标不再与时间t 有关，而初始条件的影响也显得不那么重要了。此时，我们称该排队系统已由过渡阶段进入稳定状态阶段（或统计平衡状态阶段）。由于稳定性分析较之瞬态分析要容易得多，故它是本章介绍的重点。在排

队系统的稳态分析中，下述指标是人们关心的（以下指标均指在系统达到统计平衡状态后的特性指标，不再一一加以注明）：

N ：系统队长；

q N ：系统等待队长；

:)(j N P P i ==系统队长为j 的概率;

:)(N E L =平均队长；

:)(q q N E L =平均特待队长；

:c 平均忙着的服务员个数;

T ：到达系统的任一顾客在系统中的逗留时间；

q T :到达系统的任一顾客在系统中等待时间;

T x T P x W :)()(≤=的概率分布函数；

q q q T x T P x W :)()(≤=的概率分布函数;

T T E W :)(=的平均值(平均逗留时间)；

q q q T T E W :)(=的平均值(平均等待时间); 显然有

c L L q +=， )(n q v E W W +=

除此之外,还有

忙T ：忙期长度；

)(x T P ≤忙：忙其长度分布；

)(忙T E ：平均忙其长度;

消P ：顾客到达系统时由于不能进入系统而消失的概率;

:λ 单位时间内到达系统的平均顾客数；

:e λ单位时间内到达并进入系统的平均顾客数;

当稳定状态存在时,系统的瞬态特性指标与稳态特性指标之间有关系

j t j t P j N P j t N P lim t P lim =====∞

→∞→)())(()(； L t L lim t =∞→)(； q q t L t L lim =∞

→)(

W t W lim t =∞→)(； q q t W t W lim =∞→)(

§2 Poisson 排队系统(一)

一个排队系统, 若其输入过程为Poisson 流, 服务时间为负指数分布，则称其为Poisson 排队系统。本节主要介绍∞///c M M 与k c M M ///系统的稳态分析内容，但为使读者对瞬态分析内容有所了解，故从最简单的1/1//M M 系统着手。

(一) 1/1//M M 系统

1/1//M M 系统具有下述特性：(1)输入过程{}0),(≥t t M 为Poisson 流,设平均到达率为);0(>λλ(2)对每个顾客的服务时间n v 相互独立, 并有相同的负指数分布, 设平均服务时间有μ/1)(=n v E ，其中0>μ，它表示单位时间内服务完的平均顾客数，又称平均服务率；（3）系统只有一个服务员；（4）系统容量为1，因而一个顾客若能进入系统，必可立即接受服务。而当一顾客在接受服务时，若有其他顾客到达系统，则由于系统容量的限制，这些到达顾客将由于不能进入系统而消失。除上述四个特性外、人们通常还附加下述性质：（5）到达过程}),(,{0t t M ≥与服务过程}1,2,{,"=n v n 相互独立。

1、系统的瞬态特性

设)(t N 表示时刻t 时刻系统的顾客数，容易得知，0} t ),t (N {≥是一个只能取值0与1的随机过程，)(t N 取值的全体记作}1,0{=I 。若记转移概率

),())()((t t t P i t N j t t N P ij ?+===?+

则由全概率公式知

),()()(0000t t t P t P t t P ?+=?+),()(101t t t P t P ?++

下面来计算转移概率),(00t t t P ?+。

由于在0)(=t N 的条件下0)(=?+t t N 这一事件可分解为下述两个互斥事件之和：

（1）在时间间隔],(t t t ?+内无顾客到达。

（2）在时间间隔],(t t t ?+内至少有1人到达并进入系统。与此同时，系统至少服务完一个顾客，且到达并进入系统的顾客数与被服务完的顾客数相同，从而有0)(=?+t t N 。

显然，前者有概率

)o(10)N(t)|0),((t t e t t t M P t ?+??====?+??λλ

利用前述五个系统特性，可得第二个事件之概率

)(0,),(0,),((t t N t t t V t t t M P ?+>?+>?+0))(0==t N )(0),((t N t t t M P >?+=0))(),(0),((0)=>?+>?+?=t N ,0t t t M t t t V P ,0t t t V t t N P >?+=?+?),(0((0))(0,),(=>?+t N t t t M 0))(0,),(0),((0))(0),((=>?+>?+?=>?+≤t N t t t M t t t V P t N t t t M P

)()1)(1(t o e e

t t ?=??=????μλ 于是有

0))(|0),((),(00==?+=?+t N t t t M P t t t P 0),(0,),(0,),((=?+>?+>?++t t t N t t t V t t t M P )o(10))( t t t N ?+??==λ 对于转移概率),(10t t t P ?+，可采用类似的方法计算，考虑到在1)(=t N 的条件下0),(=?+t t t N 这一事件可分解为下述两个互斥事件之和：

（3）在时间间隔],(t t t ?+内无顾客到达，但却服务完一个顾客。

（4）在时间间隔],(t t t ?+内至少有1人到达并进入系统。同时至少服务完二个顾客，且由于服务完之顾客数比进入系统之顾客数多一人，从而有0),(=?+t t t N 。前者有概率

1)),(0,),((=?+=?+t t t V t t t M P )()(1t o t e e t t ?+?=?=????μμλ

后者的概率

)(1,),(0,),((t t N t t t V t t t M P ?+>?+>?+)(1))(0t o t N ?===

因而有

),(10t t t P ?+)(t o t ?+?=μ

利用上述转移概率),(00t t t P ?+与),(10t t t P ?+的计算结果，可得

),()(),()()(1010000t t t P t P t t t P t P t t P ?++?+=?+ )()())(1(10t o t t P t t P ?+?μ+?λ?= 从而有

)()(d )(d 100t P t P t

t P μ+λ?= 类似地有 ),()(),()()(1110101t t t P t P t t t P t P t t P ?++?+=?+

=)())(1()(10t o t t P t t P ?+?μ?+?λ 经整理得

)()(d )(d 101t P t P t

t P μ?λ=

如果该系统初始时刻空闲，即有

1(0)0)(0)(0===P N P 求上述微分方程，容易求得瞬态概率

][1)()(0t e t P μ+λ?λ+μμ+λ=，][1)()(1t e t P μ+λ??μ

+λλ= t 时刻系统的平均队长)(t L 有

][1)]([)()(t e t N E t L μ+λ??μ+λλ== 注意到该系统的容量为1，顾客如果能进入系统，必可立即接受服务。因此，对任何时刻t ，系统的平均等待队长0)(=t L q ，而每一进入系统的顾客的平均等待时间0)(=t W q ，至于t 时刻进入系统的每一顾客，其平均逗留时间为

μ/1)()(==n v E t W

2．系统的稳态特性

所谓系统的稳态特性由§2.1知，是指当系统运行了足够长（∞→t ）时间后，进入统计平衡状态时的状态概率及系统的其他数量指标，如L 、q L 、W 、q W 等。显然有

λ+μμ=

=∞→)(00t P lim P t ， λ+μλ==∞→)(11t P lim P t ， λ+μλ==∞→)(t L lim L t μ

==∞→1)(t W lim W t ， 0)(==∞→t L lim L q t q ， 0)(==∞→t W lim W q t q 并有

0/P W L e λ=μ+λλμ==λ λ为单位时间到达系统的平均顾客数，0P 可看作此时系统空闲的概率，也就是该到达顾客进入系统的概率。综上所述可知，e λ可看作单位时间到达并进入系统的平均顾客数，通常称为有效到达率。

（二）M/M/c/k 系统（c k ≥）

M/M/c/k 系统具有下述特性：（1）输入过程0}),({≥t t M 为Poisson 流，设平均到达率为0)(>λλ；（2）对每个顾客的服务时间n v 相互独立，并有相同的负指数分布，设平均服务时间为μ1/)(=n v E ，其中0>μ; (3) c 个服务员并行服务, 并按照先来先服务的原则提供服务；（4）系统容量为)(c k k ≥，因而该系统的等待空间为c k ?。当顾客达到该系统时，若该系统的队长已到达k ，则此顾客将不能进入系统而消失。故仅当该顾客到达系

统而系统队长小于k 时，该顾客方能进入系统；

（5）到达过程0}),({≥t t M 与服务过程}1,2,,{"=n v n 相互独立。

对于简单系统1/1//M M ，容易求得其瞬态概率)(t P j 。然而对于稍为复杂的排队系统，要想获得其瞬时状态概率并非易事，因此在解决实际问题时，如果能知道该系统统计平衡状态存在或存在的条件，则可直接去求解该系统在统计平衡状态下的状态概率及其它一些特性指标，而不再去求解瞬态特性。为求解上述系统，我们采用生灭过程法。

1．系统的统计平衡特性与队长分布

定理2.1 设)(t N 表示t 时刻系统的顾客数，则在k c M M ///系统中有

（1）0}),({≥t t N 为有限状态生灭过程，其状态空间为},{0,1,2,k I "=，状态转移密度为

1,0,1,2,,?=λ=λk n n "， ???+=μ?=μ=μk

c c n c c n n n ,1,, ,1,1,2,,""

（2）对任何00,>μ>λ，该生灭过程0}),({≥t t N 恒有统计平衡解，且其队长分布))((n t N P lim P t n ==∞

→有 1100!!??==???????ρ+ρ=∑∑c n k c n c n n n c c n P ，???????+=ρ?=ρ=?k c c n P c c c n P n P c

n n n

n ,1,,,!1,1,2,,!00"" （2-1）其中μλ=ρ/。

证明：为验证该过程的生灭过程特性，只需考察该系统在时间间隔),(t t t ?+内的状态转移特性即可。首先注意到该系统的容量为k ，所以任何顾客到达系统时，若发现系统队长已达k 时均将自动离去，因而有转移概率

0),(1,=?++t t t P n n k n ≥， 0),(1,=?+?t t t P n n k n n >=或0

这样，在考虑转移概率),(1t t t P n ,n ?++时，只需讨论1,0,1,?=k n "的情形，至于转移概率),(1t t t P n ,n ?+?，则只需讨论k n ,1,2,"=需的情形。而转移概率),(,t t t P n n ?+，只需讨论k n ,0,1,"=的情形。以下首先来考察转移概率

),())(1)((1,t t t P n t N n t t N P n n ?+==+=?++

在时间间隔],(t t t ?+内，系统在n t N =)(的条件下1)(+=?+n t t N 这一事件可分解为下述两个互斥事件之和：

（1）在],(t t t ?+内有一个顾客到达并进入系统，而正在服务的s 个顾客均未服务完。其中s 与队长n 的关系式为

???+=?===k c c n c c n n n s ,1,,,1,1,2,,00,""

（2-2）（2）在],(t t t ?+内至少来两个顾客，而正在服务的s 个顾客中至少有一人服务结束，且到达的顾客数恰好比服务结束的顾客数多一个，从而有1)(+=?+n t t N 。

前一事件的概率有

)()(n))(|0),(1,),((t o t e te t N t t t V t t t M P s t t ?+?=?===?+=?+????λλμλ 后一事件的概率则有

})( |1n ),(1,),(2,),((n t N t t t N t t t V t t t M P =+=?+≥?+≥?+ )(})(|2),((t o n t N t t t M P ?==≥?+≤

从而有

10,1,2,),(),(1,?=?+?λ=?++k n t o t t t t P n n "

在n t N =)(的条件下1)(?=?+n t t N 这一事件可分解为下述二个互斥事件之和：

（3）在时间间隔],(t t t ?+内无顾客到达，同时在s 个被服务的顾客中恰好服务完一个顾客。

（4）在时间间隔],(t t t ?+内至少到达且进入系统一个顾客，同时在s 个被服务的顾客中至少服务完两个顾客，并使服务完的顾客数比到达且进入系统的顾客数多一个，从而有1)(?=?+n t t N 。

前者有概率

n))(|1),(0,),((==?+=?+t N t t t V t t t M P

1))((11??μ??μ??λ?????

?????=s t t t e e s e

=)(t o t s ?+?μ 后者有概率

)(})(|1)N(t 2,),(1,),({t o n t N n t t t t V t t t M P ?==?=?+≥?+≥?+

从而有

k n t o t s t t t P n n ",1,2,),(),(1,=?+?=?+?μ

在n t N =)(的条件下，n t t N =?+)(这一事件可分解为下述二个互斥事件之和：

（5）在时间间隔],(t t t ?+内无顾客到达，且被服务的s 个顾客均未服务完。

（6）在时间间隔],(t t t ?+内至少有一人到达并进入系统，且在被服务的s 个顾客中至少有一个结束服务，并且进入系统与结束服务的顾客数量相等，从而有n t t N =?+)(。容易求得

0,),((),(,=?+=?+t t t M P t t t P n n 0,),(())(0),(>?++==?+t t t M P n t N t t t V ))()(0,),(n t N n t t N t t t V ==?+>?+k n t o t s ,1,2,),()(1"=?+?μ+λ?= 当0=n 时有

)(1),(00t o t t t t P ?+?λ?=?+

于是有

)(),(1t o t t t P

I j nj ?=?+∑∈

其中，当1,1,2,?=k n "时，1},1,{1+??=n n n I I ，当0=n 时，{0,1}1?=I I ，当k

n =时，}1,{1k k I I ??=。

综上可知，0}),({≥t t N 为有限状态生灭过程，其状态空间},{0,1,2,k I "=，转移密度为

1,0,1,2,,?=λ=λk n n "， ?

??+=μ?=μ=μk

c c n c c n n n ,1,, 1,1,2, ""

所以，恒有统计平衡解，将上述计算的转移密度代入下式可得

???????+=ρ?=ρ=μμμλλλ=????k c c n P c c c n P n P P n n n n n n n n ,1,,,!1,1,2,,!0c

011021"""" ∑∑∑?==?=?ρ+ρ=μμλλ+=1011010!!111c n k c n c n n n k N N N c

c n P "" 2．系统的数字特征

定理2.2 在k c M M ///系统中，设μλ=ρ/，μλ=ρc c /，0c !P c P c ρ=

，则该系统

在统计平衡状态下有如下数字特征 ???

????=ρ?+?≠ρρ?+ρ+??ρ?ρ=+??12)1)((1])(1)([1)(112c c c c k c c k c c c c q c k c k P c k c k P L （2-3）

)(1k e P ?λ=λ， )(1k P c ?ρ=， c L L q +=， k

P P =消其中消P 为顾客到达系统时，由于不能进入系统而自动消失的概率。

证明当系统达到统计平衡状态后，若系统队长c N ≤时，其等待队长应有0=q N ，

仅当队长)(0c k l l c N ?≤<+=时，方有等待队长0>=l N q ，故知等待队长q N 有分布列 ∑∑======c

j c j q P j N P N P 0j 0)(0)(，c k l P l c N P l N P l c q ?≤<=+===+0 ,)()(

从而当1≠ρc 时有

∑∑∑∑?=?=?=++?=ρ=ρ====c k n c

k n c k n n

c c n c n n

c c k n q q n P P c c n nP n N nP L 00000!)( 而

]]'11[]'[100c

c k c c c k n n c

c c k n n c c n n ρρρρρρ

ρ??==+??=?=∑∑ 12-1)(1)1([)

(1+??+?+???=

c k c c c k c c c c k ρρρρρ 所以 ])(1)([1)(112+??ρ?+ρ+??ρ?ρ=c k c c k c c c c

q c k c k P L 当1=ρc 时，容易推得

)1)((0c k c k P n P L c n c c k n c

q ?+?=ρ=∑?=? 考虑到有效到达率表示单位时间内到达并进入系统的平均顾客数，它应等于单位时间到达系统的平均顾客数λ乘以每一到达顾客能进入系统的概率)(k N P <，因此有

)(1)(k e P k N P ?λ=<λ=λ

此外，当系统达到统计平衡状态时，单位时间进入系统的平均顾客数应与单位时间离开系统（由于服务结束才离开的）的平均顾客数相等，前者为e λ，而后者应等于μc ，故有等式

μ?=?λ=λc P k e )(1 由此可得

)(1k e P c ?ρ=μ

λ=， c L L q += 至于k P P =消则是显然的。在k c M M ///系统中，

由前知当k c <时，该系统为混合制排队系统，特殊地当k c =时，该系统为损失制排队系统，容易得到损失制排队系统的如下结果。

定理2.3 在c c M M ///系统中有统计平衡解

c n P n P n

n ,1,2,,!0"=ρ=， 1c n n

n [P ?=∑ρ=00!

（2-4）

c P P =消, 0==q q W L , )(1c P L c ?ρ== 3．应用

例2.1 电话站有n 条线路，同时可供n 对用户进行通话。设用户呼唤流为Poisson 流，平均到达率2=λ次/分，每个用户的通话时间服从负指数分布，平均服务率2=μ次/分。试求在系统达到统计平衡状态后，任一用户电话打不通的概率小于0.01时所需的最少线路数c ，以及此时对应的电话站平均占用线路数c 。

解在通信理论中，当某用户要求通话时，若该电话站的c 条线路均占线时，该用户可视作自动消失，而当其再次要求通话时，可看作另一新用户的到达。在上述意义下，用户呼唤流经统计检验，符合Poisson 流的统计特性。因此，我们可将电话站视作c c M M ///系统，且该系统有2=λ次/分，2=μ次/分，从而有1=ρ，注意到 P(顾客打不通）=)!12!

11!1(1!1!!0c c n c P P c n n c

c ++++=ρρ==∑="消分别以",3,2,1=c 代入上式，经计算可得表。 c 1 2 3 4

5 c P 0.5 0.2

0.0625 0.01538 0.003

可知，当5=c 时满足条件P(顾客打不通）=01.05

0.9951)(15=?=?ρ=P P c c

亦即在五条线路中，忙的平均数仅为一条。

例2.2 某机场有两条跑道，飞机的到达与起飞过程可看作Poisson 流，平均到达率10=λ架次/天。飞机在起飞与降落时将占用跑道，并由机场的一台专用设备对其装卸货物。设飞机占用跑道的时间（主要是装卸货物的时间）服从负指数分布，平均占用率30=μ架次/天。为改进该民航系统的服务效率，管理者拟定了甲、乙两种方案，其中甲方案为增加一条跑道，但不改变λ与μ；乙方案则改变跑道的平均占用率，将其由30=μ架次/天提高到40=μ架次/天，但不改变λ与跑道数。（1）若不考虑费用问题，问应取何种方案？

（2）若将平均到达率增加到30=λ架次，又应取何种方案为好？

解如果将飞机到达机场时，由于跑道已被占用而飞往邻近机场看作自动消失，并将机场装卸设备作为服务员，跑道数k 看作系统容量，则该民航系统为k M M /1//系统。由于不考虑费用问题，故选取的目标函数是单位时间到达并进入系统的平均架次e λ最大。利用（2-3）、（2-4）结果并取1=c ，可得

???????=ρ+λ≠ρρ?ρ?λ=????????????ρ

+ρ?λ=?λ=λ+=∑1 ,1

1 ],11[11)(111k k P k k k n n k k e （1）当采用甲方案与乙方案时，其对应的系统模型及有关参数计算结果见下表。可知，采用甲方案时9.75=λe 架次/天，采用乙方案时9.5=λe 架次/天。比较上述两种方案的，

题，还是取目标函数e λ最大，则采用甲、乙方案时的有关参数及e λ的计算值列于下表。易知，此时应取乙方案为好，即拟采用提高跑道平均占用率到40=μ架次/天的途径。

方案对应系统 c k λ μ ρ λ（架次/天）

甲 3/1//M M

1 3 30 30 1 22.5

该系统有如下特性：（1）输入过程0}),({≥t t M 为Poisson 流，设平均到达率为)0(>λλ。（2）对每个顾客的服务时间n v 相互独立，并有相同的负指数分布。其平均服务时间为μ=1/)(n v E 。（3）c 个服务员并行服务（1≥c ），并遵守先来先服务的原则。（4）系统容量为∞，因而该系统的等待空间亦为∞，从而使每一到达系统的顾客总能进入系统，或接受服务，或排队等待。（5）到达过程}0),({≥t t M 与服务过程}1,2,,{"=n v n 相互独立。

1．系统的统计平衡特性与队长分布

定理2.4 设)(t N 表示t 时刻系统的顾客数，则在∞///c M M 系统中有

（1）0}),({≥t t N 为可列状态生灭过程，状态空间},2,1,0{"=I ，并有转移密度

"0,1,2, ,=λ=λn n ， ??

???++=μ?=μ==μ""2,1,, ,1,1,2, ,0 0,c c c n c c n n n n

（2）生灭过程}0),({≥t t N 有统计平衡解的充要条件为1/<μλc 。当该条件满足时，有队长分布

∑?=ρ?ρ+ρ=100)/(1!!

1c n c n c c n P ，???????++=ρ?=ρ=?"""2,1,, ,!11,2, ,!00c c c n P c c c n P n P c n n n

n （2-5）其中μλ=ρ/。

证明（1）只须在时间间隔),(t t t ?+内来考察该过程的转移概率特性即可。应用与定理2.1类似的思路，可知有

})(|1)({),(1,n t N n t t N P t t t P n n =+=?+=?++

})(|0),(1,),({n t N t t t V t t t M P ==?+=?+= 2,),((≥?++t t t M P ))(1)(1,),(n t N n t t N t t t V =+=?+≥?+

"0,1,2,),(=?+?λ=n t o t

而正在服务的顾客数s 与对长n 的关系为 ??

???+=?===""1,, ,1,1,2, , 0 0c c n c c n n n s

})(1)({),(1,n t N n t t N P t t t P n n =?=?+=?+?)(t o t s ?+?μ=

???+=?+?μ?=?+?μ="

"1,,),(1,1,2,),(c c n t o t c n t o t n

=?+),(t t t P nn "0,1,2, ),()(1=?+?μ+λ?n t o t s

从而有

)(),,(t o t t t P

I j nj ?=?+∑∈

其中当0=n 时，{0,1}1?=I I ，当 1>n 时有1},1,{1+?=n n n I 。综上可知，0}),({≥t t N 为可列状态生灭过程，并有转移密度

"0,1,2, ,=λ=λn n ， ???+=μ?=μ=μ"

"1,, ,1,1,2, ,c c n c c n n n

（2）略。

此外，在（2-1）中令∞→k ，可得（2-5）式。

2．系统的数字特征与等待时间分布

定理2.5 在∞///c M M 系统中，设0P !

,/ ,/c P c c

c c ρ=μλ=ρμλ=ρ，则当1c <ρ时，有

c c c q P L 2)(1ρ?ρ=， ρ=c ， c L L q += （2-6）

证明当系统达到统计平衡状态时（即1c <ρ时），仅当队长c n N >=时，才有等待队长，并有分布列

q N 0 1

2 … k … )(k N P q = ∑=c n n P

0 1+c P

2+c P … k c P + … 于是，平均等待队长有

∑∑∑∞=+∞=+∞=ρ====000

0!)(k k k c k k

c k q q P c c k kP k N kP L 2000)(1!c

c c k k c c k k c P k P c k P c ρ?ρ=ρ=??????ρρ=∑∑∞=∞= 此外，当系统达到统计平衡状态时，单位时间进入系统的平均顾客数应与单位时间离开系统的平均顾客数相等，前者为λ，而后者为μ?c ，从而有μ?=λc ，于是可得ρ=c 。等式c L L q +=的物理意义是明显的。

定理2.6 当1/<μλc 时，∞///c M M 系统在进入统计平衡状态后，每一顾客在系统中的等待时间q T 有分布函数

)(111)()(c t c c c q q e P t T P t W ρ?μ?ρ??

=≤= 0≥t 并有

(1)(c c q q c P W T E ρ?μ==， μ+==1)(q W W T E （2-7） 3．应用

例2.3 某大城市的计算中心需购买计算机，有两个方案可供选择：

方案甲购买一台大型机集中使用。

方案乙购买n 台小型机分散使用（分散使用的含义可认为是将原来大型机的用户平均分给n 台小型机。因而若设到达大型机的顾客流是平均到达率为λ的Poisson 流，则到达每台小型机的顾客流仍可看作Poisson 流，但平均到达率为n /λ）。

若设大、小型机对每个用户的服务时间均服从负指数分布，但大型机平均服务率为μ，小型机为n /μ，并设1/<μλ。试问在两个方案费用基本接近的情况下，选择哪一种方案为好？

解设大型机系统为排队系统I，n 台小型机构成的系统为排队系统II，则系统I 为∞/1//M M 系统，平均到达率λλ=1，平均服务率μμ=1。系统II 由n 个∞/1//M M 子系统构成，其中每个子系统的平均到达率n /2λλ=，平均服务率n /2μμ=。注意到系统I 的利用率1ρ与系统II 的利用率2ρ有1/21<μλ=ρ=ρ，故可利用（2-6）与（2-7）

得下表。观察可知，系统II 的平均等待队长，每个顾客在系统中的平均逗留时间以及平均等待时间均为系统I 的n 倍，显然系统II 的服务效率低于系统I 的服务效率，故应采用方

该售票口对每个观众的售票时间服从负指数分布，每张票的平均售票时间为20秒钟。试问：

（1）若有一球迷于开赛前2分钟到达售票口，并设买票后尚需1.5分钟才能找到座位。求该球迷在比赛开始前找到座位的概率。（2）若该球迷希望有99%的把握在比赛开始前找到座位，则他最迟应提前多少分钟到达售票口？

解若将体育馆售票系统看作一排队系统，由题意知为∞/1//M M 系统。且该系统的平均到达率1=λ人/分。平均服务时间3/1/1=μ分/人，即3/1=ρ，从而知该系统能达到统计平衡状态。

（1）设系统达到统计平衡状态后，每一球迷在售票口前的逗留时间为T ，可以求得)(11)()(ρ?μ??=≤=t e t T P t W ，0≥t 。则易知球迷在比赛开始前能找到座位的充要条件为0.5≤T 分，因而有

0.6321)(=?=≤?1e 15.0T P

（2）欲使0.99)(=≤t T P ，应有01.02=?t e ，

可解得3026.2=t 分，即需提前3.8026分到达。

§2.3 Poisson 排队系统（二）

R c M M ///和∞///c M M 是Poisson 排队系统中的基本模型，其基本特点除输入为Poisson 流、服务为负指数分布外，其排队与服务采用串行排队，并行服务和先来先服务规则进行工作。显然，这种方式在日常生活和工作中是常见的。然而随着排队论应用范围的不断拓广，尤其是排队论在计算机系统、通信系统、交通运输系统以及军事作战系统中的广泛应用，由于这些系统物理背景的特殊性，出现了众多与前述系统有显著不同的各种排队系统。如优先权排队系统、串并联或网络结构的排队系统、有限源排队系统、有限等待时间制排队系统及各种反馈规则的反馈排队系统等等。本节仅选择其中的部分内容来介绍它们解决问题的基本思想与方法。

（一）概率守恒原理

定理 3.1 设{}T t t X X T ∈= ),(为具有有限状态空间的齐次马氏过程，状态空间{}k I , 1, 0,"=，其转移密度矩阵为11)(+×+=k k ij q Q 。若T X 的所有状态互通，则T X 的平稳分布{} I j ,∈j P 必存在，并满足方程组

I i q P q P I k i k ki k

I j i j j i i ∈=∑∑∈≠∈≠ （3-1）

（3-1）的概率含义：左边和式表示达到统计平衡状态后，系统从状态i 转移到其他状态的转移速率。右端和式表示在达到统计平衡状态后，系统从其他状态转移到状态i 的转移速率。即

系统自状态i 离开的转移速率和=系统进入状态i 的转移速率和。

上述等式称为概率守恒原理。概率守恒原理与物理学中的基尔霍夫定律是极其相仿的。

后者说明，当电流达到恒稳状态时，对于电路网络的每一节点i 而言，在任一时刻流入节点i 的电流强度（速率）和等于自i 流出的电流强度和。

一个有限状态齐次马氏过程} ),({T t t X X T ∈=经验证得知能达到统计平衡状态时，利用上述概率守恒原理很易求出其平稳分布} ,{I j P j ∈，作法如下：

（1）求出T X 的转移密度矩阵)(ij q Q =。然后，画出其对应的转移密度图。

（2）在转移密度图中，对于每一个选定的状态i ，观察其流入i 与流出i 的密度及其状态，并根据概率守恒原理，写出该状态应满足的稳态方程。

（3）依次观察状态空间I 中的每一状态，并按照（2）的方法逐个写出其应满足的稳态方程，从而可得到方程组（3-1）。

（4）求解如下方程组，即可得平稳分布} ,{I j P j ∈

???????=∈=∑∑∑∈∈≠∈≠I

j i I k i k ki k I j i j ij i P I i q P q P 1 , 例 3.1 设齐次马氏过程}{, ),(T t t X X T ∈=有状态空间}2 1, ,0{=I 及转移密度

图，试求其统计平衡解（其中0 0,>μ>λ）。

解可判别出I 的所有状态互通，故T X 为不可约的有限状态齐次马氏过程，其平稳分布存在。对每一状态2 1, ,0。依次运用概率守恒原理，可获得下列的差分方程组

?????λ+=μμ+λ=μ+λμ=+λλλ

1222112)()(P P P P P P P P o

o o

将上述方程组与条件1210=++p p p 联立，可解得

?????

??????μλ+μλ+=μλ+μλ=μλ=2002201)(23211])(232[23P P P P P （二）具有消失制的成批到达排队系统

考虑一个[]

/4/4/2M M 系统，它有如下特性：（1）顾客的相继到达时间间隔,,21ττ…，n τ…独立同负指数分布，0,,1/)(>λλ=τn E 但在每一到达时刻来的不是一个顾客，而是一批顾客（其中每批均为两个顾客）。（2）对每个顾客的服务时间用" ,21v v n v …独立同负指数分布，o v E n >μμ=,1/)(。（3）4个服务员，顾客到达后排成一列，按照先来先服务的原则并行实施服务，同批到达的顾客可任意指定先后。（4）系统容量为4，即无等待空

间，因此顾客到达时，若得不到服务均将自动消失。（5）到达过程{=τn n ,1，2，…}与服务过程{=n v n ,1，2，…}相互独立。

上述系统的物理背景是，一个由4座防空武器组成的防空系统。每座防空武器均有一定战斗性能，可以射击一定飞行高度上的空中目标，且同一时间内只能射击各自瞄准的一个目标。而敌机以机群方式实施空袭，机群到达流为Poisson 流，空袭密度为λ，每批机群均为两架，每座防空武器对目标的发射时间均服从负指数分布，平均发射率为μ，且每

座武器射击后能击落目标的概率为)0(>p 。

显然，上述防空系统即为一个[]

4/4//2M M 系统。为了衡量该系统的性能好坏，人们通常要计算该防空系统的两个效率指标：敌机的突防概率及被击落敌机的平均数。

设)(t N 表示t 时刻系统的顾客数（t 时刻进入防区的敌机数）。易知0}),(≥t t N {为有限状态齐次马氏过程，状态空间I={0，1，2，3，4}，并有转移密度图。又所有状态互通，

因而这是一个不可约的有限状态齐次马氏过程，其平稳分布恒存在。

由概率守恒原理可写出其稳态方程组

???????????=+λ=μμ+λ=μ+λμ+λ=μ+λμ=μ+λμ=λ∑=4

032441330221101)(44)3(3)2(2)(j j P P P P P P P P P P P P P P

由λ=4批/分，μ=2架/分，P=0 .8代入上述方程组，则得

7560=

P ，2541=P ，2562=P ，1543=P ，75

194=P 故可得 0.25375

194≈==P P 突防平均击落敌机架数=L×P=∑==400.8n n nP

p ×2.453≈2架

（三）具有串、并联服务结构形式的有限源优先排队系统

考虑一个具有如下服务结构形式的有限源排队系统，它具有下述特性：（1）系统内有m 个顾客，每个顾客均有一定的优先级，其优先级为1，2，…，m 。每个顾客需循环反复地接受二级串联服务（即每一顾客在完成I 级服务后将进入II 级服务站，当完成II 级服务后又将回到I 级接受服务，如此往返循环）。（2）I 级服务站无等待空间，但有m 个服务员

并行服务，且第i 个服务员只能对第i 个优先级的顾客服务，

其服务时间服从参数为)0(>i λ的负指数分布，i =1，2，…，m ；II 级服务站仅有一个服务员，但有m -1个等待座位。到达II 级服务台的顾客按其优先级大小顺序排成一列，接受非强占型优先权服务，服务时间均服从参数)0(>μ的负指数分布。上述服务的结构形式见图。（3）I 级服务站对各顾客的服务时间，II 级服务站对各顾客的服务时间以及两级服务之间均相互独立。

上述排队系统的物理背景是一个多微机处理系统。该系统由m 个微处理机、一条总线及一个公共存贮器构成。第i 个微处理机对其自身专用内存的处理时间服从负指数分布，平均处理时间为1/i λ，i =1，2，…，m 。当该处理机对专用内存完成了一个负指数分布处理时间后，就需通过总线去访问公共内存。此时设第i 个微处理机对公共内存访问的优先级别仍为i ，则当其希望访问公共内存时，若公共内存已有其他微处理机占用，该微机处理机就将按照优先级别顺序排队，并接受非强占型服务。而一旦完成了对公共内存的访问的，它又将开始对自身的专用内存访问，如此往复循环……。一般来说各处理机对各自的专用内存处理时间，对公共内存访问时间以及两者之间均相互独立。为了衡量上述多微处理机系统的性能优劣，通常要计算该系统的处理能力A，其中A 表示I 级服务站的平均队长（处理专用内存的平均处理机数）。下面我们就m =2来计算该系统的处理能力A。

当m =2时，设N(t )=(j i ,)，其中i 表示t 时刻正在接受II 级服务的顾客序号（正在访问公共内存的微处理机序号），j 表示t 时刻正在II 级排队的微处理机序号。若0i =或0=j ，表示II 级空或II 级无排队。容易看出{}0),(≥t t N 是一个有限状态的齐次马氏过程，有状态空间I={（0，1），（1，0），（2，0），（1，2），（2，1）}。根据题意可以计算出转移密度ij q ，并得到转移密度图。注意到该过程的所在状态互通，因而是不可约的有限状态齐次马氏过程，其统计平衡解必存在，即有

∑

∈∞→=∈==I

j i ij ij t P ,I j i P j i t N P lim ),(1),( ,)),()((

由概率守恒原理，列出下述稳态方程组，有

???????????=++++λ=μλ=μμ+λ=μ+λμ+λ=λ+μμ+μ=λ+λ1

)()()(21122010002012110212

120022012100110220100021P P P P P P P P P P P P P P P P P P 求解上述方程组，可得系统处理能力

A=2-II 级服务站的平均对长=[])2(221122010p p P P +++?

（四）服务速率依赖于队长的排队系统

考虑一个服务速率依赖于队长的排队系统，它具有如下系统特性，（1）顾客的到达流

{0}),(≥t t M 为Poisson 流，平均到达率0>λ。（2）对每个顾客的服务时间相互独立，且均服从负指数分布。但其服务速率依赖于队长。当队长小于M 时，其服务速率为1μ，当队长达到或超过M 时，则采用服务速率2μ，其中M 为定数，o >>12μμ。（3）系统有一

个服务员。到达顾客排成一列按照先来先服务的原则接受服务。（4）系统容量为∞。

（5）到达过程与服务过程相互独立。

上述系统的物理背景是一个自动加工机的控制优化问题。设该自动加工机的产品到达为Poisson 流，平均到达率为λ，而机器对产品的加工时间相互独立，并服从负指数分布。为了提高生产效率，工程技术人员将产品加工速率分成二档：当队长小于控制量M 时，采用慢加工速率,1μ 当队长达到或超过控制量M 时，采用快加工速率)0(122>>μμμ。对于上述系统，人们关心的是如何确定控制量M ，以使系统在单位时间内所耗费的期望服务总费用达到最小。

为解决上述问题，设系统的服务费用分为两部分：（1）加工费用与平均加工速率μ成

正比，单位时间内采用单位加工速率的加工费为a ；

（2）产品逗留损失费与平均队长L 成正比，每个产品在系统内逗留单位时间的损失费为b 。因而单位时间内系统所耗费的期望服务总费用为

)()()(M bL M a M G +μ=

为求出使)(M G 达到最小的M ，关键在于计算)(M μ与)(M L 。为此，可设)(t N 表示t 时刻该系统的顾客数（等待加工与正在加工的产品数），则过程}0),({≥t t N 为可列状态生灭过程，有},2,1,0{"=I ，及转移密度

??????++=μ=μ=μ=λ=λ"""2,M 1,M M,n ,1-M 2, 1,n ,2, 1, 0, ,21n n n 当需1,/22<μλ=ρ 该生灭过程有统计平衡解

?????+=ρρ?=ρ=μμμλλλ=+?????""""1,,,12, 1, ,012

110101021M M n P M n P P P M n M n 1n n n n n 其中221/ ,μλ=ρμλ=ρ1/， ??????ρ?ρρ+ρ?ρ?=??????μμμλλλ+=??∞=???∑21121111102101111M 1

M n n n n n P "" （3-2）

由此可得平均队长

∑∑∑∞

=∞=+???=??

????ρρ+ρ==0M 12111010)(n n M n M M n n n n n P nP M L )(d d )(d d 222211101101??????ρρρρρ+??????ρρρ=∑∑∞=??=n M n M n M n P [][]??

????ρ?ρ?+ρρ+ρ?ρ?ρ?+ρ=??2221122111110)(1)(1)(11)(1M M M M P M M M 至于平均服务率，有 ∑∑∑∞=?==μ+μ=μ=μμ=μM

n n M n 2n 1n n n P P P M 1

021)()( 0221121110121121011111 P P M M m n M n M M n n ?????

?ρ?ρρμ+ρ?ρ?μ=??????ρρμ+ρμ=?∞=????=∑∑

其中o P 由（3-2）确定。

将上述计算的)(M L 与)(M μ代入)()()(M bL M M G +αμ=，

即可得)(M G 关于控制量M 的具体函数表达式。在此函数表达式中，由于21,,μμλ均为已知，故只需将控制变量M 作为未知量，利用最优化问题的数值法来确定最优值*M 即可。

第六章排队论

第六章排队论模型排队论起源于1909年丹麦电话工程师A. K．爱尔朗的工作，他对电话通话拥挤问题进行了研究。1917年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理论的几个问题的解决”。排队论已广泛应用于解决军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机性。可以说排队现象几乎是不可避免的。排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展的一门学科。它研究的内容有下列三部分：（i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。（ii）最优化问题，又分静态最优和动态最优，前者指最优设计。后者指现有排队系统的最优运营。（iii）排队系统的统计推断，即判断一个给定的排队系统符合于那种模型，以便根据排队理论进行分析研究。这里将介绍排队论的一些基本知识，分析几个常见的排队模型。 §1 基本概念 1.1 排队过程的一般表示下图是排队论的一般模型。一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统。对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。因此，顾客总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。 1.2 排队系统的组成和特征一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如下： 1.2.1 输入过程输入过程是指顾客到来时间的规律性，可能有下列不同情况：（i）顾客的组成可能是有限的，也可能是无限的。（ii）顾客到达的方式可能是一个—个的，也可能是成批的。

排队论习题及答案

《运筹学》第六章排队论习题 1. 思考题（1）排队论主要研究的问题是什么；（2）试述排队模型的种类及各部分的特征；（3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义；（4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念；（5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分布的主要性质；（6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系与区别。 2．判断下列说法是否正确（1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布；（2）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分顾客合起来的顾客流仍为普阿松分布；（3）若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序，则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布；（4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流；（5）在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大量实际系统的统计研究，这样的假定比较合理；（6）一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后，系统将进入稳定状态；（7）排队系统中，顾客等待时间的分布不受排队服务规则的影响；（8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间少于允许队长无限的系统；（9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有关，当服务时间分布的方差越大时，顾客的平均等待时间就越长；（10）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。 3．某店有一个修理工人，顾客到达过程为Poisson 流，平均每小时3人，修理时间服从负指数分布，平均需19分钟，求：（1）店内空闲的时间；（2）有4个顾客的概率；（3）至少有一个顾客的概率；（4）店内顾客的平均数；（5）等待服务的顾客数；（6）平均等待修理的时间；（7）一个顾客在店内逗留时间超过15分钟的概率。 4．设有一个医院门诊，只有一个值班医生。病人的到达过程为Poisson 流，平均到达时间间隔为20分钟，诊断时间服从负指数分布，平均需12分钟，求：（1）病人到来不用等待的概率；（2）门诊部内顾客的平均数；（3）病人在门诊部的平均逗留时间；（4）若病人在门诊部内的平均逗留时间超过1小时，则医院方将考虑增加值班医生。问病人平均到达率为多少时，医院才会增加医生？ 5．某排队系统只有1名服务员，平均每小时有4名顾客到达，到达过程为Poisson 流，，服务时间服从负指数分布，平均需6分钟，由于场地限制，系统内最多不超过3名顾客，求：（1）系统内没有顾客的概率；（2）系统内顾客的平均数；

排队论模型

排队论模型排队论也称随机服务系统理论。它涉及的是建立一些数学模型，藉以对随机发生的需求提供服务的系统预测其行为。现实世界中排队的现象比比皆是，如到商店购货、轮船进港、病人就诊、机器等待修理等等。排队的内容虽然不同，但有如下共同特征：有请求服务的人或物，如候诊的病人、请求着陆的飞机等，我们将此称为“顾客”。有为顾客提供服务的人或物，如医生、飞机跑道等，我们称此为“服务员”。由顾客和服务员就组成服务系统。顾客随机地一个一个（或者一批一批）来到服务系统，每位顾客需要服务的时间不一定是确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时候服务员又空闲无事。排队论主要是对服务系统建立数学模型，研究诸如单位时间内服务系统能够服务的顾客的平均数、顾客平均的排队时间、排队顾客的平均数等数量规律。一、排队论的一些基本概念为了叙述一个给定的排队系统，必须规定系统的下列组成部分：输入过程即顾客来到服务台的概率分布。排队问题首先要根据原始资料，由顾客到达的规律、作出经验分布，然后按照统计学的方法（如卡方检验法）确定服从哪种理论分布，并估计它的参数值。我们主要讨论顾客来到服务台的概率分布服从泊松分布，且顾客的达到是相互独立的、平稳的输入过程。所谓“平稳”是指分布的期望值和方差参数都不受时间的影响。排队规则即顾客排队和等待的规则，排队规则一般有即时制和等待制两种。所谓即时制就是服务台被占用时顾客便随即离去；等待制就是服务台被占用时，顾客便排队等候服务。等待制服务的次序规则有先到先服务、随机服务、有优先权的先服务等，我们主要讨论先到先服务的系统。服务机构服务机构可以是没有服务员的，也可以是一个或多个服务员的；可以对单独顾客进行服务，也可以对成批顾客进行服务。和输入过程一样，多数的服务时间都是随机的，且我们总是假定服务时间的分布是平稳的。若以ξ 表示服务员为 n }，n=1，2，…第n个顾客提供服务所需的时间，则服务时间所构成的序列{ξ n 所服从的概率分布表达了排队系统的服务机制，一般假定，相继的服务时间ξ ， 1ξ2，……是独立同分布的，并且任意两个顾客到来的时间间隔序列{T n}也是独立的。如果按服务系统的以上三个特征的各种可能情形来对服务系统进行分类，那么分类就太多了。因此，现在已被广泛采用的是按顾客相继到达时间间隔的分布、服务时间的分布和服务台的个数进行分类。研究排队问题的目的，是研究排队系统的运行效率，估计服务质量，确定系统参数的最优值，以决定系统的结构是否合理，设计改进措施等。所以，必须确

(完整word版)《运筹学》_第六章排队论习题及_答案

《运筹学》第六章排队论习题转载请注明 1. 思考题（1）排队论主要研究的问题是什么；（2）试述排队模型的种类及各部分的特征；（3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义；（4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念；（5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分布的主要性质；（6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系与区别。 2．判断下列说法是否正确（1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布；（2）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分顾客合起来的顾客流仍为普阿松分布；（3）若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序，则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布；（4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流；（5）在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大量实际系统的统计研究，这样的假定比较合理；（6）一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后，系统将进入稳定状态；（7）排队系统中，顾客等待时间的分布不受排队服务规则的影响；（8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间少于允许队长无限的系统；（9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有关，当服务时间分布的方差越大时，顾客的平均等待时间就越长；（10）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。 3．某店有一个修理工人，顾客到达过程为Poisson 流，平均每小时3人，修理时间服从负指数分布，平均需19分钟，求：（1）店内空闲的时间；（2）有4个顾客的概率；（3）至少有一个顾客的概率；（4）店内顾客的平均数；（5）等待服务的顾客数；（6）平均等待修理的时间；（7）一个顾客在店内逗留时间超过15分钟的概率。 4．设有一个医院门诊，只有一个值班医生。病人的到达过程为Poisson 流，平均到达时间间隔为20分钟，诊断时间服从负指数分布，平均需12分钟，求：（1）病人到来不用等待的概率；（2）门诊部内顾客的平均数；（3）病人在门诊部的平均逗留时间；（4）若病人在门诊部内的平均逗留时间超过1小时，则医院方将考虑增加值班医生。问病人平均到达率为多少时，医院才会增加医生？ 5．某排队系统只有1名服务员，平均每小时有4名顾客到达，到达过程为Poisson 流，，服务时间服从负指数分布，平均需6分钟，由于场地限制，系统内最多不超过3名顾客，求：

运筹学--第十三章排队论

３２８习题十三 13.1 某市消费者协会一年365天接受顾客对产品质量的申诉。设申诉以λ＝4件/天的普阿松流到达，该协会每天可以处理申诉5件，当天处理不完的将移交专门小组处理，不影响每天业务。试求：（1）一年内有多少天无一件申诉；（2）一年内多少天处理不完当天的申诉。 13.2 来到某餐厅的顾客流服从普阿松分布，平均每小时20人。餐厅于上午11：00开始营业，试求：（1）当上午11：07有18名顾客在餐厅时，于11：12恰好有20名顾客的概率（假定该时间段内无顾客离去）；（2）前一名顾客于11：25到达，下一名顾客在11：28至11：30之间到达的概率。 13.3 某银行有三个出纳员，顾客以平均速度为4人/分钟的泊松流到达，所有的顾客排成一队，服务时间服从均值为0.5分钟的负指数分布，试求：（1）银行内空闲时间的概率；（2）银行内顾客数为n 时的稳态概率；（3）平均队列长Lq ；（4）银行内的顾客平均数Ls ；（5）平均逗留时间Ws ；（6）平均等待时间Wq 。 13.4 某加油站有一台油泵。来加油的汽车按普阿松分布到达，平均每小时20辆，但当加油站中已有n 辆汽车时，新来汽车中将有一部分不愿等待而离去，离去概率为4 n （n ＝0，1，2，3，4）。油泵给一辆汽车加油所需时间为具有均值3分钟的负指数分布。（1）画出此排队系统的速率图；（2）导出其平衡方程式；（3）求出加油站中汽车数的稳态概率分布；（4）求那些在加油站的汽车的平均逗留时间。 13.5 某无线电修理商店保证每件送到的电器在一小时内修完取货，如超过一小时则分文不取。已知该商店每修理一件平均收费10元，其成本平均每件5.50元。已知送来修理的电器按普阿松分布到达，平均每小时6件，每维修一件的时间平均为7.5分钟，服从负指数分布。试问：（1）该商店在此条件下能否盈利；（2）当每小时送达的电器为多少件时该商店的经营处于盈亏平衡点。 13.6 某企业有5台车运货，已知每台车每运行100小时平均需维修2次，每次需时20分钟，以上分别服从普阿松及负指数分布。求该企业全部车辆正常运

排队论

排队论实验报告

《排队现象的建模、解析与模拟》课程设计姓名：学号：班级：

题目描述：排队系统的稳定性与什么有关？与系统的一步概率转移矩阵有什么关系？收敛速度快慢与什么有关？解答过程：（1）初始设定：设初始状态X=(P1 P2 P3 … Pn),一步状态概率转移矩阵为P ，最终系统趋于稳定的状态为Y=(Y1 Y2 Y3 … Yn)，可知X 和Y 是一个固定不变的行向量，且P1+P2+P3+…+Pn=1，Y1+Y2+Y3+…+Yn=1。（2）描述模型：对排队系统最终趋于稳定的描述为：Y=X*P n ，n>N(N 是一个足够大的数)。（3）提出假想：由（2）中对于系统最终趋于稳定状态的描述，因为X 和Y 都是固定的向量，所以，若系统趋于稳定，则P n 收敛。假设P 最终收敛为 P σ=(a1 a2 ?an ???x1x2?xn ) ，由概率转移矩阵的性质可知各行概率之和为1，即a1+a2+…+an=1。因为Y* P σ= (Y1 Y2 Y3 … Yn)* (a1 a2 ?an ???x1x2?xn )=Y=(Y1 Y2 Y3 … Yn)，故提出猜测：概率转移矩阵收敛后各列的元素值相等。 (4)MATLAB 验证猜想： ① 当n ≥73时收敛：

② 当n≥38时收敛 ③ 当n≥11时收敛

④ 当n≥3时收敛 ⑤ P本身就是收敛后的结果

(5)结论：经过一系列验证，得出系统的稳定性只与一步转移概率矩阵P 有关，若P 收敛，则系统趋于稳定，反之系统不稳定。并且P 收敛后行和为1，每列元素值相同。因为Y* P σ= (Y1 Y2 Y3 …… Yn)* (a1 a2 ?an ???a1a2?an ) =((Y1+Y2+Y3+…Yn)*a1 (Y1+Y2+Y3+…Yn)*a2 … (Y1+Y2+Y3+…Yn)*an) =(a1 a2 … an) 所以最终的概率分布的结果是矩阵收敛后的一行。收敛速度快慢与一步概率转移矩阵每列元素值的分布有关，若每列元素值分布比较均匀，则收敛速度较快，反之收敛速度较慢。每列元素值相等的矩阵，本身就是收敛后的结果。单位阵是一个特例，它每列元素值不相等，但是单位阵收敛。与单位阵类似的一类矩阵，即每列有且仅有一个1出现的矩阵，这类矩阵不会收敛。

运筹学[第十二章排队论]山东大学期末考试知识点复习

第十二章排队论 1．排队一般的排队系统都有3个基本组成部分：输入过程，排队规则，服务机构。输入过程： (1)顾客源的组成可能是有限的也可能是无限的。 (2)顾客到达的方式可能是一个一个的，也可能是成批的。 (3)顾客相继到达的间隔时间可以是确定的，也可以是随机的。 (4)顾客之间到达可以是相互独立的或关联的。 (5)输入过程可以是平稳的，或称对时间是齐次的，即指间隔时间的分布和所含参数均与时间无关，否则称为非平稳的，不过一般总假定是平稳的。 2．三种排队规则 (1)损失制：顾客到达后发现服务台正被占用，则离去。 (2)等待制：顾客到达后发现服务台正被占用，排队等侯。等待制的服务规则：①先到先服务；②后到先服务；③随机服务；④有优先权服务。 (3)混合制：是等待制和损失制相结合的一种排队服务规则。有两种： ①队长有限制的情况，即当顾客排队等待服务的人数超过规定数量时，后来的顾客就自动离去，另求服务。 ②排队时间有限制的情况，当顾客排队时间超过一定时间时，顾客就自动离去。服务机构情况：服务机构可以从下述几个方面来描述。 ①服务台数量及布置形式。

从数量上来看，是单服务台还是多服务台，在多服务台的情况下，是串列的还是并列的，或是串、并列结合的，如图12—1所示。 ②在某一时刻接受服务的顾客数，即每个服务台每次对单个顾客还是成批顾客。 ③服务时间分布，服务时间和顾客来到时间一样，多数情况下是随机的。常见的分布有：泊松分布，负指数分布，爱尔朗分布等。 3．排队模型有关指标与记号 (1)系统状态——指一个排队服务系统中顾客数(包括正在被服务的顾客数)； (2)队长——指系统中等待服务的顾客数，它等于系统状态减去正在被服务的顾客数； (3)N(t)——在时刻t排除服务系统中的顾客数，即系统在时刻t的瞬时状态；

排队论论文

摘要：本文首先对排队论中的基本建模与相关知识点进行了总结，然后对生活中排队论的运用的例子进行了讲解,接下来对无线通信中排队论的运用进行了相关的说明。最后进行了总结。关键词：排队论,随机过程，泊松分布一、排队论中的基本建模与相关知识点不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待,则加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开系统。各个顾客由顾客源(总体)出发,到达服务机构(服务台、服务员)前排队等候接受服务,服务完成后离开。排队结构指队列的数目和排列方式,排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。排队过程的一般模型实际的排队系统虽然千差万别,但是它们有以下的共同特征: (１)有请求服务的人或物——顾客; (2)有为顾客服务的人或物,即服务员或服务台； (3)顾客到达系统的时刻是随机的,为每一位顾客提供服务的时间是随机的,因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长,而另外一些时候服务员(台)又空闲无事。排队系统由三个基本部分组成：①输入过程②排队规则③服务机构。输入过程: 这是指要求服务的顾客是按怎样的规律到达排队系统的过程。

(１)顾客总体数,又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的,也可以是无限的。 (2)顾客到达方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。 (3)顾客流的概率分布,或称相继顾客到达的时间间隔的分布。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流）、爱尔朗分布等若干种。服务规则： (1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。 (２）等待制。这是指当顾客来到系统时,所有服务台都不空,顾客加入排队行列等待服务。 ①先到先服务。 ②后到先服务。 ③随机服务。 ④优先权服务。 (3)混合制。这是等待制与损失制相结合的一种服务规则,一般是指允许排队，但又不允许队列无限长下去。 ①队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务,即系统的等待空间是有限的。 ②等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度Ｔ，当等待时间超过Ｔ时,顾客将自动离去,并不再回来。 ③逗留时间(等待时间与服务时间之和)有限。不难注意到,损失制和等待制可看成是混合制的特殊情形,如记ｓ为系统中服务台的个数,则当Ｋ=ｓ时，混合制即成为损失制；当Ｋ=∞时，混合制即成为等待制。服务台情况: (1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。（2) 服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。（3) 服务时间的分布。一般来说,在多数情况下,对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布（所有顾客的服务时间都是独立同分布的)等等。排队系统的描述符号与分类为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类,可给出很多排队模型。为了方便对众多模型的描述,肯道尔（D．G．Ｋendall)提出了一种目前在排队论中被广泛采用的“Kendall记号”,完整的表达方式通常用到６个符号并取如下固定格式：Ａ/B/C/D/E/Ｆ各符号的意义为： A—表示顾客相继到达间隔时间分布,常用下列符号：Ｍ—表示到达过程为泊松过程或负指数分布; D—表示定长输入； Eｋ—表示ｋ阶爱尔朗分布; G—表示一般相互独立的随机分布。 B—表示服务时间分布,所用符号与表示顾客到达间隔时间分布相同。

排队论测试题

以上分别服从泊松分布和负指数分布。为减轻打字员负担，有两个方案；一是增加一名打字员，每天费为 40 元，其工作效率同原打字员；二为购一台自动打字机，以提高打字效率，已知有三种类型打字机其费用及提高打字的效率如表 6-1 所示。表 6-1 型号每天费用 / 元打字员效率提高程度 /% 1 37 50 2 39 75 3 43 150 据公司估测，每个文件若晚发出 1h 将平均损失 0.80 元。设打字员每天工作 8h ，试确定该公司应采用的方案。 6.8 某商店收款台有 3 名收款员，顾客到达率为每小时 504 人，每名收款员服务率为每小时 240 人，设顾客到达为泊松流，收款服务时间服从负指数分布，分别求 P 0 、 L q 、 L s 、 W q 及 W s 。 6.9 某设备维修中心有 k 名工人，每天到达的需检修的设备服从λ=10 的负指数分布，每名工人维修设备的平均时间服从μ=3 的负指数分布。现已知设置一名工人的服务成本为每天 4 元，而设备等待损失为每天 25 元，试决定此设备维修中心工人的最佳数字 k 。 6.10 考虑某个只有一个服务员的排队系统，输入为参数λ的普阿松流。假定服务时间的概率分布未知，但期望值已知为 1/ μ。 (a) 比较每个顾客在队伍中的期望等待时间，如服务时间的分布为：①负指数分布；②定长分布；③爱郎分布，` 值为负指数分布的 1/2 ； (b) 如与值均增大为原来的 2 倍，值也相应变化，求上述三种情况下顾客在队伍中期望等待间的改变情况。 6.11 汽车按泊松分布到达一个汽车服务部门，平均 5 辆 /h 。洗车部门只拥有一套洗车设备，试分别计算在下列服务时间分布的情况下系统的 L s ， L q ， W s 与 W q 的值： (a) 洗车时间为常数，每辆需 10min ； (b) 负指数分布， 1/u=10min; (c) t 为 5～15min 的均匀分布； (d) 正态分布，μ=9min,Var(t)=42 ; (e) 离散的概率分布 P （ t=5 ） =1/4 ， P(t=10)=1/2, P(t=15)=1/4 。 6.12 某仓库贮存的一种商品，每天的到货与出货量分别服从普阿松分布，其平均值为λ和μ，因此该系统可近似看成为（ M/M/1/ ∞ / ∞）的排队系统。设该仓库贮存费为每天每件 c 1 元，一旦发生缺货时，其损失为每天每件 c 2 元，已知 c 2 >c 1 , 要求： (a) 推导每天总期望费用的公式； (b) 使总期望费用为最小的λ/ μ值。 6.13 设顾客按泊松流到达某服务台，平均到达率为λ=12 位 /h ，设每一位接收服务的顾客的等候成本为每小时 5 元，服务台的服务成本为每位顾客 2 元。试确定使此服务台总费用最少的平均服务率μ* 。 6.14 填空

排队论(queuing theory)

排队论排队论(Queuing Theory) ，是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，又称随机服务系统理论，为运筹学的一个分支。 1.定义排队论(queuing theory), 或称随机服务系统理论，是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。 1、排队模型的表示 X/Y/Z/A/B/C X—顾客相继到达的间隔时间的分布； Y—服务时间的分布； M—负指数分布、D—确定型、Ek —k阶爱尔兰分布； Z—服务台个数； A—系统容量限制（默认为∞）； B—顾客源数目（默认为∞）； C—服务规则（默认为先到先服务FCFS)。 2、排队系统的衡量指标队长Ls—系统中的顾客总数；排队长Lq—队列中的顾客数；

逗留时间Ws—顾客在系统中的停留时间；等待时间Wq—顾客在队列中的等待时间；忙期—服务机构两次空闲的时间间隔；服务强度ρ；稳态—系统运行充分长时间后，初始状态的影响基本消失，系统状态不再随时间变化。 3、到达间隔时间与服务时间的分布泊松分布；负指数分布；爱尔兰分布；统计数据的分布判断。排队系统的构成及应用前景排队系统由输入过程与到达规则、排队规则、服务机构的结构、服务时间与服务规划组成。一般还假设到达间隔时间序列与服务时间均为独立同分布随机变量序列，且这两个序列也相互独立。评价一个排队系统的好坏要以顾客与服务机构两方面的利益为标准。就顾客来说总希望等待时间或逗留时间越短越好，从而希望服务台个数尽可能多些但是，就服务机构来说，增加服务台数，就意味着增加投资，增加多了会造成浪费，增加少了要引起顾客的抱怨甚至失去顾客，增加多少比较好呢？顾客与服务机构为了照顾自己的利益对排队系统中的3个指标：队长、等待时间、服务台的忙期（简称忙期）都很关心。因此这3个指标也就成了排队论的主要研究内容。 2.组成部分排队系统又称服务系统。服务系统由服务机构和服务对象（顾客）构成。服务对象到来的时刻和对他服务的时间（即占用服务系统的时间）都是随机的。

(数学建模教材)6第六章排队论

第六章排队论模型排队论起源于1909 年丹麦电话工程师A. K．爱尔朗的工作，他对电话通话拥挤问题进行了研究。1917 年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理论的几个问题的解决”。排队论已广泛应用于解决军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机性。可以说排队现象几乎是不可避免的。排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展的一门学科。它研究的内容有下列三部分：（i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。（ii）最优化问题，又分静态最优和动态最优，前者指最优设计。后者指现有排队系统的最优运营。（iii）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研究。这里将介绍排队论的一些基本知识，分析几个常见的排队模型。 §1基本概念 1.1 排队过程的一般表示下图是排队论的一般模型。图1 排队模型图中虚线所包含的部分为排队系统。各个顾客从顾客源出发，随机地来到服务机构，按一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统。对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。因此，顾客总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。 1.2 排队系统的组成和特征一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如下： 1.2.1 输入过程输入过程是指顾客到来时间的规律性，可能有下列不同情况：（i）顾客的组成可能是有限的，也可能是无限的。 -118-

排队论

5.2 排队论排队是日常生活和工作中常见的现象，它由两个方面构成，一是要求得到服务的顾客，二是设法给予服务的服务人员或服务机构（统称为服务员或服务台），顾客与服务台就构成一个排队系统，或称为随机服务系统。如图5.5所示。图5.5 排队系统结构 5.2.1 排队论概述 1. 排队论研究的基本问题随机性是排队系统的共同特性，顾客的到达间隔时间与顾客所需的服务时间中，至少有一个具有随机性。排队论研究的首要问题是系统的主要数量指标（如：系统的队长（系统中的顾客数）、顾客的等待时间和逗留时间等）的概率特性，然后进一步研究系统优化问题。与这两个问题相关联的还有系统的统计推断问题。 1) 性态问题(即数量指标的研究) 研究排队系统的性态问题就是通过研究系统的主要数量指标的瞬时性质或统计平衡下的性态来研究排队系统的基本特征。 2) 最优化问题排队系统的最优化问题涉及排队系统的设计、控制以及系统有效性的度量，包括系统的最优设计（静态最优）和已有系统的最优运行控制（动态最优），前者是在服务系统设置之前，对未来运行的情况有所估计，确定系统的参数，使设计人员有所依据；后者是对已有的排队系统寻求最优运行策略。其内容很多，有最小费用问题，服务率的控制问题等。 3) 统计推断问题排队系统的统计推断是通过对正在运行的排队系统多次观测、搜集数据，用数理统计的方法对得到的资料进行加工处理，推断所观测的排队系统的概率规律，建立适当的排队模型。 2. 排队系统的基本组成及特征实际中的排队系统是各种各样的，但从决定排队系统进程的因素看，它由3个基本部分组成：输入过程、排队规则和服务机构。由于输入过程、排队规则和服务机构的复杂多样性，可以形成各种各样的排队模型，因此在研究一个排队系统之前，有必要弄清楚这3部

第9章排队论

第9章排队论判断下列说法是否正确： 09100011、若到达排队系统的顾客为泊松流，则依次到达的两名顾客之间的间隔时间服从负指数分布； 09100021、假如到达排队系统的顾客来自两个方面，分别服从泊松分布，则这两部分顾客合起来的顾客流仍为泊松分布； 09100031、若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序，则第1、3、5、7，…名顾客到达的间隔时间也服从负指数分布； 09100041、对M/M/1或M/M/C的排队系统，服务完毕离开系统的顾客流也为泊松流； 09100051、在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大量实际系统的统计研究，这样的假定比较合理； 09100061、一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后，系统将进入稳定状态； 09100071、排队系统中，顾客等待时间的分布不受排队服务规则的影响； 09100081、在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间将少于允许队长无限的系统； 09100091、在顾客到达的分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有关，当服务时间分别的方差越大时，顾客的平均等待时间将越长； 09100101、在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。 M/M/1 09301012、某理发店只有一名理发师，来理发的顾客按泊松分布到达，平均每小时4人，理发时间服从负指数分布，平均需6小时，求：（1）理发店空闲时间的概率；（2）店内有3个顾客的概率；（3）店内至少有1个顾客的概率；（4）在店内顾客平均数；（5）在店内平均逗留时间；（6）等待服务的顾客平均数；（7）平均等待服务时间；（8）必须在店内消耗15分钟以上的概率。

排队论习题集汇总jieda

排队论习题集汇总_解答例1 高速公路入口收费处设有一个收费通道，汽车到达服从Poisson 分布，平均到达速率为100辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求 1、收费处空闲的概率； 2、收费处忙的概率； 3、系统中分别有1，2，3辆车的概率。根据题意, λ=100辆/小时， μ1=15秒=240 1（小时/辆）,即μ＝240（辆/小时）。因此 12 5 240100==μλ= ρ 系统空闲的概率为： 583.012 712511P 0==- =ρ-= 系统忙的概率为： 417.012 5 )1(1P 10== ρ=ρ--=- 系统中有1辆车的概率为： 243.0144 35127125)1(P 1==?= ρ-ρ= 系统中有2辆车的概率为： 101.01728 175127125)1(P 2 2 2==???? ??=ρ-ρ= 系统中有3辆车的概率为： 0422.020736 875127125)1(P 3 33==???? ??=ρ-ρ= 1. 思考题（1）排队论主要研究的问题是什么；（2）试述排队模型的种类及各部分的特征；（3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义；（4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念；（5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分布的主要性质；（6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系

与区别。 2．判断下列说法是否正确（1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布；（2）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分顾客合起来的顾客流仍为普阿松分布；（3）若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序，则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布；（4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流；（5）在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大量实际系统的统计研究，这样的假定比较合理；（6）一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后，系统将进入稳定状态；（7）排队系统中，顾客等待时间的分布不受排队服务规则的影响；（8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间少于允许队长无限的系统；（9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有关，当服务时间分布的方差越大时，顾客的平均等待时间就越长；（10）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。 3．某店有一个修理工人，顾客到达过程为Poisson 流，平均每小时3人，修理时间服从负指数分布，平均需19分钟，求：（1）店内空闲的时间；（2）有4个顾客的概率；（3）至少有一个顾客的概率；（4）店内顾客的平均数；（5）等待服务的顾客数；（6）平均等待修理的时间；（7）一个顾客在店内逗留时间超过15分钟的概率。 4．设有一个医院门诊，只有一个值班医生。病人的到达过程为Poisson 流，平均到达时间间隔为20分钟，诊断时间服从负指数分布，平均需12分钟，求：（1）病人到来不用等待的概率；（2）门诊部内顾客的平均数；（3）病人在门诊部的平均逗留时间；（4）若病人在门诊部内的平均逗留时间超过1小时，则医院方将考虑增加值班医生。问病人平均到达率为多少时，医院才会增加医生？ 5．某排队系统只有1名服务员，平均每小时有4名顾客到达，到达过程为Poisson 流，，服务时间服从负指数分布，平均需6分钟，由于场地限制，系统内最多不超过3名顾客，求：（1）系统内没有顾客的概率；（2）系统内顾客的平均数；（3）排队等待服务的顾客数；（4）顾客在系统中的平均花费时间；（5）顾客平均排队时间。 6．某街区医院门诊部只有一个医生值班，此门诊部备有6张椅子供患者等候应诊。当椅子坐满时，后来的患者就自动离去，不在进来。已知每小时有4名患者按Poisson 分布到达，每名患者的诊断时间服从负指数分布，平均12分钟，求：（1）患者无须等待的概率；（2）门诊部内患者平均数；（3）需要等待的患者平均数；

排队论习题五

习题五 [5-1] 设某地铁站口顾客流是泊松流，每小时平均有120人乘车，求在1分钟内无人乘车，有1、2、3、4人乘车的概率，1分钟内有超过1人乘车的概率。 [5-2] 设货车按泊松流到达车站，平均每天到达2辆，装卸货物时间服从负指数分布，平均每天可装卸3车。求每辆货车在车站平均停留时间，平均有多少车在排队等待装卸。 [5-3] 设某个售票点只有一个窗口，顾客到达服从泊松分布，平均每分钟到达1人，窗口售票时间服从负指数分布，平均每分钟可服务2人。求系统平稳状态下的平均队长、平均等待队长、平均等待时间、顾客逗留时间、顾客不等待的概率以及等待队长超过5人时的概率。 [5-4] 某超市的顾客按泊松流到达，平均每小时12人，收款台收费时间服从负指数分布，平均每位顾客需要4分钟。求该超市的效益指标。 [5-5] 设某产品是生产过程中需要的，若进货过多，会造成保管费增加，若存货不足会影响生产，因此需要找到合理的库存量S ，使得库存费用与缺货损失的总和最小。设对这种产品的需求量是泊松分布，参数为λ，生产这种产品的时间服从负指数分布，参数为μ。库存一件该产品单位时间费用为C ，缺少一个该产品造成损失H ，求最优库存S 。 [5-6] 设某单位需要购置计算机，一种方案是购置一台大型计算机，一种方案是购置n 台微型计算机，每台微型计算机是大型计算机处理能力的1/n 。设要求上机的题目是参数为λ的泊松流，大型与微型计算机计算题目时间是服从负指数分布，大型计算机的参数为μ，试从平均逗留时间、平均等待时间分析，选择哪种方案合适。 [5-7] 设某信访部门的接待人员每天工作10小时，来访人员的到来和接待时间都是随机的，每天平均有90人到来，接待的平均速率为10人/小时。求排队等待的平均人数，等待接待的人多于2人的概率，若要使等待的人平均为2人，接待的速率应提高多少？ [5-8] 设[0,t )内到达的顾客服从泊松分布，参数为λ。只有单个服务员、服务时间为负指数分布，平均服务时间为1/μ。试证明：(1) 在服务员的服务时间内到达顾客的平均数为λ/μ；(2) 在服务员的服务时间内无顾客到达的概率为μ/(λ+μ)。 [5-9] 设有单个服务员、服务时间为负指数分布的排队系统，平均服务时间为1/μ；到达服务点的顾客数服从泊松分布，参数为λ，求顾客到达时系统中已有n 个或n 个以上的顾客的概率。 [5-10] 设有题5-9所给定的排队服务系统，设排队已经到达统计平稳状态。服务的规则是先到先服务。设y 代表一顾客花费在排队等候的时间和服务时间的总和。求y 的概率密度f y (t)，并证明： (1) 一个顾客花费在系统内的时间小于或等于x 的概率为x e )(1λμ???； (2) 一个顾客花费在排队的时间小于或等于x 的概率为 1(0)x λμ?=；()1()[1](0)x e x μλλμλ???+?> [5-11] 设电话总机有3条线路，一条线路平均每分钟有0.8次呼叫，每次通话时间平均1.5分钟。求系统的平稳分布、绝对和相对通过能力、损失概率及占用线路的平均数。 [5-12] 设运输船到码头，在港口停留1小时损失C 1元，而接受港口服务费用正比服务率每小时C 2元，进港船只数服从参数为λ的泊松分布，装卸服务时间服从参数为μ的负指数分布。求整个系统总费用最小的服务率μ。

排队论

排队论—关于学校澡堂洗澡排队问题本文所处理的排队论问题：学校的澡堂每周周一到周五下午 5 点开到晚上10 点，周六周日是早上9 点到晚上10 点开，在周一至周五期间，5 点到 6 点半这段时间内，因为上课和体能锻炼结束，在晚饭前后，会有很多学生前去洗澡，这时由于高峰期去的人很多，就会产生排队情况。本文就对这个个排队现象进行分析。首先对排队现象进行基本的分析和简化处理： 1.学生大多数是一个一个的来洗澡、有时候会两个或三个人一起来，且每个的到来都是互不影响的，所以我们简化处理，假设学生是一个一个的到来，且每个人的到来时间间隔都是服从指数分布的，故在高峰期这段时间间隔内，学生的到来就服从参数为的泊松分布。 2.学生到澡堂后，首先进入等待区，将衣物放入橱衣柜才能洗澡，设有k 个橱衣柜，而有 c 个淋浴喷头可以洗澡，实际情况中经常是储物柜的数目大于喷头数目，因为有些学生时间比较紧，不一定会将衣物放入储物柜中才去洗澡，但也不会有很多这种情况，故我们假设这也是将衣物存放在储物柜中的，故储物柜的个数大于喷头数，而且由于使用时间比较长了，所以喷头有一些都坏了，故喷头数是小于橱衣柜的树木的，并且对每个学生来说，如果没有排队现象，只要来到澡堂就能立刻洗澡，所以遵从先来先服务的服务

原则。 3.而且每个学生洗澡都是独自用一个喷头，故假设使用喷头的过程是相互独立，都是各自洗各自的，互不影响，且洗澡时间是服从参数为μ的指数分布，且只要洗完就不会再里面逗留，直接出来。系统模型如下图所示：所以我们得出系统的模型，这样的排队问题是典型的M / M / c / k模型，即每个学生是按指数分布到达，按指数分布服务，服务员有c个，等待区间的大小为k。 M / M / c / k 模型：如上图所示：其中向右的箭头表示流入速率λ，即学生进入澡堂的速率，向左的箭头表示服务速率μj，即学生洗完澡离去的速率：由局部能量守恒定律可知，故而可推出：将λ和μj带入有：

第六部分 排队论

第六章 排队论