运筹学6排队论.ppt

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) 一般的排队过程为：顾客由顾客源出发，到达服务一般的排队过程为：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接机构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。

排队过程的一般过程可用下图表示完服务后就离开排队过程的一般过程可用下图表示我们所说的排队系统就是指图中虚线所包括的部分我们所说的排队系统就是指图中虚线所包括的部分 在现实生活中的排队现象是多种多样的，对上面所在现实生活中的排队现象是多种多样的，对上面所说的说的““顾客顾客””和和““服务员服务员””要作广泛的理解它们可以要作广泛的理解它们可以是人，也可以是某种物质或设备排队可以是有形的，是人，也可以是某种物质或设备排队可以是有形的，也可以是无形的也可以是无形的6.1 基本概念 6.1.1 排队过程的一般表示6.1 基本概念 6.1.2 排队系统的组成和特征 尽管排队系统是多种多样的，但从决定排队系统进尽管排队系统是多种多样的，但从决定排队系统进程的因素来看，它有三个基本的组成部分，这就是输入程的因素来看，它有三个基本的组成部分，这就是输入过程、排队规则及服务机构过程、排队规则及服务机构1)1)输入过程：描述顾客来源以及顾客到达排队系统的规输入过程：描述顾客来源以及顾客到达排队系统的规律包括：律包括： 顾客源中顾客的数量是有限还是无限；顾客源中顾客的数量是有限还是无限； 顾客到达的方式是单个到达还是成批到达；顾客到达的方式是单个到达还是成批到达； 顾客相继到达的间隔时间分布是确定型的还是随机顾客相继到达的间隔时间分布是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。

型的，分布参数是什么，是否独立，是否平稳 2)排队规则：排队规则：描述顾客排队等待的队列和接受服务的次描述顾客排队等待的队列和接受服务的次序包括：序包括： 即时制还是等待制；即时制还是等待制； 等待制下队列的情况（是单列还是多列，顾客能不等待制下队列的情况（是单列还是多列，顾客能不能中途退出，多列时各列间的顾客能不能相互转移）；能中途退出，多列时各列间的顾客能不能相互转移）； 等待制下顾客接受服务的次序（先到先服务，后到等待制下顾客接受服务的次序（先到先服务，后到先服务，随机服务，有优先权的服务）先服务，随机服务，有优先权的服务）3)3)服务机构：描述服务台服务机构：描述服务台( (员员) )的机构形式和工作情况的机构形式和工作情况包括：包括： 服务台（员）的数目和排列情况；服务台（员）的数目和排列情况； 服务台（员）的服务方式；服务台（员）的服务方式； 服务时间是确定型的还是随机型的，分布参数是什服务时间是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳么，是否独立，是否平稳6.1 基本概念 6.1.3 排队模型的分类 在在19531953年提出了一个分类方法，按照系统的三个最年提出了一个分类方法，按照系统的三个最主要的、影响最大的三个特征要素进行分类，它们是：主要的、影响最大的三个特征要素进行分类，它们是：顾客相继到达的间隔时间分布、服务时间的分布、并列顾客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。

按照这三个特征要素分类的排队系统，的服务台个数按照这三个特征要素分类的排队系统，用符号（称为用符号（称为KendallKendall记号）表示为记号）表示为 X/Y/ZX/Y/Z其中其中X X处填写顾客相继到达的间隔时间分布，处填写顾客相继到达的间隔时间分布，Y Y处填写服处填写服务时间的分布，务时间的分布，Z Z处填写并列的服务台个数处填写并列的服务台个数 例如例如M/M/1M/M/1，，表示顾客相继到达的间隔时间为负指表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、单服务台的模型数分布、服务时间为负指数分布、单服务台的模型 后来，在后来，在19711971年关于排队论符号标准化的会议上年关于排队论符号标准化的会议上决定，将决定，将KendallKendall符号扩充为：符号扩充为： X/Y/Z/A/B/CX/Y/Z/A/B/C 其中前三项意义不变其中前三项意义不变 A A处填写系统容量限制处填写系统容量限制; ; B B处填写顾客源中的顾客数目处填写顾客源中的顾客数目; ; C C处填写服务规则（如先到先服务处填写服务规则（如先到先服务FCFSFCFS，，后到先服后到先服务务LCFSLCFS）。

