《我的运筹课件排队论》由会员分享，可在线阅读，更多相关《我的运筹课件排队论（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例:
