《管理运筹学（第五版）》-排队论

排队系统顾客服务台服务电话系统电话呼叫电话总机接通呼叫或取消呼叫售票系统购票旅客售票窗口收款、售票设备维修出故障的设备修理工排除设备故障防空系统进入阵地的敌机高射炮瞄准、射击直至敌机被击落或离开9.1基本概念

9.1.1排队过程的一般表示举例：

一般的排队过程为：顾客由顾客源出发，到达服务机构(服务台、服务员)前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。排队过程的一般过程可用下图表示。在现实生活中的排队现象是多种多样的，排队可以是有形的，也可以是无形的。3单服务台单队系统:队列:服务台到达离开4多服务台单队系统到达离开5多服务台多队系统到达离开6多服务台串联系统到达离开9.1基本概念9.1.2排队系统的组成和特征决定排队系统进程的因素有三个基本的组成部分，这就是输入过程、排队规则及服务机构。1)输入过程：顾客来源以及顾客到达排队系统的规律。包括：

顾客源中顾客的数量是有限还是无限；顾客到达的方式是单个到达还是成批到达；相继到达的间隔时间分布是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。2)排队规则：描述顾客排队等待的队列和接受服务的次序,包括：即时制还是等待制(即时制又称损失制)

；等待制下队列的情况(是单列还是多列，顾客能不能中途退出，多列时各列间的顾客能不能相互转移)；等待制下顾客接受服务的次序(先到先服务，后到先服务，随机服务，有优先权的服务)。3)服务机构：描述服务台(员)的机构形式和工作情况。包括：服务台(员)的数目和排列情况；服务台(员)的服务方式；服务时间是确定型的还是随机型的，分布参数是什么，是否独立，是否平稳。9.1基本概念9.1.3排队模型的分类

D.G.Kendall在1953年提出了一个分类方法，按照系统的三个最主要的、影响最大的三个特征要素进行分类，它们是：顾客相继到达的间隔时间分布、服务时间的分布、服务台数。按照这三个特征要素分类的排队系统，用符号(称为Kendall记号)表示为:X/Y/Z其中：X处填写顾客相继到达的间隔时间分布；

Y处填写服务时间的分布；

Z处填写并列的服务台个数。常用的表示相继到达间隔时间和服务时间的各种分布如下：M–负指数分布(具有Markov性)；D–定常分布；Ek–k阶Erlang分布例如M/M/1，表示顾客相继到达的间隔时间为负指数分布、服务时间为负指数分布、单服务台的模型。

后来，在1971年关于排队论符号标准化的会议上决定，将Kendall符号扩充为：X/Y/Z/A/B/C

其中前三项意义不变。A处填写系统容量限制；

B处填写顾客源中的顾客数目；C处填写服务规则(如先到先服务FCFS，后到先服务LCFS)。

约定，如略去后三项，即指X/Y/Z/∞/∞/FCFS的情形。

后面我们只讨论先到先服务FCFS的情形，所以略去第六项。9.1基本概念9.1.4排队系统的求解为了研究排队系统运行的效率、估计服务质量、研究设计改进措施，必须确定一些基本指标。1)队长：把系统中的顾客数称为队长，期望值记作Ls。把系统中排队等待服务的顾客数称为排队长(队列长)，期望值记作Lq。

队长＝排队长＋正被服务的顾客数

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

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

3)瞬态和稳态系统中的顾客数称为系统的状态。考虑在t时刻系统的状态为n的概率，它是随时刻t而变化的，用Pn(t)表示，称为系统的瞬态。

limPn(t)＝Pn

t→∞称其为稳态或称统计平衡状态的解。逗留时间＝等待时间＋服务时间9.2几个主要概率

9.2.1经验分布

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

平均间隔时间=总时间/到达顾客总数平均服务时间=服务时间总和/顾客总数平均到达率=到达顾客总数/总时间平均服务率=顾客总数/服务时间总和9.2几个主要概率分布9.2.2Poisson分布

在概率论中，随机变量的Poisson分布

如果一个随机变量，概率分布与时间t有关，则称这个随机变量为一随机过程，排队系统中顾客到达的个数就是一个随机过程。

设N(t)表示在时间区间[t0,t0+t)内到达的顾客随机数。当N(t)满足下列四个条件时，我们说顾客的到达符合Poisson分布。这四个条件是：(3)普通性在充分短的时间区间Δt内，到达多于1个顾客的概率极小，可以忽略不计，即