约定，如略去后三项，即指约定，如略去后三项，即指X/Y/Z/∞/∞/FCFSX/Y/Z/∞/∞/FCFS的的情形 后面我们只讨论先到先服务后面我们只讨论先到先服务FCFSFCFS的情形，所以略的情形，所以略去第六项去第六项6.1 基本概念6.1.4 排队系统的求解 对于一个排队系统，运行状况的好坏既涉及到顾客对于一个排队系统，运行状况的好坏既涉及到顾客的利益，又涉及到服务机构的利益，还有社会效果好的利益，又涉及到服务机构的利益，还有社会效果好坏的问题为了研究排队系统运行的效率、估计服务坏的问题为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标，质量、研究设计改进措施，必须确定一些基本指标，用以判断系统运行状况的优劣下面介绍几种常用的用以判断系统运行状况的优劣下面介绍几种常用的指标 1)1)队长：把系统中的顾客数称为队长：把系统中的顾客数称为队长队长，它的期望值记，它的期望值记作作LsLs而把系统中排队等待服务的顾客数称为而把系统中排队等待服务的顾客数称为排队长排队长（队列长）（队列长），它的期望值记作，它的期望值记作LqLq。

显然有显然有 队长＝排队长＋正被服务的顾客数队长＝排队长＋正被服务的顾客数 2)2)逗留时间：一个顾客从到达排队系统到服务完逗留时间：一个顾客从到达排队系统到服务完毕离去的总停留时间称为毕离去的总停留时间称为逗留时间逗留时间，它的期望值记作，它的期望值记作WsWs 一个一个顾客在系统中排队等待的时间称为顾客在系统中排队等待的时间称为等待时等待时间间，它的期望值记作，它的期望值记作WqWq显然有显然有 逗留时间＝等待时间＋服务时间逗留时间＝等待时间＋服务时间 3) 3)瞬态和稳态瞬态和稳态 把系统中的顾客数称为系统的把系统中的顾客数称为系统的状态状态考虑在考虑在t t时刻时刻系统的状态为系统的状态为n n的概率，它是随时刻的概率，它是随时刻t t而变化的，用而变化的，用P Pn n(t)(t)表示，称为系统的表示，称为系统的瞬态瞬态求瞬态解是很不容易的，求瞬态解是很不容易的，一般即使求出也很难利用，因此我们常用它的极限一般即使求出也很难利用，因此我们常用它的极限 lim Plim Pn n(t)(t)＝＝P Pn n t→∞ t→∞称为称为稳态稳态或称统计平衡状态的解或称统计平衡状态的解。

6.2 几个主要概率分布 6.2.1 经验分布 在处理实际排队系统时，需要把有关的原始资料在处理实际排队系统时，需要把有关的原始资料进行统计，确定顾客到达间隔和服务时间的经验分布，进行统计，确定顾客到达间隔和服务时间的经验分布，然后按照统计学的方法确定符合哪种理论分布然后按照统计学的方法确定符合哪种理论分布 经验分布的主要指标如下：经验分布的主要指标如下： 总时间总时间 平均间隔时间平均间隔时间= 到达顾客总数到达顾客总数 服务时间总和服务时间总和 平均服务时间平均服务时间= 顾客总数顾客总数 到达顾客总数到达顾客总数 平均到达率平均到达率= 总时间总时间 顾客总数顾客总数 平均服务率平均服务率= 服务时间总和服务时间总和6.2 几个主要概率分布 6.2.2 普阿松分布 设设N(t)N(t)表示在时间区间表示在时间区间[ [t t0,t,t0+t)+t)内到达的顾客数，内到达的顾客数，是随机变量。

当是随机变量当N(t)N(t)满足下列三个条件时，我们说顾客满足下列三个条件时，我们说顾客的到达符合普阿松分布这三个条件是：的到达符合普阿松分布这三个条件是： (1) (1)平稳性平稳性 在时间区间在时间区间[ [t t0,t,t0+t)+t)内到达的顾客数内到达的顾客数N(t)N(t)，，只与区间长度只与区间长度t t有关而与时间起点有关而与时间起点t t0无关 (2) (2)无后效性无后效性 在时间区间在时间区间[ [t t0,t,t0+t)+t)内到达的顾客内到达的顾客数数N(t)N(t)，，与与t t0以前到达的顾客数独立以前到达的顾客数独立 (3) (3)普通性普通性 在充分短的时间区间在充分短的时间区间ΔtΔt内，到达两个内，到达两个或两个以上顾客的概率极小，可以忽略不计，即或两个以上顾客的概率极小，可以忽略不计，即 ∞ ∑ ∑P Pn(Δt)(Δt)＝＝o(Δt)o(Δt) n=2  在上述三个条件下可以推出在上述三个条件下可以推出 ( (λt)λt)n P Pn(t)(t)＝＝——— e——— e-λt n=0,1,2,…… n=0,1,2,…… n! n!其中其中λλ表示单位时间平均到达的顾客数，即为到达表示单位时间平均到达的顾客数，即为到达率。

