排队模型分析法
排队系统的基本组成——排队规则
服务是否允许排队,顾客是否愿意排队。在排队等待 的情况下服务的顺序是什么。 1) 损失制 顾客到达时,若所有服务台均被占,服务机构不
允许顾客等待,此时该顾客就自动离去 2) 等待制 顾客到达时,若所有服务台均被占,他们就排队
等待服务 a) 先到先服务 b) 后到先服务 c) 随机服务 d) 有优先权服务:强拆型优先权、非强拆型优先权 3) 混合制 损失制与等待制的混合 a) 队长(容量)有限的混合制 b) 等待时间有限的混合制 c) 逗留时间有限的混合制
排队系统的基本组成——服务机构
1) 服务台的数目 在多个服务台的情况下,是串联或是并联
2) 服务方式是确定不变的(例如:从汽车装配生产 线下来的产品),还是随机的(例如:人们花时间 购物)
3) 顾客所需的服务时间服从什么概率分布,每个 顾客所需的服务时间是否相互独立,是成批服 务或是单个服务
排队方式
MX/Mr/1/:顾客成批到达,每批到达的数量X 是具有某个离散型概率分布律的随机变量,批 与批的到达间隔时间独立、服从负指数分布; 顾客成批服务、每批为r个顾客,且服务时间独 立、服从负指数分布;有1个服务台;容量为无 穷的等待制系统
定长分布(deterministic distribution)
M/G/1 with embedded Markov chain method 1961: Little proved the Little Formula 1975/6: Kleinrock published the best known textbook in
queueing theory 1982: Wolff proved and popularized the PASTA principle 1981: Neuts introduced the matrix analytic method
一般地,若随机变量t取具有概率密度函数为
e t
f (t) 0
t0 t0
其中λ>0为常数,则t称服从参数为λ的指数分布,其分布
函数F (t)为:
1 e t F(t)
0
t0 t 0
其均值为
E(t) 1
方差值为
1 D(t)
2
爱尔朗(Erlang)分布
k= 0,1,2 …
其中λ>0是常数,则称X服从参数为λ的泊松分布。
其均值为 E( Χ )
方差值为 D( Χ )
泊松分布只需要确定一个参数λ,且事件发生间隔之间服从
负指数分布。
主要应用:广泛应用于各种随机事件的描述或近似
负指数分布(Exponential distribution)
M/M/c/:输入过程是泊松流,服务时间服从负 指数分布,有c个服务台平行服务(0<c),容量 为无穷的等待制系统
M/G/1/:输入过程是泊松流,服务时间独立、 服从一般概率分布,只有1个服务台,容量为无 穷的等待制系统
Ek/G/1/K:相继到达的间隔时间独立、服从k阶 爱尔朗分布,服务时间独立、服从一般概率分布, 只有1个服务台,容量为k(0k<)的混合制系统
D/M/c/K:相继到达的间隔时间独立、服从定长 分布,服务时间独立、服从负指数分布,有c个 服务台平行服务,容量为k(ck<)的混合制系统
几个经典排队系统的符号表示(2)
Mr/M/1/:顾客以每批为固定的r个成批到达, 批与批的到达间隔时间独立、服从负指数分布, 服务时间独立、服从负指数分布,有1个服务台, 容量为无穷的等待制系统
Milestones of Queueing Theory
1909: Erlang published his first paper on queueing theory 1917: Erlang published his famous paper “Solution ….” 1936-47: Palm published “Repairmen in Serving Automatic
“Kendall”记号:X / Y/ Z / A / B / C
第一个字母表示顾客相继到达的时间间隔分布 第二个字母表示服务时间的分布类型 第三个字母表示服务台的数目 第四个字母表示系统的容量 第五个字母表示顾客源中的顾客数目 第六个字母表示服务规则(默认为 FCFS)。
几个经典排队系统的符号表示(1)
排队论所要研究解决的问题(续)
排队论研究排队系统的最优化问题。 最优化问题一般涉及两种类型:
排队系统的最优设计(静态优化)问题。例如,电 话网中的中继电路群数目,分组交换网中的存储空 间大小等,工厂的中间制品仓库大小,医院病床数 量的多少,机场跑道的数量,车站站台数等等。 排队系统的最优控制(动态优化)问题。例如,电 话网中的中继电路群数目的增加与否,路由转发设 备的升级与否,网络基础设施的改造与否等。
0
If k r,T T1 T2 Tr的密度函数为
f r (t )
(t )r 1
(r 1)!
e t
(t 0)
Then
k
r 1,T
T1
T2
Tr
Tr
的密度函数为
1
fr1 (t )
f1 (t
u)
fr (u)du
§1.2 排队论所要研究解决的问题
如果服务设施太少,顾客排队等待的时间就会 很长,这样对顾客会带来不良影响;
面对拥挤现象,人们通常的做法是增加服务设 施,但是增加的数量越多,人力、物力的支出就 越大,甚至会出现空闲浪费。
如何做到既保证一定的服务质量指标,又使服 务设施费用经济合理,恰当地解决顾客排队时间 与服务设施费用大小这对矛盾,就是随机服务系 统理论——排队论所要研究解决的问题。
输入过程 排队规则 服务机构
描述顾客来源及顾客按怎 样的规律抵达。
服务是否允许排队, 顾客是否愿意排队。 在排队等待的情况下 服务的顺序是什么。
服务台的数目 服务时间分布
排队系统的基本组成——输入过程
描述顾客来源及顾客按怎样的规律抵达。 1) 顾客总体数
顾客的来源可能是有限的(例如:公司只有3台 机器时,需要维修的机器数量),也可能是无限 的(例如:排队等候公共汽车的乘客人数 ) 2) 到达类型 顾客是单个到达,还是成批到达 3) 顾客相继到达间隔时间服从什么概率分布,分布 函数是什么,到达的间隔时间之间是否独立 在排队论中,一般假定顾客到达的间隔时间序列 {n|n1}相互独立、同分布。
生灭过程
生灭过程的状态转移流图 生灭过程的平稳分布
、福克-普朗克方程
、系统方程
排队系统
流入=流出”
第3章 排队模型分析法
第1节 排队论简介 第2节 单服务窗简单排队模型 第3节 单服务窗特殊排队模型 第4节 多服务窗排队模型
第1节 排队论简介
排队论,又称为随机服务系统理论,是在随机过 程基础上发展起来的一门研究资源有限性和需求 随机性的数学方法,通过研究各种服务系统在排 队等待中的概率特性,来解决系统的最优设计和 最优控制。
排 队 论 起 源 于 20 世 纪 初 丹 麦 电 信 工 程 师 A.K. Erlang对电信系统的研究,现已发展成为一门应 用广泛的学科,在电信、交通运输、生产与库存 管理、计算机系统设计、计算机通信网络、军事 作战、柔性制造系统和系统可靠性等众多领域, 有着非常重要的应用。
排队论的发展史
排队系统的理论基础
随机变量(离散型,连续型); 概率及概率分布函数、概率密度函数; 数学期望(均值)、方差(偏差); 概率的归一性(正则规则); 生灭过程的系统方程。
§1.3 排队系统的符号表示方法
一个排队系统是由许多条件决定的,为简明起 见,在经典的排队系统中,常采用3~6个英文字母 表示一个排队系统,字母之间用斜线隔开。
即
k
T T1 T2 Tk Ti
i 1
理解:对于k个串联的服务台,每个服务台的服务时间相 互独立,均服从负指数分布,则每个顾客总的服务时间服 从Ek分布。
f(t)
20
6 45
23 k=1
1
当k=1, Ek为负指数分布, 完全随机;当k足够大 时,Ek分布近似于正态 分布;当k →∞时,X以 概率1取值 1/ μ ,即为 定长分布,因此Ek分布 t 可以看作随机模型和非
初期(10‘s-40‘s)
主要研究应用于电话网和远程通信系统等无队列排 队系统
中期(40‘s-60’s)
推广应用到军事、运输、生产、社会服务等领域, 主要研究有队列的排队系统和排队网络
近期(60‘s-今)
主要研究大规模复杂排队系统的理论分析、数值分 析和近似分析,尤其注重对业务突发性和带有各种 网络控制的排队系统的研究
1. 单服务员(台)的排队系统
顾客到达 …
2. 多服务员(台)的排队系统
顾客到达
一个队列
…
服务员 服务完成离去
服务员1
服务员2 …
服务员n
服务完成离去
多个队列 顾客到达 串联 顾客到达
…
…
服务员1
…
服务员2
……
…
服务员n
服务员1
…
服务完成离去 服务完成离去 服务完成离去
服务员2 离去
排队系统的分类
1、均值
E[X ] k
k
3、均方差 X
2、方差
D[X ]
k 2
4、方差系数
1
k
T1
T2
T3
T4
T5 T6
t 0
T’1