排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

第四章 排队模型

两类排队模型:

1. Markov 排队模型

2. 非Markov 排队模型

Markov 排队模型:

4-0 Little 定理

1961 年 J.D.Little 证明 1974 年 S.Slidhan 一般性证明

定理 : 在极限平稳状态下,排队系统内顾客平均数L 系 和 顾客在系统内平均逗留时间W 系 之间的关系,不管到达流的分布如何,也不管服务规则如何,均有以下关系:

为到达流的强度

系λλ1

4.-=L W

证明:

设 X(t) ---- t 时刻前到达的瞬时顾客数, Y(t)--- t 时刻前离开的瞬时顾客数.

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

Y(t)

在稳定后,流入与流出的顾客数应相等, 则在t 时刻留在系统内的顾客数为:

Z(t)=X(t)-Y(t)

在足够长的时间T 来考虑有:

队系

系系系同理可以证明所以有逗留时间系统内每个顾客的平均时

间的总和所有顾客在系统内逗留时间个顾客在系统内的逗留第其中的小面积的总和高度为长度为阴影部分的面积W L W L W T

t t i t t T

t T t T T dt

t Z T L i

i

i

i i i

i

i

i i T

.:

.:.

..,:

.11

]1*[1][1)(10λλλλλ

==--=--=

?=

===∑∑∑∑?

4-1 M/M/1/0 (单通道损失制)

服务员数:n=1 队长:m=0

M -- 到达流为Poisson,流强λ

M -- 服务时间服从指数分布:)0()(>=?-t e t f t μμ 状态为系统内顾客数,I={0,1}

"0"表示服务员闲,其概率为:P 0(t);

"1"表示服务员忙,其概率为:P 1(t); 状态转换图:

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

Fokker-Plank k 方程:

可得:

)0(1

)0(:341)()(24)()()(14)()()(1010011100==-=+-+-=-+-=??

P P t P t P t P t P t P t P t P t P 初始条件λμμλ

联立求解4-1与4-3得:

λ

μ

λλμλμμ

λλ

μλλλ

μλ

λ

μμμ

μλμλμλμλ+=

∞+=

∞∞

→==+-+=-=++

+=

-++-=-+-=+----+-?

?

)(,

)()

