我的运筹课件排队论

我的运筹课件排队论第1页，共21页，2023年，2月20日，星期五

一般的排队过程为：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。排队过程的一般过程可用下图表示。我们所说的排队系统就是指图中虚线所包括的部分。

在现实生活中的排队现象是多种多样的，对上面所说的“顾客”和“服务员”要作广泛的理解。它们可以是人，也可以是某种物质或设备。排队可以是有形的，也可以是无形的。6.1基本概念

6.1.1排队过程的一般表示第2页，共21页，2023年，2月20日，星期五

6.1.2排队系统的组成和特征

尽管排队系统是多种多样的，但从决定排队系统进程的因素来看，它有三个基本的组成部分，这就是输入过程、排队规则及服务机构。1)输入过程：描述顾客来源以及顾客到达排队系统的规律。包括：顾客源中顾客的数量是有限还是无限；顾客到达的方式是单个到达还是成批到达；顾客相继到达的间隔时间分布是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。第3页，共21页，2023年，2月20日，星期五

2)排队规则：描述顾客排队等待的队列和接受服务的次序。包括：即时制还是等待制；等待制下队列的情况（是单列还是多列，顾客能不能中途退出，多列时各列间的顾客能不能相互转移）；等待制下顾客接受服务的次序（先到先服务，后到先服务，随机服务，有优先权的服务）。3)服务机构：描述服务台(员)的机构形式和工作情况。包括：服务台（员）的数目和排列情况；服务台（员）的服务方式；服务时间是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。第4页，共21页，2023年，2月20日，星期五

6.1.3排队模型的分类

D.G.Kendall在1953年提出了一个分类方法，按照系统的三个最主要的、影响最大的三个特征要素进行分类，它们是：顾客相继到达的间隔时间分布、服务时间的分布、并列的服务台个数。按照这三个特征要素分类的排队系统，用符号（称为Kendall记号）表示为X/Y/Z其中X处填写顾客相继到达的间隔时间分布，Y处填写服务时间的分布，Z处填写并列的服务台个数。例如M/M/1，表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、单服务台的模型。第5页，共21页，2023年，2月20日，星期五

后来，在1971年关于排队论符号标准化的会议上决定，将Kendall符号扩充为：X/Y/Z/A/B/C其中前三项意义不变。A处填写系统容量限制;

B处填写顾客源中的顾客数目;C处填写服务规则（如先到先服务FCFS，后到先服务LCFS）。约定，如略去后三项，即指X/Y/Z/∞/∞/FCFS的情形。后面我们只讨论先到先服务FCFS的情形，所以略去第六项。第6页，共21页，2023年，2月20日，星期五

6.1.4排队系统的求解

对于一个排队系统，运行状况的好坏既涉及到顾客的利益，又涉及到服务机构的利益，还有社会效果好坏的问题。为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标，用以判断系统运行状况的优劣。下面介绍几种常用的指标。1)队长：把系统中的顾客数称为队长，它的期望值记作Ls。而把系统中排队等待服务的顾客数称为排队长（队列长），它的期望值记作Lq。显然有

队长＝排队长＋正被服务的顾客数。第7页，共21页，2023年，2月20日，星期五

2)逗留时间：一个顾客从到达排队系统到服务完毕离去的总停留时间称为逗留时间，它的期望值记作Ws。

一个顾客在系统中排队等待的时间称为等待时间，它的期望值记作Wq。显然有

逗留时间＝等待时间＋服务时间。3)瞬态和稳态把系统中的顾客数称为系统的状态。考虑在t时刻系统的状态为n的概率，它是随时刻t而变化的，用Pn(t)表示，称为系统的瞬态。求瞬态解是很不容易的，一般即使求出也很难利用，因此我们常用它的极限limPn(t)＝Pnt→∞称为稳态或称统计平衡状态的解。第8页，共21页，2023年，2月20日，星期五6.2几个主要概率分布

6.2.1经验分布

在处理实际排队系统时，需要把有关的原始资料进行统计，确定顾客到达间隔和服务时间的经验分布，然后按照统计学的方法确定符合哪种理论分布。经验分布的主要指标如下：总时间平均间隔时间=

到达顾客总数服务时间总和平均服务时间=

顾客总数

到达顾客总数平均到达率=

总时间顾客总数平均服务率=

