4.1第六章 排队论.pdf

第六章随机服务系统理论
排队论
Queuing Theory
确定型只是随机现象的特例
随机服务系统基础
•系统的输入与输出是随机变量
• 于1909~1920年发表了一系列根据话务量计
算电话机键配置的方法,为随机服务理论奠定了基础
•又称为排队论(Queuing Theory)或拥塞理论(Congestion
Theory)
•应用广泛
•交通行业应用:交叉口/高速收费站/机场航班…
2
基本要素
排队系统的三个基本组成部分.
•输入过程(顾客按照怎样的规律到达);
•排队规则(顾客按照一定规则排队等待服务);
•服务机构(服务机构的设置,服务台的数量,服务的
方式,服务时间分布等)
排队系统
顾客服务完离开
顾客来源队列服务机构
3
输入过程
•顾客源
–有限
–无限
•经常性的顾客来源
–顾客到达间隔时间: 到下一个顾客到达的时间
–服从某一概率分布(确定型/随机型)
•顾客的行为假定
–在未服务之前不会离开
–当看到队列很长的时候离开
–从一个队列移到另一个队列
4
排队服务规则
–队列容量
•有限/无限

–排队规则
•损失制
•等待制:先到先服务(FCFS),后到先服务(LCFS),
随机服务(RS),优先权服务(PS)
•混合制
•逐个到达,成批服务;成批到达,逐个服务
5
服务机构的组织方式与服务方式
–单通道和多通道
–并联服务
–串联服务
–串并联服务
顾客到达 1  2  3 顾客离开
顾客离开
1 顾客到达 1 顾客离开
顾客到达
2 顾客离开
顾客到达 2 顾客离开
3 顾客离开
顾客到达 3 顾客离开
银行服务-叫号系统机场安全检查通道 6
符号表示
顾客到达时间间隔分布/服务时间分布/服务台数目/
排队系统允许的最大顾客容量/顾客总体数量/排队规则
(扩充的Kendall 符号)-- Kendall’s notation
常用符号
• M—泊松分布(负指数分布)
• Ek—k阶爱尔朗分布
• D—确定型分布
• G—一般分布
• M/M/1/K/∞/FCFS—顾客到达服从泊松分布,顾客的服务时
间服从负指数分布,单通道,系统容量有限(K)而顾客源
无限,先到先服务的排队系统
7
排队系统营运指标
队长:系统中的顾客数量的期望值
排队长:系统中正在等待的顾客数量期望值
逗留时间:顾客在排队系统中的总时间(等待时间与被
服务时间之和)的期望值
排队时间:顾客的排队等待时间的期望值
忙期:服务机构连续繁忙的时间长度
服务强度:顾客到达率的期望值与服务率的期望值之比
8
与服务系统性能相关的特性
•服务系统存在来自两个矛盾方面的要求
–顾客希望服务质量好,如排队等待时间短,损失率低
–系统运营方希望设备利用率高
•给用户一个经济上能够承受的满意的质量
•哪些系统特性会影响系统的性能?
–服务机构的组织方式与服务方式
–顾客的输入过程和服务时间分布
–系统采用的服务规则
9
顾客到达分布和服务时间分布
概述
•顾客的服务时间由于多种原因具有不确定性,最好的描述
方法就是概率分布;同样顾客到达的间隔时间也服从一定
的概率分布
1 2 3 4
顾客1 2 3 4
到达时刻
开始
服务时刻 w2 w3
服务
t
终结时刻 h1 h2 h3 空 h4
1 2 3 4