∞

∑Pn(Δt)＝o(Δt)

n=2

(1)平稳性在时间区间

内到达的顾客数N(t)，只与区间长度t有关而与时间起点

无关。(2)无后效性

在时间区间内到达的顾客数N(t)，与

以前到达的顾客数独立。(4)有限性

任意有限个区间内到达有限个顾客的概率等于1，即

在上述三个条件下可以推出，在[0,t)内到达n个顾客的概率为：(λt)nPn(t)＝———e-λtn=0,1,2,……n!

N(t)的数学期望和方差分别是：

E[N(t)]＝λtVar[N(t)]＝λt那么，λ＝E[N(t)]/t

，表示单位时间内到达的顾客数的期望值，即平均到达的顾客数，称为平均到达率。9.2几个主要概率分布

9.2.3负指数分布

随机变量T的概率密度若是

λe-λtt≥0fT(t)＝0t

0则称T服从负指数分布，它的分布函数是1-e-λtt≥0FT(t)＝0t

0T的数学期望和方差分别为：E[T]＝1/λ，Var(T)＝1/λ2负指数分布具有下列性质：

(1)无记忆性或马尔柯夫性，即P{T>t+s|T>s}＝P{T>t}(2)当顾客到达符合Poisson分布时，顾客相继到达的间隔时间T必服从负指数分布。

对于Poisson

分布，λ表示单位时间平均到达的顾客数，所以1/λ表示顾客相继到达的平均间隔时间，而这正和E[T]的意义相符。因此，“到达的顾客数是一个以λ为参数的Poisson流”与“顾客相继到达的时间间隔服从以λ为参数的负指数分布”这两个命题是等价的。服务时间符合负指数分布时，设它的概率密度函数和分布函数分别为

fv(t)＝μe-μt；Fv(t)＝1-e-μt(t≥0)

其中μ表示单位时间能够服务完的顾客数，称作平均服务率；而1/μ表示一个顾客的平均服务时间，正是v的期望值。9.3单服务台负指数分布排队系统分析

9.3.1标准M/M/1模型(M/M/1/∞/∞)

排队系统的状态n随时间变化的过程称为生灭过程，设平均到达率为λ,平均服务率为μ,负指数分布排队系统(M/M/1/∞/∞)的生灭过程可用下面的状态转移图表示：

稳态概率方程如下:λP0=μP1λPn-1+μPn+1=λPn+μPn01n-1nn+1...λλλλλλμμμμμμ由第1个等式得：由第2个等式，令n＝2，得：代入解得：用递推方法可以得到：得

令则，否则队列将排至无限远。由

这里的ρ称为服务强度，它是平均到达率与平均服务率之比；它刻画了服务机构的繁忙程度，所以又称服务机构的利用率。上式可表示为：该级数收敛，有：代入递推公式，有：

系统的各项运行指标计算如下：系统中的平均顾客数(即对长期望值)

系统中的等待的平均顾客数(即排队长期望值)

顾客在系统中的逗留时间分布函数：顾客在系统中的平均逗留时间

顾客在系统中的逗留时间X服从参数为的负指数分布，因此X的期望值即平均逗留时间为：顾客在系统中的平均等待时间

顾客在系统中的等待时间的期望值，等于顾客在系统中逗留时间的期望值减去接受服务的时间的期望值。对于(M/M/1/∞/∞)系统总结如下：系统中有k个顾客的概率为：系统中的平均顾客数为：排队的平均长度为：顾客逗留时间分布函数为：顾客在系统中的平均等待时间为：顾客在系统中的平均逗留时间为：Little公式总结如下：适用模型：M/M/1λ=2.1μ=2.5解：首先算出每小时病人平均达到率=2.1人/小时到达的病人数出现次数为病人完成手术的时间(小时)出现次数0100.0--0.2381280.2--0.4252290.4—0.6173160.6—0.894100.8—1.06561.0—1.256以上11.2以上0(Model1:M/M/1)例1：医院手术室根据病人就诊和完成手术时间的记录，任意抽查100个工作小时，没小时来就诊的病人数N的出现次数见表所示。又任意抽查100个完成手术的病例，所用时间M出现的次数见表所示。(1)手术室的空闲率，在病房中的平均病人数，排队等待的平均病人数，病人在病房中的平均逗留时间和平均等待时间。(2)若希望病人的平均逗留时间减少一半，则每小时平均完成手术的人数用该提高多少？