率 不难算出，不难算出，N(t)N(t)的数学期望和方差分别是：的数学期望和方差分别是： E[N(t)]E[N(t)]＝＝λt λt Var[N(t)] Var[N(t)]＝＝λtλt6.2 几个主要概率分布 6.2.3 负指数分布 随机变量随机变量T T的概率密度若是的概率密度若是 λeλe-λt t≥0 t≥0 f fT(t)(t)＝＝ 0 t 0 t 0 0则称则称T T服从负指数分布，它的分布函数是服从负指数分布，它的分布函数是 1- 1-e e-λt t≥0 t≥0 F FT(t)(t)＝＝ 0 t 0 t 0 0 T T的数学期望和方差分别为：的数学期望和方差分别为： E[T]E[T]＝＝1/λ1/λ，， Var(T) Var(T)＝＝1/λ1/λ2 负指数分布具有下列性质：负指数分布具有下列性质： (1) (1)无记忆性或马尔柯夫性，即无记忆性或马尔柯夫性，即 P{T>t+s / T>s}P{T>t+s / T>s}＝＝P{T>t}P{T>t} (2) (2)当顾客到达符合普阿松分布时，顾客相继到达的当顾客到达符合普阿松分布时，顾客相继到达的间隔时间间隔时间T T必服从负指数分布。

必服从负指数分布  对于普阿松分布，对于普阿松分布，λλ表示单位时间平均到达表示单位时间平均到达的顾客数，所以的顾客数，所以1/1/λλ表示顾客相继到达的平均间表示顾客相继到达的平均间隔时间，而这正和隔时间，而这正和E[T]E[T]的意义相符的意义相符 服务时间符合负指数分布时，设它的概率密服务时间符合负指数分布时，设它的概率密度函数和分布函数分别为度函数和分布函数分别为 f fv(t)(t)＝＝μeμe-μt；； F Fv(t)(t)＝＝1-e1-e-μt (t≥0) (t≥0)其中其中μμ表示单位时间能够服务完的顾客数，为服表示单位时间能够服务完的顾客数，为服务率；而务率；而1/1/μμ表示一个顾客的平均服务时间，正表示一个顾客的平均服务时间，正是是v v的期望值的期望值6.3 单服务台负指数分布排队系统分析 6.3.1 标准M/M/1模型(M/M/1/∞/∞) 排队系统的状态排队系统的状态n随时间变化的过程称为生灭过程，随时间变化的过程称为生灭过程，设平均到达率为设平均到达率为λ,平均服务率为平均服务率为μ,负指数分布排队系统负指数分布排队系统（（M/M/1/∞/∞）的生灭过程可用下面的状态转移图表示：）的生灭过程可用下面的状态转移图表示：01 n-1n n+1... λ λ λ λ λ λ μ μ μ μ μ μ 稳态概率方程如下：稳态概率方程如下： -λP0=μP1 λPn-1+μPn+1=λPn+μPn设设ρ=λ/μ<1，考虑到，考虑到 Pn=1，解得，解得 P0=1-ρ Pn=(1-ρ) ρn , n≥1 这里的这里的ρ称为服务强度，也称话务强度，它刻划了服务称为服务强度，也称话务强度，它刻划了服务机构的繁忙程度，所以又称服务机构的利用率。

机构的繁忙程度，所以又称服务机构的利用率 系统的各项运行指标计算如下：系统的各项运行指标计算如下：平均队长：平均队长： Ls=ΣnPn=λ (μ–λ)平均排队长：平均排队长： Lq=Σ(n–1)Pn =ρλ (μ-λ) =Ls–ρ =Ls–(1-P0)逗留时间分布函数为逗留时间分布函数为: F(ω)=1–e－－(μ－－λ)ω平均逗留时间平均逗留时间: Ws=1 (μ–λ)=Ls λ平均等待时间平均等待时间: Wq=Ws–1 μ=Lq λ 例：例：6.3 单服务台负指数分布排队系统分析 6.3.2 系统容量有限制的情形(M/M/1/N/∞) 当系统的容量有限制当系统的容量有限制(为为N)时，设平均到达率为时，设平均到达率为λ、、平均服务率为平均服务率为μ，排队系统（，排队系统（M/M/1/N/∞）的生灭过程）的生灭过程可用下面的状态转移图表示：可用下面的状态转移图表示：01 n+1 λ λ λ λ λ λ λ λ μ μ μ μ μ μ μ μ 系统处于稳态时的概率方程如下：系统处于稳态时的概率方程如下： λP0=μP1 λPn-1+μPn+1=λPn+ μPn （（n