服务时间总和第9页，共21页，2023年，2月20日，星期五

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

第10页，共21页，2023年，2月20日，星期五

在上述三个条件下可以推出(λt)nPn(t)＝———e-λtn=0,1,2,……n!其中λ表示单位时间平均到达的顾客数，即为到达率。不难算出，N(t)的数学期望和方差分别是：E[N(t)]＝λtVar[N(t)]＝λt第11页，共21页，2023年，2月20日，星期五

6.2.3负指数分布

随机变量T的概率密度若是λe-λtt≥0fT(t)＝0t0则称T服从负指数分布，它的分布函数是1-e-λtt≥0FT(t)＝0t0T的数学期望和方差分别为：

E[T]＝1/λ，Var(T)＝1/λ2负指数分布具有下列性质：(1)无记忆性或马尔柯夫性，即P{T>t+s/T>s}＝P{T>t}(2)当顾客到达符合普阿松分布时，顾客相继到达的间隔时间T必服从负指数分布。第12页，共21页，2023年，2月20日，星期五

对于普阿松分布，λ表示单位时间平均到达的顾客数，所以1/λ表示顾客相继到达的平均间隔时间，而这正和E[T]的意义相符。服务时间符合负指数分布时，设它的概率密度函数和分布函数分别为fv(t)＝μe-μt；Fv(t)＝1-e-μt(t≥0)其中μ表示单位时间能够服务完的顾客数，为服务率；而1/μ表示一个顾客的平均服务时间，正是v的期望值。第13页，共21页，2023年，2月20日，星期五系统的运行指标：（1）、系统中顾客数的期望值Ls（2）、系统中排队等待顾客数的期望值Lq（3）、系统中顾客平均的排队等待时间Wq（4）、系统中顾客的平均逗留时间Ws（5）、有效到达率e

第14页，共21页，2023年，2月20日，星期五（6）、系统中Ls，Lq，Wq，Ws，e

之间的关系

Ls=npn，Lq=(n-c)pn，

Ws=Ls/e，Wq=Lq/e，

Ws=Wq+1/，

e=

npn=

npn

，

Ls=Lq+e/。

第15页，共21页，2023年，2月20日，星期五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这里的ρ称为服务强度，也称话务强度，它刻划了服务机构的繁忙程度，所以又称服务机构的利用率。第16页，共21页，2023年，2月20日，星期五

系统的各项运行指标计算如下：平均队长：

Ls=ΣnPn=λ(μ–λ)平均排队长：

Lq=Σ(n–1)Pn=ρλ(μ-λ)=Ls–ρ=Ls–(1-P0)逗留时间分布函数为:F(ω)=1–e－(μ－λ)ω平均逗留时间:Ws=1(μ–λ)=Lsλ平均等待时间:Wq=Ws–1μ=Lqλ

例：第17页，共21页，2023年，2月20日，星期五

6.3.2系统容量有限制的情形(M/M/1/N/∞)

当系统的容量有限制(为N)时，设平均到达率为λ、平均服务率为μ，排队系统（M/M/1/N/∞）的生灭过程可用下面的状态转移图表示：01

n+1

λλλλλλλλ

μμμμμμμμ

系统处于稳态时的概率方程如下：

λP0=μP1λPn-1+μPn+1=λPn+μPn

（n<N)μPN=λPN-1

设ρ=λ/μ≠1，考虑到P0+P1+…+PN=1,解得

P0=(1-ρ)(1-ρN+1)Pn=P0ρn,n≤N...N

N-1...n

n-1第18页，共21页，2023年，2月20日，星期五

系统的各项运行指标计算如下：平均队长：

Ls=ρ(1-ρ)–(N+1)ρN+1(1-ρN+1)平均排队长：

Lq=Ls–(1-P0)有效到达率：

λe=λ(1-PN)=μ(1-P0)平均逗留时间:Ws=Lsλe平均等待时间:Wq=Ws–1μ=Lqλe

例:第19页，共21页，2023年，2月20日，星期五

6.3.3顾客源为有限的情形(M/M/1/∞/m)

当系统的顾客源为有限(为m)时，设各个顾客的平均到达率都为λ、服务台的平均服务率为μ，排队系统（M/M/1/∞/m）的生灭过程可用下面的状态转移图表示：01

n+1

mλ(m-1)λ(m-n+1)λ(m-n)λλ