0(,1)0(0)(1)()(4

4)()()()(1[)()(1010)(01)(000000P P t P P t e t P t P e t P t P t P t P t P t P t

t

定义:

系统负载能力:μ

λρ=

指标:

(1) ρ

μ

λμ

+=

+===110P Q 请求服务的顾客数

被服务顾客数 (2) 绝对通过能力:

ρ

λμλλμλ+=

+=

==1Q A 数单位时间被服务的顾客

(3) 损失概率(即顾客来时,系统服务员忙,顾客离去)

ρ

ρμ

λλμ

λμ+=

+=+-=-==1111Q P P 损

例一:一条电话线,呼叫率为:0.8次/分(λ=0.8),每次平均通话时间为:

τ=1.5分。求相对通过能力,绝对通过能力,损失率,比较实际通过能力与最大(额面)通过能力。

解:

分次通过能力额面最大电话损失概率绝对通过能力相对通过能力系统负荷水平额损/667.05

.11

1

:)(545.011:364

.02

.118

.01:455

.02.111

11:2.1667

.08

.0:667.05

.11

1

0==

==

=-=+=

=+=

+=

=+=+=====

==

=

μτ

ρ

ρ

λ

ρμλρτ

μA Q P A P Q Erlang

4-2 多通道损失制 ( M/M/n/0)

服务员数:n

系统内最大顾客数(排队最大顾客数):m=0

系统状态:"0"---n 个服务员闲,系统内顾客数为0; "1"---1个服务员忙,系统内顾客数为1,(n-1)个服务员闲; …………………………………….. "k"---k 个服务员忙,系统内顾客数为k ,(n-k)个服务员闲; "n"---n 个服务员忙,系统内顾客数为n 。

系统状态转换图:

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

(1) 求瞬态解:

n B P A P μ-=?

→?

?

(2) 求稳态解:

[ P 0,P 1,………P n ]

a. B A P n μ1

-→

?

-=

b. 利用状态转换图:

n k i k P k P n P P P P P n P P n P n P

k k P P P k P k P

P P P P P P P P P n

i i

k

k n

k k

n

n n

n n n k

k k k

k ......2,1,0!

!

!

1

1

)!

.....

..........!

2!11(1........!

)("

"..................................................................................!!)()("

"...............................................................................!2!2)(2:

"1":"0"0

02

0100

10

010

2

0222

100

110==

=

=++

+

=++=========

==

=∑

∑==--ρρρ

ρρρ

ρμλρμλμλρμλμλμ

λρρμλ

μλ对对对对

指标:

(1) 系统损失概率:

0!

P n P P n

n ρ=

=损

(2) 系统的相对通过能力:

0!

11P n P Q n

ρ-

=-=损

(3) 系统绝对通过能力:

)1()!

1(0n n

P P n Q A -=-

==λρλλ

(4) 占用的服务员的平均数=占用通道的平均数:

μ

λ

ρ

ρρρρρρρρρρρρρρA

A

P P n n P P n k P k P k

P P k P k k

kP k E n n

n n

n k k

n k k

n

k k n

k k

n

k k

n

k k =

=-=-=-=-

=∑

=∑

-=∑

-=∑=∑=-=-==-===]

1[]!1[]!1[]!

!

[!

)!

1()!

1(!

][0001

01

011

00

100

(5) 通道利用率:

n

k E ][=

η 例二:某电话总机有三条中继线(n=3),其它条件同例一,求系统的极限

概率,绝对与相对通过能力,损失概率,占用通道的平均数。 解: λ=0.8 μ=0.667 ρ=0.8/0.667=1.2

极限概率:

090

.0312.0*228.0!

3224.0312.0*7.0!

2374.0312

.0]!

3!

21[03

302

20113

2

0===

======+

+

+=-P P P P P P P ρρρρρρ

系统损失概率:

09.03==P P 损 相对通过能力:

91.009.011=-=-=损P Q

绝对通过能力:

728.091.0*8.0===Q A λ 占用通道的平均数:

09.1667

.0728.0===-μ

A k

通道利用率:

363.03

09

.1====

-

n k η 比较n=1,与n=3的情况:

P 损 Q A k η

n=1 0.545 0.455 0.364 0.545 0.545 n=3 0.09 0.91 0.728 1.09 0.363 由上表可见,增加外线数n 可使损失概率减小,通过能力增加,通道利用率减小。

4-3 单通道等待制( M/M/1/∝=M/M/1)

n=1 一个服务员

m=∝ 无穷大队长,服务员有空,顾客被服务;服务员忙,顾客排队,

直到得到服务

"状态"定义为系统中的顾客数, " 0 " ---系统中无顾客,服务员闲;

" 1 " ---系统中有一个顾客,正在服务, 服务员忙; " 2 " ---系统中有2个顾客,1个正在服务,另一个在排队,服务员忙; ……………………………………………… " k " ---系统中有k 个顾客,1个正在服务,(k-1)个在排队,服务员忙。 ……………………………………………..

可以证明:当 ρ<1 时,虽然状态数为无穷大,仍然存在极限概率。 其状态转换图:

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

列稳态K-F 方程:

Z

z g P P P P P P P P P P P P P P P P P P P k k k k

k k k ρ

ρ

ρρρ

ρρρρρρμ

λ

μλμλρμ

λ

μλ--∞

==

?-=-==

=++++=++++===+=+==

=∑1100202100

20221

200011

0)()

1(11

1.........).......1(1.....

..............

.................)()(

求系统指标:

(1) 系统内顾客数的均值:

..

λ

μλ

ρρρρρρρ

ρρρρρρρρρρρρ-=

-=--=--=∑-=∑-=∑-=∑=∞=-∞

=1)1(1)1()1()

1()1()1()1(2010

d d d d k

k kP L k k k k k k 第二种方法:

λ

μλρρρρρρρ-=-===--=--=

=1])([

][)1()

1()(11)(12

Z dz z dg k E L Z dz z dg Z

z g

(2) 顾客在系统中平均逗留时间:

利用Little 定理:

λ

μρμλ

-=

-==1)

1(1L W (3) 顾客排队平均队长: L q =L - L s

Ls -- 在服务的顾客数平均值,由于只有一个服务员,他的平

均值就是忙的概率P 忙; 而:P 忙+P 0=1

Ls = P 忙=1-P 0=1-(1-ρ)=ρ 所以有:

)

(112

2λμμλρρρρρ

-=

-=--=-=Ls L L q (4) 顾客平均排队时间:

)

1(2ρλρλ

-=

=

q

q L W

(5) 系统内有多于一个顾客的概率:

P(k>1)=1-P 0-P 1=1-(1-ρ)-ρ(1-ρ)=ρ2 (6) 系统内有多于m 各顾客的概率:

111

)1(11)(++==--=∑-=>m m m

k k P m k P ρρ

(7) 系统内顾客数的方差:

2

02)

1()()(ρρ-=

∑-=∞

=k k P L k k D 证明:利用矩生成函数 (母函数)

ρρ

ρρρρρρ

ρ

ρρρρρρρρρρρρρρρρρρρρ--

++--='-'+''=-=

'==--=-----=''--=

--=

'--=∑-=∑-=∑=∞

=∞

=∞

=11)1()1(2)]1([)1()1(][1)1(][)1()

1(2)1())(1(2)1()()1()

1()1()1()(11)()1()1()(3

22

324

2

20

g g g k D g k E L Z Z Z Z g Z Z Z g Z

Z Z Z P z g k k

k k

k k k k 2

)1(ρρ-=

或写成均方差:

ρ

σρ

ρσ1

)

()

()(:1)(=

=

-=

=

k E k k V k D 偏离系数

(8) 排队中的顾客数的方差:

2

4322

23

322

3

32

222221

2

12

1

12

12

)1()1(1)1()1(2)]1([)1()1()(1)1()()1()

1(2)()1()

1()(111)1()1()

111

)(1()1(]

1)[1()1()1()1()1()1()()

1(0)10(01)1()1(1

1,0)(ρρρρρ

ρρρρρρρ

ρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρ--+=

---+--='-'+''=-='==--=''--=

'

-+--=

--+

-=---+-=∑--+-=∑-+-=∑-+-=∑=?

?

?>>===-=-+-=∴

??

?≥-==∑=∞

=∞

=∞

=+∞

=+∞

=q q q q

q q

q q q q q q

q q q

q q q

q q q q q q

g g g q D g q E L Z Z g Z Z g Z

Z Z Z

Z Z

Z Z Z Z P Z g k q k k q P k k k k q qP q D

(9) 顾客在排队时间的分布,均值与方差:

先求排队时间的分布密度:

设随机变量:w q =第n+1个顾客排队等待服务的时间,即前面已有n 个顾客在系统中,其中一个在服务,n-1个在排队,这第n+1个顾客要等n 个顾客服务完毕后才能得到服务,所以等待时间为:w q =s 1+s 2+…..+s n ;而s 1,s 2,…..s n 服从均值(1/μ)的指数分布,则w q 服从k-Erlang 分布,其分布函数为:

)!

1()()(1-=--n t e t g n t

w q μμμ 考虑到n 可从1到∝变化,所以有:

t

t

t

m m t

n n t

n n

n t

n

n w w e

e e m t e

n t e n t e

P t g t f q q .)..(..1.11.1

11)1(.)1()!

()()1()!1().()1()

1()!

1()()()(λμλμμμμρρμρρμλρρμρμρρμρρμμ+--

=--∞=-∞

=--∞

=-=-=∑

-=-∑

-=∑--=∑=

平均排队时间为:

)

1(.)1(..)1()(.0.)..(0

.)..(0

ρμρρμρμρρλμλμ-=

?-=?-=?=∞

--∞--∞dt e t dt e t dt t f t W t t w q q

(10) 顾客在系统中逗留时间的分布,均值:

第n+1个顾客在系统中逗留时间为:

t

n n t

n t n

n n n

w w t

n

n w n n e n t e

e n t P t

f t f e n t t

g Erlang n s s s s w .)..(0

..10

.1121)1(!).()1()

1(!

)()(!

)(:1....λμμμμρμμρρμρρμμ--∞

=--+∞

=-++-=∑

-=-∑

=∑

=

=+++++=分布阶它服从

顾客在系统中逗留的平均时间:

)

1(1.)1(.).1()(.0

)..(0

.)..(0

ρμρμρμλμλμ-=

?-=?-=?=∞

--∞

--∞

dt

e t dt

e t dt t

f t W t t w

验算:)

1(11

)

1(ρμμ

ρμρ-=

+-=

+=s q W W W 例:一个批处理计算机系统,作业处理时间服从指数分布,平均时间为三分钟/作业,作业的到达服从Poison 分布,平均为:1作业/4分钟,服务规则为:先到先服务(FCFS)。

求:1) 一个作业处理时间超过 20 分钟的概率;

2) 在排队中的顾客平均数。

