我运筹课件排队论.ppt

6 排队论
基本概念
排队过程的一般表示
排队系统的组成和特征
排队模型的分类
排队系统的求解
几个主要概率分布
经验分布
普阿松分布
负指数分布
单服务台负指数分布排队系统分析
标准M/M/1模型(M/M/1/∞/∞)
系统容量有限的情形(M/M/1/N/∞)
顾客源为有限的情形(M/M/1/∞/m)
一般的排队过程为:顾客由顾客源出发,到达服务机构(服务台、服务员)前,按排队规则排队等待接受服务,服务机构按服务规则给顾客服务,顾客接受完服务后就离开。排队过程的一般过程可用下图表示。我们所说的排队系统就是指图中虚线所包括的部分。
在现实生活中的排队现象是多种多样的,对上面所说的“顾客”和“服务员”要作广泛的理解。它们可以是人,也可以是某种物质或设备。排队可以是有形的,也可以是无形的。
基本概念
排队过程的一般表示
排队系统的组成和特征
尽管排队系统是多种多样的,但从决定排队系统进程的因素来看,它有三个基本的组成部分,这就是输入过程、排队规则及服务机构。
1)输入过程:描述顾客来源以及顾客到达排队系统的规律。包括:
顾客源中顾客的数量是有限还是无限;
顾客到达的方式是单个到达还是成批到达;
顾客相继到达的间隔时间分布是确定型的还是随机型的,分布参数是什么,是否独立,是否平稳。
2)排队规则:描述顾客排队等待的队列和接受服务的次序。包括:
即时制还是等待制;
等待制下队列的情况(是单列还是多列,顾客能不能中途退出,多列时各列间的顾客能不能相互转移);
等待制下顾客接受服务的次序(先到先服务,后到先服务,随机服务,有优先权的服务)。
3)服务机构:描述服务台(员)的机构形式和工作情况。包括:
服务台(员)的数目和排列情况;
服务台(员)的服务方式;
服务时间是确定型的还是随机型的,分布参数是什么,是否独立,是否平稳。
排队模型的分类
,按照系统的三个最主要的、影响最大的三个特征要素进行分类,它们是:顾客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。按照这三个特征要素分类的排队系统,用符号(称为Kendall记号)表示为
X/Y/Z
其中X处填写顾客相继到达的间隔时间分布,Y处填写服务时间的分布,Z处填写并列的服务台个数。
例如M/M/1,表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、单服务台的模型。
后来,在1971年关于排队论符号标准化的会议上决定,将Kendall符号扩充为:
X/Y/Z/A/B/C
其中前三项意义不变。
A处填写系统容量限制;
B处填写顾客源中的顾客数目;
C处填写服务规则(如先到先服务FCFS,后到先服务LCFS)。
约定,如略去后三项,即指X/Y/Z/∞/∞/FCFS的情形。
后面我们只讨论先到先服务FCFS的情形,所以略去第六项。
排队系统的求解
对于一个排队系统,运行状况的好坏既涉及到顾客的利益,又涉及到服务机构的利益,还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施,必须确定一些基本指标,用以判断系统运行状况的优劣。下面介绍几种常用的指标。
1)队长:把系统中的顾客数称为队长,它的期望值记作Ls。而把系统中排队等待服务的顾客数称为排队长(队列长),它的期望值记作Lq。显然有
队长=排队长+正被服务的顾客数。
2)逗留时间:一个顾客从到达排队系统到服务完毕离去的总停留时间称为逗留时间,它的期望值记作Ws。
一个顾客在系统中排队等待的时间称为等待时间,它的期望值记作Wq。显然有
逗留时间=等待时间+服务时间。
3)瞬态和稳态
把系统中的顾客数称为系统的状态。考虑在t时刻系统的状态为n的概率,它是随时刻t而变化的,用Pn(t)表示,称为系统的瞬态。求瞬态解是很不容易的,一般即使求出也很难利用,因此我们常用它的极限
lim Pn(t)=Pn
t→∞
称为稳态或称统计平衡状态的解。
几个主要概率分布
经验分布
在处理实际排队系统时,需要把有关的原始资料进行统计,确定顾客到达间隔和服务时间的经验分布,然后按照统计学的方法确定符合哪种理论分布。
经验分布的主要指标如下:
总时间
平均间隔时间=
到达顾客总数
服务时间总和
平均服务时间=
顾客总数

到达顾客总数
平均到达率=
总时间
顾客总数
平均服务率=
服务时间总和
普阿松分布