运筹学18排队论.ppt

排队论(Queueing Theory)(随机服务系统)
12/10/2017
1
排队论(Queueing Theory),也称随机服务系统理论,是运筹学的一个重要分支之一。
1909年,丹麦哥本哈根电子公司电话工程师A. K. Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话,通信中的问题相联系的,这些问题仍然是排队论传统的应用领域。
近年来在计算机通讯、网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到了广泛的应用。
12/10/2017
2
设备修理修理工人
修理工人领取配件管理员
病人就诊医生
打电话通话交换台
文件打印打印机
飞机降落跑道指挥机构
顾客就餐服务员
汽车通过路口红绿灯
§ 排队系统的组成与特征
三个基本组成部分:;;。
§1 排队系统的基本概念
输入即为顾客的到达,可有下列情况:
1)顾客源:有限的,或无限的。
2)到达方式:成批到达,或单个到达。
3)到达间隔时间:随机的,或确定的。
4)到达关联性:相互独立的,或关联的。所谓独立指t时刻顾客的到达对t时刻以后顾客的到达无影响。
5)输入过程可以是平稳的(stationary),也可以是非平稳的。平稳的,指顾客相继到达间隔时间分布及其参数(均值、方差)与时间无关;非平稳的则与时间相关,非平稳的处理比较困难。
1. 输入过程
2. 排队规则
1)队列数:单列,或多列。(多列时包括各列间可以相互转移、不能相互转移;中途可退出、中途不能退出等。)
2)队列的空间:有容量限制,或无容量限制。也可分为有形的和抽象的。
3)顾客到达后接受服务,服务分为即时制(损失制)和等待制。即时制不允许排队,不形成队列;而对于等待制将会形成队列,顾客可以按以下规则接受服务:先到先服务FCFS;后到先服务LCFS;随机服务RAND;有优先权服务PS。
3. 服务机构
1)服务机构:单服务台,或多服务台。
2)服务方式:单个顾客服务,或成批顾客服务。
3)服务时间:确定型(定长时间),或随机型。
4)服务时间的分布:假定是平稳的。
我们研究的问题是:输入服从某种分布,顾客的到达是相互独立的平稳过程;各列间不能相互转移、中途不能退出;顾客单个到来,服务方式FCFS。
最主要的、影响最大的特征是:
顾客相继到达间隔时间的分布
服务时间的分布
服务台数
,1953提出了分类法,称为Kendall记号:X/Y/Z
1971年又扩充为:X/Y/Z/A/B/C
§ 排队系统的模型分类
式中:
X ——表示顾客相继到达间隔时间分布;
Y ——表示服务时间分布;
各种分布符号如下:
M—负指数分布(负指数分布具有无记忆性,即Markov性);
D—确定型(Deterministic)分布;
Ek—K阶爱尔朗分布Erlang;
GI—一般相互独立随机分布(General Independent);
G —一般随机分布。