3) 我们决定:当工作负载增加到使系统的平均处理时间超过30 分钟,计算机容量将增加,这中情况下,作业的平均到达率λ应为多少?超过目前负载的百分比多少?此时在系统中的平均作业数是多少?

解:

1) 设该系统是一个M/M/1排队系统,

τ=4 Min λ=1/τ =1/4=0.25 jobs/min w s =3 min/job μ=1/w s =1/3=0.333 jobs/min 负载:ρ=λ/μ =0.25*3=0.75 在系统中逗留平均时间:

min 12

75

.013

)1(1=-=-=

ρμW

求在系统逗留时间超过20min 的概率: 先求w 的分布函数:

1889

.0)20()(1)(]

1[]

1[]0[)(1)1()1()()(666.112

20.)..(.).(.).(0

===>=≤-=>-=-=---=?-=?=≤---

-

--+-+-e e

w P e t w P t w P e e t e dt

e dt t

f t w P w w

t w w w t t t t t

w w λμλμλμλμρμρμ

2) 如果不算排队长度为0的情况,

此时队长分布为:

)

1(;,........)1()1()1()

1(.......2,1122

321

11

1

1ρρρρρρρρρρρρ-==+-+-=-∑=∑'=∑-=='-''∞

=+∞=∞=+q q q q q q q

q q q q P P P P P q 得归一化将用

它的生成函数为:

=

-----=--

--=---=-∑-=∑-=∑-=∑=-∞

=''-∞

=''

-∞

=''

-'∞

=''

'')