例2汽车按泊松流到达某高速公路收费口，平均每小时90辆。每辆车通过收费口的时间服从均值35秒的负指数分布。

(1)在收费口有多于2辆车排队等待的概率是多少？

(2)因司机们抱怨等待时间太长，管理部门拟采用自动收款装置使平均收费时间缩短到30秒，但条件是原收费口平均等待车辆超过6辆，且新装置的利用率不低于75%时才采用，问新装置能否被采用？适用模型：M/M/1λ=90μ=3600/35=102.869.3单服务台负指数分布排队系统分析

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

当系统的容量有限制(为N)时，设平均到达率为λ、平均服务率为μ，排队系统(M/M/1/N/∞)的生灭过程可用下面的状态转移图表示：01n+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...NN-1...nn-1系统的各项运行指标计算如下：平均队长：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

(Model2:M/M/1/N)例3某加油站只有一个加油泵，而且场地很小，最多只能停放6辆排队等待加油的汽车。设汽车到达间隔和加油时间都服从负指数分布，平均每小时到达30辆汽车，每辆汽车加油平均需要1.5分钟。试问：

(1)来加油的汽车一到达就能立即加油的概率是多少？

(2)等待加油的汽车平均数是多少？

(3)平均有效到达率是多少？

(4)每辆汽车在加油站内停留的平均时间是多少？

(5)在可能到达的汽车中有百分之几不加油就离开？适用模型：M/M/1/withFiniteSystemSizeλ=30μ=40N=709.3单服务台负指数分布排队系统分析

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

当系统的顾客源为有限(为m)时，设各个顾客的平均到达率都为λ、服务台的平均服务率为μ，排队系统(M/M/1/∞/m)的生灭过程可用下面的状态转移图表示：01n+1mλ(m-1)λ(m-n+1)λ(m-n)λλμμμμμ系统处于稳态时的概率方程如下：mλP0=μP1(m-n+1)λPn-1+μPn+1=(m-n)λPn+μPn(n<m)μPm=λPm-1

考虑到P0+P1+…+Pm=1,解得

P0=-1

Pn=(n≤m)...mm-1...nn-1系统的各项运行指标计算如下：平均队长：Ls=m–μ(1-P0)/λ平均排队长：Lq=Ls–(1-P0)有效到达率：λe=λ(m-Ls)=μ(1-P0)平均逗留时间:Ws=Ls/λe平均等待时间:Wq=Ws–1/μ=Lq/λe(Model3:M/M/1withfinitepopulaton)例4某工人负责看管5台机器，每台机器的连续运转时间服从平均值15分钟的负指数分布。机器发生故障后，每次修理时间服从负指数分布，平均为12分钟。求：

(1)工人空闲的概率；

(2)五台机器都出故障的概率；

(3)出故障机器的平均数；

(4)等待修理机器的平均数；

(5)正常运转的机器平均数；

(6)每台机器平均停工时间；

(7)每台机器平均待修时间。M/M/1WithFinitePopulation48M/M/S/∞/∞单位时间顾客平均到达数

，单位平均服务顾客数。1.系统中无顾客的概率2.平均排队的顾客数3.系统中的平均顾客数Ls=Lq+/,4.顾客花在排队上的平均等待时间Wq=

Lq/,495.顾客在系统中的平均逗留时间Ws=Wq+1/,6.系统中顾客必须排队等待的概率7.系统中恰好有n个顾客的概率当n≤c时当n>c时50

对任一个排队模型成立，这里Ls,Lq,Ws,μ的定义如上所述，而应为实际进入系统平均到达率，对于排队长度有限制的模型，我们设因排队长度的限制顾客被拒绝的概率为PN，则实际进入系统平均到达率应为,这时，原来公式中的应改为。(Model4:M/M/s)例5运煤的汽车不断地给煤场运煤，汽车的到达是泊松流，平均每小时到达9辆。煤场设有三个相同的卸货点，卸货时间服从负指数分布，平均每小时可卸货4辆。现设汽车到达后排成一个队列，依次到有空的卸货点卸货。

模型指标M/M/33个M/M/1空闲的概率

0.07480.25(每个子系统)顾客必须等待的概率0.56780.75平均队长

