没有合适的资源?快使用搜索试试~ 我知道了~
排队论教程
需积分: 9 10 下载量 111 浏览量
2015-08-05
23:56:39
上传
评论
收藏 469KB PDF 举报
温馨提示
试读
36页
数学建模中排队论的介绍,参与数学建模的可以了解一下。
资源推荐
资源详情
资源评论
-118-
第六章 排队论模型
排队论起源于 1909 年丹麦电话工程师 A. K.爱尔朗的工作,他对电话通话拥挤问
题进行了研究。1917 年,爱尔朗发表了他的著名的文章—“自动电话交换中的概率理
论的几个问题的解决”。排队论已广泛应用于解决军事、运输、维修、生产、服务、库
存、医疗卫生、教育、水利灌溉之类的排队系统的问题,显示了强大的生命力。
排队是在日常生活中经常遇到的现象,如顾客到商店购买物品、病人到医院看病常
常要排队。此时要求服务的数量超过服务机构(服务台、服务员等)的容量。也就是说,
到达的顾客不能立即得到服务,因而出现了排队现象。这种现象不仅在个人日常生活中
出现,电话局的占线问题,车站、码头等交通枢纽的车船堵塞和疏导,故障机器的停机
待修,水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机
性。可以说排队现象几乎是不可避免的。
排队论(Queuing Theory)也称随机服务系统理论,就是为解决上述问题而发展
的一门学科。它研究的内容有下列三部分:
(i)性态问题,即研究各种排队系统的概率规律性,主要是研究队长分布、等待
时间分布和忙期分布等,包括了瞬态和稳态两种情形。
(ii)最优化问题,又分静态最优和动态最优,前者指最优设计。后者指现有排队
系统的最优运营。
(iii)排队系统的统计推断,即判断一个给定的排队系统符合于哪种模型,以便
根据排队理论进行分析研究。
这里将介绍排队论的一些基本知识,分析几个常见的排队模型。
§1 基本概念
1.1 排队过程的一般表示
下图是排队论的一般模型。
图 1 排队模型
图中虚线所包含的部分为排队系统。各个顾客从顾客源出发,随机地来到服务机构,按
一定的排队规则等待服务,直到按一定的服务规则接受完服务后离开排队系统。
凡要求服务的对象统称为顾客,为顾客服务的人或物称为服务员,由顾客和服务员
组成服务系统。对于一个服务系统来说,如果服务机构过小,以致不能满足要求服务的
众多顾客的需要,那么就会产生拥挤现象而使服务质量降低。 因此,顾客总希望服务
机构越大越好,但是,如果服务机构过大,人力和物力方面的开支也就相应增加,从而
会造成浪费,因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权
衡决策,使其达到合理的平衡。
1.2 排队系统的组成和特征
一般的排队过程都由输入过程、排队规则、服务过程三部分组成,现分述如下:
1.2.1 输入过程
输入过程是指顾客到来时间的规律性,可能有下列不同情况:
(i)顾客的组成可能是有限的,也可能是无限的。
-119-
(ii)顾客到达的方式可能是一个—个的,也可能是成批的。
(iii)顾客到达可以是相互独立的,即以前的到达情况对以后的到达没有影响;
否则是相关的。
(iv)输入过程可以是平稳的,即相继到达的间隔时间分布及其数学期望、方差等
数字特征都与时间无关,否则是非平稳的。
1.2.2 排队规则
排队规则指到达排队系统的顾客按怎样的规则排队等待,可分为损失制,等待制和
混合制三种。
(i)损失制(消失制)。当顾客到达时,所有的服务台均被占用,顾客随即离去。
(ii)等待制。当顾客到达时,所有的服务台均被占用,顾客就排队等待,直到接
受完服务才离去。例如出故障的机器排队等待维修就是这种情况。
(iii)混合制。介于损失制和等待制之间的是混合制,即既有等待又有损失。有
队列长度有限和排队等待时间有限两种情况,在限度以内就排队等待,超过一定限度就
离去。
排队方式还分为单列、多列和循环队列。
1.2.3 服务过程
(i)服务机构。主要有以下几种类型:单服务台;多服务台并联(每个服务台同
时为不同顾客服务);多服务台串联(多服务台依次为同一顾客服务);混合型。
(ii)服务规则。按为顾客服务的次序采用以下几种规则:
①先到先服务,这是通常的情形。
②后到先服务,如情报系统中,最后到的情报信息往往最有价值,因而常被优先处
理。
③随机服务,服务台从等待的顾客中随机地取其一进行服务,而不管到达的先后。
④优先服务,如医疗系统对病情严重的病人给予优先治疗。
1.3 排队模型的符号表示
排队模型用六个符号表示,在符号之间用斜线隔开,即
CBAZYX ///// 。第一
个符号
X
表示顾客到达流或顾客到达间隔时间的分布;第二个符号
Y
表示服务时间的
分布;第三个符号
Z
表示服务台数目;第四个符号
A
是系统容量限制;第五个符号
B
是
顾客源数目;第六个符号
C 是服务规则,如先到先服务 FCFS,后到先服务 LCFS 等。并
约定,如略去后三项,即指
FCFS/////
∞
∞
ZYX 的情形。我们只讨论先到先服务 FCFS
的情形,所以略去第六项。
表示顾客到达间隔时间和服务时间的分布的约定符号为:
M
—指数分布(
M
是 Markov 的字头,因为指数分布具有无记忆性,即 Markov
性);
D —确定型(Deterministic);
k
E — k 阶爱尔朗(Erlang)分布;
G —一般(general)服务时间的分布;
GI —一般相互独立(General Independent)的时间间隔的分布。
例如,
1// MM
表示相继到达间隔时间为指数分布、服务时间为指数分布、单服
务台、等待制系统。
cMD // 表示确定的到达时间、服务时间为指数分布、 c 个平行
服务台(但顾客是一队)的模型。
1.4 排队系统的运行指标
为了研究排队系统运行的效率,估计其服务质量,确定系统的最优参数,评价系统
的结构是否合理并研究其改进的措施,必须确定用以判断系统运行优劣的基本数量指
-120-
标,这些数量指标通常是:
(i)平均队长:指系统内顾客数(包括正被服务的顾客与排队等待服务的顾客)的
数学期望,记作
s
L 。
(ii)平均排队长:指系统内等待服务的顾客数的数学期望,记作
q
L 。
(iii)平均逗留时间:顾客在系统内逗留时间(包括排队等待的时间和接受服务的
时间)的数学期望,记作
s
W 。
(iv)平均等待时间:指一个顾客在排队系统中排队等待时间的数学期望,记作
q
W 。
(v)平均忙期:指服务机构连续繁忙时间(顾客到达空闲服务机构起,到服务机
构再次空闲止的时间)长度的数学期望,记为
b
T 。
还有由于顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等,
这些都是很重要的指标。
计算这些指标的基础是表达系统状态的概率。所谓系统的状态即指系统中顾客数,
如果系统中有
n 个顾客就说系统的状态是 n ,它的可能值是
(i)队长没有限制时,
L,2,1,0=n ,
(ii)队长有限制,最大数为
N
时, Nn ,,1,0 L
=
,
(iii)损失制,服务台个数是
c 时, cn ,,1,0 L
=
。
这些状态的概率一般是随时刻
t 而变化,所以在时刻 t 、系统状态为 n 的概率用
)(tP
n
表示。稳态时系统状态为 n 的概率用
n
P 表示。
§2 输入过程与服务时间的分布
排队系统中的事件流包括顾客到达流和服务时间流。由于顾客到达的间隔时间和服
务时间不可能是负值,因此,它的分布是非负随机变量的分布。最常用的分布有泊松分
布、确定型分布,指数分布和爱尔朗分布。
2.1 泊松流与指数分布
设
)(tN 表示在时间区间 ),0[ t 内到达的顾客数( 0>t ),令 ),(
21
ttP
n
表示在时间区
间
))(,[
1221
tttt >
内有 )0(≥n 个顾客到达的概率,即
)0,(})()({),(
121221
≥>
=
−= nttntNtNPttP
n
当
),(
21
ttP
n
合于下列三个条件时,我们说顾客的到达形成泊松流。这三个条件是:
1
o
在不相重叠的时间区间内顾客到达数是相互独立的,我们称这性质为无后效
性。
2
o
对充分小的 tΔ ,在时间区间 ),[ ttt
Δ
+
内有一个顾客到达的概率与 t 无关,而
约与区间长
tΔ 成正比,即
)(),(
1
tottttP
Δ
+Δ=Δ
+
λ
(1)
其中
)( to Δ ,当 0→Δt 时,是关于 t
Δ
的高阶无穷小。 0>
λ
是常数,它表示单位时间
有一个顾客到达的概率,称为概率强度。
3
o
对于充分小的 tΔ ,在时间区间
),[ ttt
Δ
+
内有两个或两个以上顾客到达的概率
极小,以致可以忽略,即
∑
∞
=
Δ=Δ+
2
)(),(
n
n
totttP (2)
-121-
在上述条件下,我们研究顾客到达数 n 的概率分布。
由条件 2
o
,我们总可以取时间由 0 算起,并简记 )(),0( tPtP
nn
=
。
由条件 1
o
和2
o
,有
)()()(
000
tPtPttP
Δ
=Δ
+
∑
=
−
=Δ=Δ+
n
k
kknn
ntPtPttP
0
,2,1),()()( L
由条件 2
o
和3
o
得
)(1)(
0
tottP
Δ
+Δ−=
Δ
λ
因而有
t
to
tP
t
tPttP
Δ
Δ
+−=
Δ
−Δ
+
)(
)(
)()(
0
00
λ
,
t
to
tPtP
t
tPttP
nn
nn
Δ
Δ
++−=
Δ
−Δ
+
−
)(
)()(
)()(
1
λλ
.
在以上两式中,取
tΔ 趋于零的极限,当假设所涉及的函数可导时,得到以下微分方程
组:
)(
)(
0
0
tP
dt
tdP
λ
−= ,
L,2,1),()(
)(
1
=+−=
−
ntPtP
dt
tdP
nn
n
λλ
.
取初值
1)0(
0
=
P , ),2,1(0)0( L
=
=
nP
n
,容易解出
t
etP
λ
−
=)(
0
;再令
t
nn
etUtP
λ
−
= )()( ,可以得到 )(
0
tU 及其它 )(tU
n
所满足的微分方程组,即
,,2,1),(
)(
1
L==
−
ntU
dt
tdU
n
n
λ
1)(
0
=tU , 0)(
=
tU
n
.
由此容易解得
L,2,1,
!
)(
)( ==
−
ne
n
t
tP
t
n
n
λ
λ
.
正如在概率论中所学过的,我们说随机变量
)}()()({ sNtsNtN
−
+
=
服从泊松分
布。它的数学期望和方差分别是
ttNE
λ
=)]([ ; ttN
λ
=
)](Var[ 。
当输入过程是泊松流时,那么顾客相继到达的时间间隔
T
必服从指数分布。这是
由于
),0{[}{ tPtTP
=
> 内呼叫次数为零
t
etP
λ
−
== )(}
0
那么,以
)(tF
表示
T
的分布函数,则有
⎩
⎨
⎧
<
≥−
==≤
−
0,0
0,1
)(}{
t
te
tFtTP
t
λ
而分布密度函数为
0,)( >=
−
tetf
t
λ
λ
.
-122-
对于泊松流,
λ
表示单位时间平均到达的顾客数,所以
λ
1
就表示相继顾客到达平均
间隔时间,而这正和
E
T
的意义相符。
对一顾客的服务时间也就是在忙期相继离开系统的两顾客的间隔时间,有时也服从
指数分布。这时设它的分布函数和密度函数分别是
t
etG
μ
−
−= 1)( ,
t
etg
μ
μ
−
=)(
我们得到
μ
=
>Δ
Δ
+
≤
<
=
Δ
>Δ+
≤
→Δ→Δ
}{
}{
lim
}|{
lim
00
tTtP
ttTtP
t
tTttTP
tt
这表明,在任何小的时间间隔
),[ ttt
Δ
+
内一个顾客被服务完了(离去)的概率是
)( tot Δ+Δ
μ
。
μ
表示单位时间能被服务完成的顾客数,称为平均服务率,而
μ
1
表示
一个顾客的平均服务时间。
2.2 常用的几种概率分布及其产生
2.2.1 常用的连续型概率分布
我们只给出这些分布的参数、记号和通常的应用范围,更详细的内容参看专门的概
率论书籍。
(i)均匀分布
区间
),( ba 内的均匀分布记作 ),( baU 。服从 )1,0(U 分布的随机变量又称为随机
数,它是产生其它随机变量的基础。如若
X
为 )1,0(U 分布,则 XabaY )( −
+
=
服从
),( baU 。
(ii)正态分布
以
μ
为期望,
2
σ
为方差的正态分布记作 ),(
2
σμ
N 。正态分布的应用十分广泛。
正态分布还可以作为二项分布一定条件下的近似。
(iii)指数分布
指数分布是单参数
λ
的非对称分布,记作 )(Exp
λ
,概率密度函数为:
⎩
⎨
⎧
<
≥
=
−
0,0
0,
)(
t
te
tf
t
λ
λ
它的数学期望为
λ
1
,方差为
2
1
λ
。指数分布是唯一具有无记忆性的连续型随机变量,即
有
)()|( sXPtXstXP >=>+> ,在排队论、可靠性分析中有广泛应用。
(iv)Gamma 分布
Gamma 分布是双参数
β
α
, 的非对称分布,记作 ),(
β
α
G ,期望是
αβ
。 1=
α
时蜕
化为指数分布。
n 个相互独立、同分布(参数
λ
)的指数分布之和是 Gamma 分布
(
),
λ
β
α
== n 。Gamma 分布可用于服务时间,零件寿命等。
Gamma 分布又称爱尔朗分布。
(v)Weibull 分布
Weibull 分布是双参数
β
α
, 的非对称分布,记作 ),(
β
α
W 。 1
=
α
时蜕化为指数分
布。作为设备、零件的寿命分布在可靠性分析中有着非常广泛的应用。
(vi)Beta 分布
剩余35页未读,继续阅读
资源评论
baidu_30392479
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功