1()1)(1()1(11)1(]11)[

1(]1)()[1()

()1()1(.)(10

1

1

1

111Z Z Z Z Z Z Z Z Z Z Z

P z g q q q q q q q q q q q ρρρρρρρ

ρ

ρρρρρρρρρ

ρρρ

ρρ

则不计算排队为0的平均队长为:

jobs g q q E L q q 475

.011

11)1()0/(=-=-==>''=''ρ

若计算排队为0的平均队长为:

jobs L q 25.225

.075.012

2==-=ρρ

3) 当负载ρ增加使W=30 Min ,而Ws=3min ,μ=1/3时的λ'应为:

9.0333

.03.0:%

2025.025

.03.0:

min

/25.0;

min /3.030

131301301

=='=

'=-==-=-

='='

-=

μλρλλμλλμ系统中的平均作业数超过的百分比为原先的jobs jobs W

jobs L 99

.019

.01=-='-'=

'ρρ

4-4 单通道混合制(M/M/1/m )

服务员数n=1 最大队长为:m

系统状态为系统内顾客数,当顾客到来,排队满员时(q=m),顾客离去。

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

列F-P 方程:

μ

1

(10)

1

10

1====

=∑+=++m k k

m m k k P

P P P P P P ρ

ρμ

λρρ

可求出:2

11

11020+=

=--=

+m P P m ρρρ

)1.....(2,1,01)1(+=--=

m k P k k ρρρ

指标:

1) 系统损失概率:

2

101

11)1(++++--===m m m m P P P ρρρρ

2) 系统相对通过能力:

211)

1(11++---=-=m m P Q ρ

ρρ损 3) 绝对通过能力:

A=λQ

4) 平均队长:

先算q 的分布:

???

????=--=--=+++m

q q P m q m q ....2,11)1(0

1121

22ρρρ

ρρ

∑-

-∑-+-=∑-+-=∑-+-=∑=-∞

+=∞

=∞

=∞

=+∞

=+1

2

12

12

2

]

)(1)()[1()1()()1()1()1()1()()1(m q q

q q

q q

q q

q q q q q m Z Z Z Z Z P Z g ρρρρρρρρρρρρρ

)

1)(1()]1(1[)1()1(]

)([]))(1(1)[1()[1()()1(]

1)()[1()1()(1)[1()1(22

12

2

1

20

)

1(2

+++∞=++---+-='=--++---='----+-=∑---+-=m q

q m m q

m m p m p m m g L Z Z Z Z m Z Z g Z

Z Z Z Z Z

ρρρρρρρρρρρρρ

ρρρρρρρρρρρρ

5) 系统内顾客数的均值:

2

22

22

2

01)1)(1()]1(1[11+++++--+---+-=--=

-=+=m m m m m m s s

q m m L P L L L L ρρρρρρρρρρρ

6) 逗留时间与排队时间:

λ

λ

q

q L W L

W =

=

4-5 (M/M/1,)状态依赖服务

特点:服务员的服务速率随队长而变化

??

?>≤=m q m q 2

1

μμμ

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

4-6 多通道等待制(M/M/n /∞=M/M/n)

服务员数n 队长为无限

系统状态为系统内顾客数 状态转换图:

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

4-7 多通道混合制(M/M/n/m)

服务员数:n 队长为m

状态为系统内顾客数. 状态转换图:

λ λ λ λ 11 12

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

.

4-8 多通道等待制(服务员能力不等)

年个服务员,能力不等,分别为μ1 μ2……μn 系统总能力:

∑==n

i i 1μμ

n=2时比较简单,定义为:1号服务员,2号服务员; 定义:?1为选择1号服务员的概率,

?2为选择2号服务员的概率, ?1+?2=1,

令?1 = ?,则:?2=1- ?

1

1

22

1<=+=μμ

αμμλρ系统总负载

定义:状态为系统内顾客数

状态:"0" --- k=0两个服务员均为闲,q=0.

"01" --- k=1,2号服务员忙,1号服务员闲,q=0 "10" --- k=1,1号服务员忙,2号服务员闲,q=0 "2" --- k=2,两个服务员均忙,q=0 "3" --- k=3,两个服务员均忙,q=1

状态转换图:

排队论第三部分-第四章 排队模型,第五章 MG1, 第六章 G1 M 1

列方程:

相关推荐
相关主题
热门推荐