3.95349(整个系统)平均队列长

1.70342.25(每个子系统)平均逗留时间

0.43931平均等待时间

0.18930.75例6某理发店有若干名理发师，并有足够的位置接待人们排列等待理发。顾客到达间隔服从参数为10(人/小时)的负指数分布，每名顾客的理发时间服从平均值20分钟的负指数分布。理发店经理希望确定满足下列两个条件的理发师人数：理发店的利用率不低于60%；一个顾客的平均等待时间少于5分钟。

M/M/S/N/∞

公式非常复杂，不再一一列出，直接用软件求解，M/M/S/NWithafiniteSystemSize(Model5:M/M/s/NWithaFiniteSystemSize)例7某理发店有4名理发员，除理发椅外，尚有16把椅子供等待顾客用。顾客按泊松流到达，平均每小时25人。当所有椅子都坐满时，到来的顾客将不再进入而离去。每名顾客的理发时间为负指数分布，平均时间为11.5分钟。试求：①新到顾客离去的概率；②顾客一到达就能立即理发的概率；③等待理发的顾客平均数；④顾客从进理发店起到理完发的平均时间。若要平均有效到达率不低于20.8人/小时，理发店至少应增加多少把供等待顾客用的椅子？例8在某风景区准备建造旅馆，已知顾客到达为泊松流，每天平均到达6人（假设每人住一间房间）。顾客逗留时间服从平均值2天的负指数分布。试确定旅馆的房间数目使得损失率不超过0.1且每天平均空闲房间数最小。客房数121314151617客满概率0.19860.15490.11720.08570.06040.0409住人数9.617210.141210.593510.971211.275011.5092空闲数2.38282.85883.40654.02884.72505.490862

M/M/S/∞/m

公式非常复杂，不再一一列出，直接用软件求解，M/M/SWithfinitePopulation63

M/M/s/∞/m条件：单位时间顾客平均到达数

单位平均服务顾客数

关心的项目:1.系统中无顾客的概率P02.系统中平均排队的顾客数Lq3.系统中的平均顾客数Ls4.系统中顾客平均的排队等待时间Wq5.系统中顾客的平均逗留时间Ws6.系统中顾客必须排队等待的概率Pw7.系统中恰好有n个顾客的概率Pn(Model6:M/M/S/∞/m)例9设有两名工人负责5台机器的正常运行。每台机器的连续运转时间服从负指数分布，平均损坏率为1次/小时。两名工人能以相同的平均修复率4台/小时修好机器，修理时间也服从负指数分布。使用计算机求出各状态概率，然后求：（1）等待修理的机器平均数；（2）需要修理的机器平均数；（3）平均有效损坏率；（4）每台机器的平均待修时间；（5）每台机器的平均停工时间；（6）损坏的机器不能马上获得修理的概率。M/M/SWithfinitePopulation损坏的机器不能马上获得修理的概率为损坏的机器不能马上获得修理的概率为例10某厂有若干台机器，它们连续运转时间都服从参数λ=0.5（次/小时）的负指数分布。工人修理时间服从同一参数µ=5（台/小时）的负指数分布。今有两个方案：方案I为3个工人各自独立看管机器，每人看管6台机器。方案II为3个工人共同看管20台机器，试比较两个方案的优劣。M/M/1/6/6与M/M/3/20/20比较指标方案Ⅰ方案Ⅱ不能马上修理时间0.5154850.332376等待修理时间0.988992（整个系统）0.338855平均停工时间0.327904（小时）0.237916（小时）平均等待时间0.127904（小时）0.037916（小时）69

M/G/1/∞/∞

单位时间顾客平均到达数

，单位平均服务顾客数，一个顾客的平均服务时间1/

，服务时间的均方差。数量指标公式:1.系统中无顾客的概率P0=1

/2.平均排队的顾客数3.系统中的平均顾客数Ls=Lq+/4.顾客花在排队上的平均等待时间Wq=

Lq/5.在系统中顾客的平均逗留时间Ws=Wq+1/

6.系统中顾客必须排队等待的概率Pw=/7.系统中恰好有n个顾客的概率Pn(MODEL7:M/G/1)例11：设某电话间的顾客按泊松流达到，平均每小时到达6人，通话时间的平均值为8分钟，标准差为4分钟。管理人员想知道平均队长和顾客平均等待时间是多少？适用模型：M/G/1λ=6μ