运筹学排队论.ppt

第五章排队论(Queuing Theory)
排队论(queuing),也称随机服务系统理论,是运筹学的一个主要分支。
1909年,丹麦哥本哈根电子公司电话工程师A. K. Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话,通信中的问题相联系的,并到现在是排队论的传统的应用领域。近年来在计算机通讯网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。
1
§ 排队系统的组成与特征
排队系统一般有三个基本组成部分:;;。现分别说明:
§1 排队系统的基本概念
2
输入即为顾客的到达,可有下列情况:
1)顾客源可能是有限的,也可能是无限的。
2)顾客是成批到达或是单个到达。
3)顾客到达的间隔时间可能是随机的或确定的。
4)顾客到达可能是相互独立的或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。
5)输入过程可以是平稳的(stationary)或说是对时间齐次的(Homogeneous in time),也可以是非平稳的。输入过程是平稳的是指顾客相继到达的间隔时间分布和参数(均值、方差)与时间无关;非平稳的则是与时间相关,非平稳的处理比较困难。
1. 输入过程
3
2. 排队规则
1)顾客到达后接受服务分为即时制(损失制)和等待制。即时制不形成队列,而对于等待制将会形成队列,顾客可以按下规则接收服务:
(1)先到先服务 FCFS (2)后到先服务 LCFS (3)随机服务RAND (4)有优先权服务 PR。
2)从队列的空间可分为有容量限制和无容量限制。
3)从队列数可分为单列和多列。
4
3. 服务机构
1)服务机构可以是单服务员和多服务员服务,这种服务形式与队列规则联合后形成了多种不同队列,不同形式的排队服务机构,如:
5
上述特征中最主要的、影响最大的是:
顾客相继到达的间隔时间分布
服务时间的分布
服务台数
,1953提出了分类法,称为Kendall记号(适用于并列服务台)即:[X/Y/Z]:[A/B/C]
2)服务方式分为单个顾客服务和成批顾客服务。
3)服务时间分为确定型和随机型。
4)服务时间的分布在这里我们假定是平稳的。
§ 排队系统的模型分类
6
式中:X——顾客相继到达间隔时间分布。
M—负指数分布Markov,D—确定型分布Deterministic, Ek—K阶爱尔朗分布Erlang, GI—一般相互独立随机分布(General Independent), G —一般随机分布。
Y——填写服务时间分布(与上同)
Z——填写并列的服务台数
A——排队系统的最大容量
B——顾客源数量
C——排队规则
如[M/M/1]:[∞/∞/FCFS]即为顾客到达为泊松过程,服务时间为负指数分布,单台,无限容量,无限源,先到先服务的排队系统模型。
7
§2 排队论基本理论总廓
§ 排队论研究的基本问题
:即通过对排队系统主要参数的统计推断和对排队系统的结构分析,判断一个给定的排队系统符合于哪种模型,以便根据排队理论进行研究。
:即研究各种排队系统的概率规律性,主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。
:即包括最优设计(静态优化),最优运营(动态优化)。
8
§ 排队问题求解(主要指性态问题)
求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标,估计服务质量,确定系统的合理结构和系统参数的合理值,以便实现对现有系统合理改进和对新建系统的最优设计等。
排队问题的一般步骤:
1. 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布(可实测)。
2. 研究系统状态的概率。系统状态是指系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率,也称瞬态概率。
9
求解状态概率Pn(t)方法是建立含Pn(t)的微分差分方程,通过求解微分差分方程得到系统瞬态解,由于瞬态解一般求出确定值比较困难,即便求得一般也很难使用。因此我们常常使用它的极限(如果存在的话):
稳态的物理意义见右图,系统的稳态一般很快都能达到,但实际中达不到稳态的现象也存在。值得注意的是求稳态概率Pn并不一定求t→∞的极限,而只需求Pn’(t)=0 即可。
过渡状态
稳定状态
pn
t
图3 排队系统状态变化示意图
称为稳态(steady state)解,或称统计平衡状态(Statistical Equilibrium State)的解。
10