排队论模型我们经常会碰到排队现象,如排队买火车票,排队吃饭 ; 打的时也要排队 ;打电话时事实上也会遇到排队现象,特别是高峰时 ;存在多个终端共用一个分时系统时,每个想用主机的终端也得排队,等等,
特点 (以电话总机为例 ):呼叫发生的时刻,每次通话延续的时间,一段时间内要求提供的线路数量以及被延误的通话数都具有随机性,
排队论中把所要服务的对象都称为顾客 ;顾客要求使用某类设备或者取得某种服务,所涉及的每件设备或每个提供服务者,都称为服务员,
一个排队系统的工作方式大致为,当一个顾客来到时,若其所需的服务员有空,则立刻服务并延续适当时间,当此次服务完成之后,这个服务员或者休息等待新的顾客到来,或者为已经等待在此的顾客服务,站在顾客的立场,若他发现没有服务员空闲时,他或者加入等待的队列,或者立刻离开,
对于一个特定的问题,我们应该具体研究,一般要确切知道以下几个方面内容,
1.访问总体,它指所以可能的潜在顾客全体,
对有大量潜在顾客的系统中 (如公共交通,银行 ),我们可认为总体个数无限 ;但对只有 N台机床的工厂,当考虑设备的维修问题时,等待维修的机床数有限,
2.输入过程或称顾客到达过程,它指顾客进入系统的规律,弄清楚其概率分布,
3.服务机制,它指服务员的数量、服务方式以及服务所需的时间,
4.排队规则,它指当一名顾客不能立刻被服务时所采取的行动,如立刻离开,排队等待,此时还有队列长度是多少,
电话总机的设臵问题一,呼叫发生与通话时间的概率描述令 N(t)为时间 [0,t)内总机收到的通话要求次数,模型假设,
1.在互不重叠的时间间隔内,总机收到的呼叫次数是相互独立的随机变量,
.,
,,),[
,2,1,0),)()(()(.2
无关与时间的起点有关这一概率仅与时间间隔假设的事件的概率呼叫次数为间隔内在表示以
tt
ittt
iitNttNPtP ii
.).(
),(
,
0
)()(1
l i m
,
)(
l i m
,0.3
10
0
1
0
零瞬间发生呼叫的概率为呼叫的概率是发生两次或两次以上的叫的概率为恰好发生一次呼的间隔内在长为其含义是有假设存在常数
to
tot
t
t
tPtP
t
tP
t
t
,
(2 )
(1 )
推导,由假设 1,2
得 ),()()(
:
000 tPtPttP
tt
没有呼叫叫等价于两个子阶段都的时段内没有呼在间隔长度为
.,2,1,)()()(
0
itPtPttP
i
k
kkii
于是
).1()()1()(
)(
)(
)(1)()(
00
1
0
000
otPotP
t
tP
tP
t
tP
t
tPttP
).1()()()()( 1 otPtPt tPttP iiii
得到
.,2,1,0)0()()(
)(
,1)0(),(
)(
1
00
0
iPtPtP
dt
tdP
PtP
dt
tdP
iii
i
解上面的微分方程组得到
.,2,1,
!
)(
)(,)(0 ie
i
t
tPetP t
i
i
t
我们称呼叫次数 {N(t):t>=0}所满足的这个规律为泊松 (Poisson)过程,我们知道,
.))((,))(( ttNDttNE 方差均值下面我们给出相邻呼叫的时间间隔的分布,由假设,任何连续两次呼叫的时间间隔是独立同分布的随机变量,以 T表示,则
.)(}),0[{)( 0 tetPtPtTP 内的呼叫次数为零在于是得到时间间隔 T的分布函数为
.0,0
,0,1)()(
t
tetTPtF t?
.0,)( tetf t分布密度函数为
.1)(,1)( 2 TDTE 方差均值上面说明,连续两次的时间间隔服从指数分布,
同样,一次通话的延续时间 ξ也服从指数分布,设其参数为 μ.
.)( )(l i m)|(l i m
00
ttP
tttP
t
tttP
tt
.),(
),[
无关续的时间这一概率与通话已经延为的概率的间隔内一次通话结束在其含义是
ttot
ttt
,
由于指数分布具有无后效性,因此马氏链有密切关系,
二,埃尔朗 (Erlang)消失制系统本节讨论当全部线路均被占用,再来的通话要求自动放弃的情形,这种规则称为 消失制,采用这种规则的系统称为 Erlang消失制系统,
假定系统有 s条线路,当有 j条被占用时,称系统处于状态 Ej(j=0,1,…,s).以 Pj(t)表示时刻 t系统处于状态 Ej的概率,记被占用的线路条数为 n(t),则
),)(()( jtnPtP j
( 3 ),))(())(|)((
))((
0
s
i
itnPitnjhtnP
jhtnP
.2||),(
,1),()1(
,1),(
))(|)((
jiho
jihohj
jihoh
itnjhtnP
当 h充分小时,在 [t,t+h)内恰好有一次呼叫的概率为 λh+o(h),有 >=两次呼叫的概率为 o(h) ;在
[t,t+h)内一条线路结束通话的概率 为 μh+o(h),
有 >=两条线路结束通话的概率为 o(h).因此
).(1))(|)((
:1))(|)((
1
hohjhjtnjhtnP
jtnkhtnP
s
k
得到又由
).()()1(
)()1()())((
1
1
hothPj
tPhjhthPjhtnP
j
jj
( 4 ) 1,,2,1
),()1()()()(
)(
11
sj
tPjtPjtP
dt
tdP
jjj
j
因此,
对 j=0或者 s,类似讨论,我们可以得到
( 5 ) ).()()(),()()( 1010 tPstPdt tdPtPtPdt tdP sss
.,0
,,1)0(:,,0
ij
ijPEt
ji 则初始条件为系统处于时若给定初值时,我们就可以求解这个线性微分方程组,然而,我们更关心的问题是,当系统运行时间足够长时,系统的分布是否会稳定下来,即趋于一个平衡分布,回答是肯定的 (用到马氏链理论 ).下面我们来求出这个平衡分布
Pj,它与 t无关,满足
1,,2,1,0)1()( 11 sjPjPjP jjj
.1.0,0 101
j
jss PPsPPP
( 6 ),,,2,1,0,1 sjPPj jj解之得
( 7 ),}
!
)/({,
!
)/( 1
0
00
s
j
jj
j jPPjP
以及
(6)式表明,当系统处于平衡时,在任意一段时间中,从任何一个状态转化为另一个状态的概率,与同一时间内反向变化的概率相等,因而又称为细致平衡,
(7)式的分布称为 截断的泊松分布,我们发现平衡分布只依赖于 λ/μ.我们称 a= λ/μ为顾客所要求的电话总机服务强度,
(8),
!
/
!
),(
0
s
k
ks
s
k
a
s
a
asB
E 概率为从而系统处于平衡状态
.,/
.,
1
或者说系统的效率表示系统的平均负载此因平均线路数它表示实际提供服务的记
sa
jPa
s
j
j
(8)式被称为埃尔朗消失制公式,当此概率较大时,就会出现经常打不通的情形,
当 a给定时,s应如何选择,才能保证有一定的通话率,例如 a=10,至少保证 90%的通话率,问如何确定 s:计算 B(s,a).
B(12,10)=12%,B(13,10)=8.4%.
s太小时,系统效率高,但是经常出现不能呼入的情形,长期来看,必定也会影响这个电信部门的声誉以及利润等 ;s太大,系统效率低,资源浪费大,也是不合适的,
三,埃尔朗 (Erlang)延迟系统当系统的 s条线路被占用时,再发生的呼叫依次排队,等待服务,队列的长度没有限制,其他假设同前,这样的系统称为埃尔朗延迟系统,现在状态 Ej(0<=j),仍以 Pj(t)表示时刻 t系统处于状态 Ej的概率,当 j>s时,有 j-s个顾客再队列中等待,
我们将系统在时间间隔 [t,t+h) 内,系统由状态
Ej变成状态 Ej+1及状态 Ej-1的概率依次为
λjh+o(h),μjh+o(h).系统的输入过程,与延迟与否无关,还是服从参数为 λ的泊松分布,即
λj=λ.但是,
)(
.,
,,
条线路在通话因为最多只有 s
sjs
sjj
j?
于是我们得到
( 9 ),,2,1
),()()()(
)(
1111
j
tPtPtP
dt
tdP
jjjjjjj
j
( 1 0 ) ).()()( 00110 tPtPdt tdP
我们还是更关心时间趋于无穷时,系统与初始状态无关的平衡分布,易求得平衡分布为
( 1 1 ),}
!!
{
,,1,,
!
.1,,2,1,
!
1
1
0
0
0
0
sk
sj
js
k
k
sj
j
j
j
j
ss
a
k
a
P
ssjP
ss
a
P
sjP
j
a
P
注意,当 a<s时,上面 {}内的级数收敛 ;当 a>=s时,
上面 {}内的级数发散,从而 P0=0,这时不存在平衡分布,也就是说等待服务的队列不断增加,队列长度趋于无穷的概率为 1.
令
.0,
}
)/1(!!
){/1(!
)/1(!!
),(
1
0
00
sa
sas
a
k
a
sas
a
P
sas
a
P
ss
a
PasC
ss
k
k
s
s
sj
sj
j
sj
j
上式称为埃尔朗延迟公式,它表示所以线路被占用,因而一个新到来的呼叫不能被立即服务的概率,直接计算可得到平衡系统平均占用的线路数为
.
1
1
aPsjPa
sj
j
s
j
j
特点 (以电话总机为例 ):呼叫发生的时刻,每次通话延续的时间,一段时间内要求提供的线路数量以及被延误的通话数都具有随机性,
排队论中把所要服务的对象都称为顾客 ;顾客要求使用某类设备或者取得某种服务,所涉及的每件设备或每个提供服务者,都称为服务员,
一个排队系统的工作方式大致为,当一个顾客来到时,若其所需的服务员有空,则立刻服务并延续适当时间,当此次服务完成之后,这个服务员或者休息等待新的顾客到来,或者为已经等待在此的顾客服务,站在顾客的立场,若他发现没有服务员空闲时,他或者加入等待的队列,或者立刻离开,
对于一个特定的问题,我们应该具体研究,一般要确切知道以下几个方面内容,
1.访问总体,它指所以可能的潜在顾客全体,
对有大量潜在顾客的系统中 (如公共交通,银行 ),我们可认为总体个数无限 ;但对只有 N台机床的工厂,当考虑设备的维修问题时,等待维修的机床数有限,
2.输入过程或称顾客到达过程,它指顾客进入系统的规律,弄清楚其概率分布,
3.服务机制,它指服务员的数量、服务方式以及服务所需的时间,
4.排队规则,它指当一名顾客不能立刻被服务时所采取的行动,如立刻离开,排队等待,此时还有队列长度是多少,
电话总机的设臵问题一,呼叫发生与通话时间的概率描述令 N(t)为时间 [0,t)内总机收到的通话要求次数,模型假设,
1.在互不重叠的时间间隔内,总机收到的呼叫次数是相互独立的随机变量,
.,
,,),[
,2,1,0),)()(()(.2
无关与时间的起点有关这一概率仅与时间间隔假设的事件的概率呼叫次数为间隔内在表示以
tt
ittt
iitNttNPtP ii
.).(
),(
,
0
)()(1
l i m
,
)(
l i m
,0.3
10
0
1
0
零瞬间发生呼叫的概率为呼叫的概率是发生两次或两次以上的叫的概率为恰好发生一次呼的间隔内在长为其含义是有假设存在常数
to
tot
t
t
tPtP
t
tP
t
t
,
(2 )
(1 )
推导,由假设 1,2
得 ),()()(
:
000 tPtPttP
tt
没有呼叫叫等价于两个子阶段都的时段内没有呼在间隔长度为
.,2,1,)()()(
0
itPtPttP
i
k
kkii
于是
).1()()1()(
)(
)(
)(1)()(
00
1
0
000
otPotP
t
tP
tP
t
tP
t
tPttP
).1()()()()( 1 otPtPt tPttP iiii
得到
.,2,1,0)0()()(
)(
,1)0(),(
)(
1
00
0
iPtPtP
dt
tdP
PtP
dt
tdP
iii
i
解上面的微分方程组得到
.,2,1,
!
)(
)(,)(0 ie
i
t
tPetP t
i
i
t
我们称呼叫次数 {N(t):t>=0}所满足的这个规律为泊松 (Poisson)过程,我们知道,
.))((,))(( ttNDttNE 方差均值下面我们给出相邻呼叫的时间间隔的分布,由假设,任何连续两次呼叫的时间间隔是独立同分布的随机变量,以 T表示,则
.)(}),0[{)( 0 tetPtPtTP 内的呼叫次数为零在于是得到时间间隔 T的分布函数为
.0,0
,0,1)()(
t
tetTPtF t?
.0,)( tetf t分布密度函数为
.1)(,1)( 2 TDTE 方差均值上面说明,连续两次的时间间隔服从指数分布,
同样,一次通话的延续时间 ξ也服从指数分布,设其参数为 μ.
.)( )(l i m)|(l i m
00
ttP
tttP
t
tttP
tt
.),(
),[
无关续的时间这一概率与通话已经延为的概率的间隔内一次通话结束在其含义是
ttot
ttt
,
由于指数分布具有无后效性,因此马氏链有密切关系,
二,埃尔朗 (Erlang)消失制系统本节讨论当全部线路均被占用,再来的通话要求自动放弃的情形,这种规则称为 消失制,采用这种规则的系统称为 Erlang消失制系统,
假定系统有 s条线路,当有 j条被占用时,称系统处于状态 Ej(j=0,1,…,s).以 Pj(t)表示时刻 t系统处于状态 Ej的概率,记被占用的线路条数为 n(t),则
),)(()( jtnPtP j
( 3 ),))(())(|)((
))((
0
s
i
itnPitnjhtnP
jhtnP
.2||),(
,1),()1(
,1),(
))(|)((
jiho
jihohj
jihoh
itnjhtnP
当 h充分小时,在 [t,t+h)内恰好有一次呼叫的概率为 λh+o(h),有 >=两次呼叫的概率为 o(h) ;在
[t,t+h)内一条线路结束通话的概率 为 μh+o(h),
有 >=两条线路结束通话的概率为 o(h).因此
).(1))(|)((
:1))(|)((
1
hohjhjtnjhtnP
jtnkhtnP
s
k
得到又由
).()()1(
)()1()())((
1
1
hothPj
tPhjhthPjhtnP
j
jj
( 4 ) 1,,2,1
),()1()()()(
)(
11
sj
tPjtPjtP
dt
tdP
jjj
j
因此,
对 j=0或者 s,类似讨论,我们可以得到
( 5 ) ).()()(),()()( 1010 tPstPdt tdPtPtPdt tdP sss
.,0
,,1)0(:,,0
ij
ijPEt
ji 则初始条件为系统处于时若给定初值时,我们就可以求解这个线性微分方程组,然而,我们更关心的问题是,当系统运行时间足够长时,系统的分布是否会稳定下来,即趋于一个平衡分布,回答是肯定的 (用到马氏链理论 ).下面我们来求出这个平衡分布
Pj,它与 t无关,满足
1,,2,1,0)1()( 11 sjPjPjP jjj
.1.0,0 101
j
jss PPsPPP
( 6 ),,,2,1,0,1 sjPPj jj解之得
( 7 ),}
!
)/({,
!
)/( 1
0
00
s
j
jj
j jPPjP
以及
(6)式表明,当系统处于平衡时,在任意一段时间中,从任何一个状态转化为另一个状态的概率,与同一时间内反向变化的概率相等,因而又称为细致平衡,
(7)式的分布称为 截断的泊松分布,我们发现平衡分布只依赖于 λ/μ.我们称 a= λ/μ为顾客所要求的电话总机服务强度,
(8),
!
/
!
),(
0
s
k
ks
s
k
a
s
a
asB
E 概率为从而系统处于平衡状态
.,/
.,
1
或者说系统的效率表示系统的平均负载此因平均线路数它表示实际提供服务的记
sa
jPa
s
j
j
(8)式被称为埃尔朗消失制公式,当此概率较大时,就会出现经常打不通的情形,
当 a给定时,s应如何选择,才能保证有一定的通话率,例如 a=10,至少保证 90%的通话率,问如何确定 s:计算 B(s,a).
B(12,10)=12%,B(13,10)=8.4%.
s太小时,系统效率高,但是经常出现不能呼入的情形,长期来看,必定也会影响这个电信部门的声誉以及利润等 ;s太大,系统效率低,资源浪费大,也是不合适的,
三,埃尔朗 (Erlang)延迟系统当系统的 s条线路被占用时,再发生的呼叫依次排队,等待服务,队列的长度没有限制,其他假设同前,这样的系统称为埃尔朗延迟系统,现在状态 Ej(0<=j),仍以 Pj(t)表示时刻 t系统处于状态 Ej的概率,当 j>s时,有 j-s个顾客再队列中等待,
我们将系统在时间间隔 [t,t+h) 内,系统由状态
Ej变成状态 Ej+1及状态 Ej-1的概率依次为
λjh+o(h),μjh+o(h).系统的输入过程,与延迟与否无关,还是服从参数为 λ的泊松分布,即
λj=λ.但是,
)(
.,
,,
条线路在通话因为最多只有 s
sjs
sjj
j?
于是我们得到
( 9 ),,2,1
),()()()(
)(
1111
j
tPtPtP
dt
tdP
jjjjjjj
j
( 1 0 ) ).()()( 00110 tPtPdt tdP
我们还是更关心时间趋于无穷时,系统与初始状态无关的平衡分布,易求得平衡分布为
( 1 1 ),}
!!
{
,,1,,
!
.1,,2,1,
!
1
1
0
0
0
0
sk
sj
js
k
k
sj
j
j
j
j
ss
a
k
a
P
ssjP
ss
a
P
sjP
j
a
P
注意,当 a<s时,上面 {}内的级数收敛 ;当 a>=s时,
上面 {}内的级数发散,从而 P0=0,这时不存在平衡分布,也就是说等待服务的队列不断增加,队列长度趋于无穷的概率为 1.
令
.0,
}
)/1(!!
){/1(!
)/1(!!
),(
1
0
00
sa
sas
a
k
a
sas
a
P
sas
a
P
ss
a
PasC
ss
k
k
s
s
sj
sj
j
sj
j
上式称为埃尔朗延迟公式,它表示所以线路被占用,因而一个新到来的呼叫不能被立即服务的概率,直接计算可得到平衡系统平均占用的线路数为
.
1
1
aPsjPa
sj
j
s
j
j
