《我的运筹课件排队论》由会员分享,可在线阅读,更多相关《我的运筹课件排队论(21页珍藏版)》请在金锄头文库上搜索。
1、6 排队论 6.1 基本概念6.1.1 排队过程的一般表示6.1.2 排队系统的组成和特征6.1.3 排队模型的分类6.1.4 排队系统的求解 6.2 几个主要概率分布6.2.1 经验分布6.2.2 普阿松分布6.2.3 负指数分布 6.3 单服务台负指数分布排队系统分析6.3.1 标准M/M/1模型(M/M/1/)6.3.2 系统容量有限的情形(M/M/1/N/)6.3.3 顾客源为有限的情形(M/M/1/m)一般的排队过程为:顾客由顾客源出发,到达服务 机构(服务台、服务员)前,按排队规则排队等待接 受服务,服务机构按服务规则给顾客服务,顾客接受 完服务后就离开。排队过程的一般过程可用下图
2、表示 。我们所说的排队系统就是指图中虚线所包括的部分 。在现实生活中的排队现象是多种多样的,对上面所 说的“顾客”和“服务员”要作广泛的理解。它们可以 是人,也可以是某种物质或设备。排队可以是有形的, 也可以是无形的。6.1 基本概念6.1.1 排队过程的一般表示6.1.2 排队系统的组成和特征尽管排队系统是多种多样的,但从决定排队系统进程的因素来看,它有三个基本的组成部分,这就是输入过程、排队规则及服务机构。1)输入过程:描述顾客来源以及顾客到达排队系统的规律。包括:顾客源中顾客的数量是有限还是无限;顾客到达的方式是单个到达还是成批到达;顾客相继到达的间隔时间分布是确定型的还是随机型的,分布
3、参数是什么,是否独立,是否平稳。2)排队规则:描述顾客排队等待的队列和接受服务的次序。包括:即时制还是等待制;等待制下队列的情况(是单列还是多列,顾客能不能中途退出,多列时各列间的顾客能不能相互转移);等待制下顾客接受服务的次序(先到先服务,后到先服务,随机服务,有优先权的服务)。3)服务机构:描述服务台(员)的机构形式和工作情况。包括:服务台(员)的数目和排列情况;服务台(员)的服务方式;服务时间是确定型的还是随机型的,分布参数是什么,是否独立,是否平稳。6.1.3 排队模型的分类D.G.Kendall在1953年提出了一个分类方法,按照系统的三个最主要的、影响最大的三个特征要素进行分类,它
4、们是:顾客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。按照这三个特征要素分类的排队系统,用符号(称为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/
5、Z/FCFS的情形。后面我们只讨论先到先服务FCFS的情形,所以略去第六项。6.1.4 排队系统的求解对于一个排队系统,运行状况的好坏既涉及到顾客的利益,又涉及到服务机构的利益,还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施,必须确定一些基本指标,用以判断系统运行状况的优劣。下面介绍几种常用的指标。 1)队长:把系统中的顾客数称为队长,它的期望值记作Ls。而把系统中排队等待服务的顾客数称为排队长(队列长),它的期望值记作Lq。显然有队长排队长正被服务的顾客数。2)逗留时间:一个顾客从到达排队系统到服务完 毕离去的总停留时间称为逗留时间,它的期望值记作 Ws。
6、一个顾客在系统中排队等待的时间称为等待时间,它的期望值记作Wq。显然有逗留时间等待时间服务时间。3)瞬态和稳态把系统中的顾客数称为系统的状态。考虑在t时刻系统的状态为n的概率,它是随时刻t而变化的,用Pn(t)表示,称为系统的瞬态。求瞬态解是很不容易的,一般即使求出也很难利用,因此我们常用它的极限lim Pn(t)Pnt称为稳态或称统计平衡状态的解。6.2 几个主要概率分布6.2.1 经验分布在处理实际排队系统时,需要把有关的原始资料 进行统计,确定顾客到达间隔和服务时间的经验分布 ,然后按照统计学的方法确定符合哪种理论分布。经验分布的主要指标如下:总时间平均间隔时间=到达顾客总数服务时间总和
7、平均服务时间=顾客总数到达顾客总数平均到达率=总时间顾客总数平均服务率=服务时间总和6.2.2 普阿松分布设N(t)表示在时间区间t0,t0+t)内到达的顾客数,是随机变量。当N(t)满足下列三个条件时,我们说顾客的到达符合普阿松分布。这三个条件是:(1)平稳性 在时间区间t0,t0+t)内到达的顾客数N(t),只与区间长度t有关而与时间起点t0无关。(2)无后效性 在时间区间t0,t0+t)内到达的顾客数N(t),与t0以前到达的顾客数独立。(3)普通性 在充分短的时间区间t内,到达两个或两个以上顾客的概率极小,可以忽略不计,即Pn(t)o(t)n=2 在上述三个条件下可以推出(t)nPn(
8、t) e-t n=0,1,2,n!其中表示单位时间平均到达的顾客数,即为到达率。不难算出,N(t)的数学期望和方差分别是:EN(t)t VarN(t)t6.2.3 负指数分布随机变量T的概率密度若是e-t t0fT(t)0 t0 则称T服从负指数分布,它的分布函数是1-e-t t0FT(t)0 t0T的数学期望和方差分别为:ET1/, Var(T)1/2负指数分布具有下列性质:(1)无记忆性或马尔柯夫性,即 PTt+s / TsPTt(2)当顾客到达符合普阿松分布时,顾客相继到达的 间隔时间T必服从负指数分布。 对于普阿松分布,表示单位时间平均到达的顾客数,所以1/表示顾客相继到达的平均间隔时
9、间,而这正和ET的意义相符。服务时间符合负指数分布时,设它的概率密度函数和分布函数分别为fv(t)e-t; Fv(t)1-e-t (t0)其中表示单位时间能够服务完的顾客数,为服务率;而1/表示一个顾客的平均服务时间,正是v的期望值。系统的运行指标:(1)、系统中顾客数的期望值 Ls(2)、系统中排队等待顾客数的期望值 Lq(3)、系统中顾客平均的排队等待时间 Wq(4)、系统中顾客的平均逗留时间 Ws(5)、有效到达率 e(6)、系统中 Ls,Lq,Wq,Ws,e 之 间的关系Ls = n pn, Lq = ( n - c ) pn ,Ws = Ls / e, Wq = Lq / e, Ws
10、 = Wq + 1 / , e = n pn = n pn ,Ls = Lq + e / 。6.3 单服务台负指数分布排队系统分析6.3.1 标准M/M/1模型(M/M/1/)排队系统的状态n随时间变化的过程称为生灭过程, 设平均到达率为,平均服务率为,负指数分布排队系统( M/M/1/)的生灭过程可用下面的状态转移图表示:01 n-1n n+1. 稳态概率方程如下: -P0=P1Pn-1+Pn+1=Pn+Pn 设=/1,考虑到Pn=1,解得P0=1-Pn=(1-) n , n1这里的称为服务强度,也称话务强度,它刻划了服务 机构的繁忙程度,所以又称服务机构的利用率。系统的各项运行指标计算如下
11、:平均队长: Ls=nPn= ()平均排队长:Lq=(n1)Pn = (-)=Ls =Ls(1-P0)逗留时间分布函数为:F()=1e()平均逗留时间: Ws=1 ()=Ls 平均等待时间: Wq=Ws1 =Lq 例:6.3.2 系统容量有限制的情形(M/M/1/N/)当系统的容量有限制(为N)时,设平均到达率为、 平均服务率为,排队系统(M/M/1/N/)的生灭过程 可用下面的状态转移图表示:01 n+1 系统处于稳态时的概率方程如下:P0=P1Pn-1+Pn+1=Pn+ Pn (nN)PN=P N-1设=/1, 考虑到 P0+ P1+ + PN=1, 解得P0=(1- ) (1- N+1)
12、Pn=P0 n , nN.N N-1.n n-1系统的各项运行指标计算如下:平均队长:Ls= (1-) (N+1)N+1 (1-N+1)平均排队长:Lq=Ls (1-P0)有效到达率:e=(1-PN)=(1-P0)平均逗留时间: Ws= Ls e平均等待时间: Wq=Ws1 = Lq e例:6.3.3 顾客源为有限的情形(M/M/1/m)当系统的顾客源为有限(为m)时,设各个顾客的平均 到达率都为、服务台的平均服务率为, 排队系统( M/M/1/m)的生灭过程可用下面的状态转移图表示:01 n+1m (m-1) (m-n+1) (m-n) 系统处于稳态时的概率方程如下:mP0=P1(m-n+1)Pn-1+Pn+1= (m-n)Pn+ Pn (nm)Pm=P m-1考虑到 P0+ P1+ + Pm=1, 解得P0= -1Pn= (nm).m m-1.n n-1系统的各项运行指标计算如下:平均队长:Ls=m(1-P0)/平均排队长:Lq=Ls(1-P0)有效到达率:e=(m-Ls)=(1-P0)平均逗留时间: Ws= Ls/ e平均等待时间:Wq=Ws1/ =Lq/ e例: