运筹学排队论新

运筹学排队论新第十二章排队论到达间隔的分布和服务时间的分布本章内容基本概念单服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析一般服务时间M/G/1模型第2页,共128页，2024年2月25日，星期天

排队论(QueuingTheory)，又称随机服务系统理论(RandomServiceSystemTheory)。1909年由丹麦工程师爱尔朗(A.K．Erlang)在研究电话系统时创立的。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。特别是自二十世纪60年代以来，由于计算机的飞速发展，使排队论的应用有了更广阔的前景。第3页,共128页，2024年2月25日，星期天WheretheTimeGoes?美国人一生中平均要花费--6年饮食5年排队等待4年做家务2年回电话不成功1年寻找放置不当的物品8个月打开邮寄广告6个月停在红灯前第4页,共128页，2024年2月25日，星期天商业服务系统系统类型 顾客 服务台理发店 人 理发师银行出纳服务 人 出纳ATM机服务 人 ATM机商店收银台 人 收银员管道服务 阻塞的管道 管道工电影院售票窗口 人 售票员机场检票处 人 航空公司代理人经纪人服务 人 股票经纪人第5页,共128页，2024年2月25日，星期天运输服务系统系统类型 顾客 服务台公路收费站 汽车 收费员卡车装货地 卡车 装货工人港口卸货区 轮船 卸货工人等待起飞的飞机 飞机 跑道航班服务 人 飞机出租车服务 人 出租车电梯服务 人 电梯消防部门 火灾 消防车停车场 汽车 停车空间急救车服务 人 急救车第6页,共128页，2024年2月25日，星期天

面对拥挤现象，如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是排队论所要研究解决的问题之一。第7页,共128页，2024年2月25日，星期天第一节基本概念第8页,共128页，2024年2月25日，星期天（一）排队系统的特征及组成

排队系统的共同特征:

①

有要求得到某种服务的人或物。排队论里把要求服务的对象统称为“顾客”②有提供服务的人或机构。把提供服务的人或机构称为“服务台”或“服务员”③顾客的到达、服务的时间至少有一个是随机的，服从某种分布。第9页,共128页，2024年2月25日，星期天一般的排队系统，都可由图12-1加以描述。顾客源排队结构服务机构排队规则顾客到来服务规则离去图12-1排队系统第10页,共128页，2024年2月25日，星期天

排队系统都有输入过程、排队规则和服务台等3个组成部分：1、输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流．一般可以从3个方面来描述输入过程。排队系统的组成第11页,共128页，2024年2月25日，星期天

(1)

顾客总体数组成(又称顾客源)是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。(2)顾客到达方式。描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。第12页,共128页，2024年2月25日，星期天(3)顾客流的概率分布，或称顾客相继到达时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。

顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。第13页,共128页，2024年2月25日，星期天2、排队规则这是指服务台从队列中选取顾客进行服务的顺序。损失制混合制队长有限等待时间有限逗留时间有限排队规则等待制先到先服务后到先服务随机服务优先权服务第14页,共128页，2024年2月25日，星期天3．服务台情况。服务台可以从3方面来描述：

(1)服务台数量及构成形式图12-2单队列-单服务台排队系统第15页,共128页，2024年2月25日，星期天图12-3单队列——S个服务台并联的排队系统图12-4S个队列——S个服务台的并联排队系统第16页,共128页，2024年2月25日，星期天图12-5单队——多个服务台的串联排队系统图12-6多队——多服务台混联、网络系统第17页,共128页，2024年2月25日，星期天 (2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。 (3)服务时间的分布。在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。第18页,共128页，2024年2月25日，星期天

为了区别各种排队系统，根据输入过程、排队规则和服务机制的不同，对排队模型进行分类。D．G．Kendall在1953年提出了模型分类方法，1971年在排队论符号标准化会议上，将Kendall符号扩充为如下固定格式：

X/Y/Z/A/B/C各符号的意义为：（二）排队模型的分类第19页,共128页，2024年2月25日，星期天X—表示顾客相继到达间隔时间分布，常用下列符号：X/Y/Z/A/B/CM—表示到达过程为泊松过程或负指数分布；D—表示定长输入；Ek—表示k阶爱尔朗分布；GI——表示一般相互独立的时间间隔分布；G——表示一般服务时间的分布。第20页,共128页，2024年2月25日，星期天Y—表示服务时间分布，常用下列符号：X/Y/Z/A/B/CM—表示服务过程为泊松过程或负指数分布；D—表示定长分布；Ek—表示k阶爱尔朗分布；G—表示一般相互独立的随机分布。第21页,共128页，2024年2月25日，星期天Z—表示服务台(员)个数： “1”则表示单个服务台，“s”(s＞1)表示多个服务台。X/Y/Z/A/B/CA—表示系统中顾客容量限额，或称等待空间容量： ∞时为等待制系统，此时∞一般省略不写；若为有限整数时，为混合制系统。第22页,共128页，2024年2月25日，星期天B—表示顾客源限额。

分有限与无限两种，∞表示顾客源无限，此时一般∞也可省略不写。X/Y/Z/A/B/CC—表示服务规则，常用下列符号：

FCFS：表示先到先服务；

LCFS：表示后到先服务；

PR：表示优先权服务。第23页,共128页，2024年2月25日，星期天例如：某排队问题为

M／M／S／∞／∞／FCFS

则表示顾客到达间隔时间为负指数分布(泊松流)； 服务时间为负指数分布； 有s(s＞1)个服务台； 系统等待空间容量无限(等待制)； 顾客源无限，采用先到先服务规则。 可简记为：

M/M/s

第24页,共128页，2024年2月25日，星期天

某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统。第25页,共128页，2024年2月25日，星期天（三）排队系统的主要数量指标1.队长和排队长

队长是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和)。

排队长是指系统中正在排队等待服务的顾客数。第26页,共128页，2024年2月25日，星期天2．等待时间和逗留时间

从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，是随机变量。 从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量。第27页,共128页，2024年2月25日，星期天3．忙期和闲期

忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个随机变量，它关系到服务员的服务强度。

与忙期相对的是闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。第28页,共128页，2024年2月25日，星期天

除了上述几个基本数量指标外，还会用到其他一些重要的指标： 损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的顾客损失率及服务强度等，也都是十分重要的数量指标。第29页,共128页，2024年2月25日，星期天

4.一些数量指标的常用记号

(1)主要数量指标

N(t)：时刻t系统中的顾客数(又称为系统的状态)，即队长；

Nq(t)：时刻t系统中排队的顾客数，即排队长；

T(t)：时刻t到达系统的顾客在系统中的逗留时间；

Tq(t)：时刻t到达系统的顾客在系统中的等待时间。第30页,共128页，2024年2月25日，星期天

上面数量指标一般都是和系统运行的时间有关的随机变量，求它们的瞬时分布一般很困难。注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。

在平衡状态下，这些量与系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。第31页,共128页，2024年2月25日，星期天L或Ls—平均队长 稳态系统任一时刻的顾客数的期望值；Lq—平均等待队长或队列长 稳态系统任一时刻等待服务的顾客数期望值；W或Ws—

平均逗留时间进入稳态系统的顾客逗留时间期望值；Wq—平均等待时间 进入稳态系统的顾客等待时间期望值。第32页,共128页，2024年2月25日，星期天Pn—系统的状态Pn=P{N=n}：稳态系统任一时刻状态为n的概率。当n=0时，Pn即P0为稳态系统所有服务台全部空闲的概率。第33页,共128页，2024年2月25日，星期天(2)其他常用数量指标s——系统中并联服务台的数目

——平均到达率（单位时间内到达的平均顾客数）1/——平均到达间隔

——平均服务率（单位时间内可以服务完的平均顾客数）1/

——平均服务时间第34页,共128页，2024年2月25日，星期天

对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已满，则自行消失。这就是说，到达的顾客不一定全部进入系统，为此引入：

e

——有效平均到达率，即每单位时间实际进入系统的平均顾客数（期望值），不同于。

对于等待制的排队系统，有：

e

＝

第35页,共128页，2024年2月25日，星期天第二节到达间隔的分布和服务时间的分布第36页,共128页，2024年2月25日，星期天

一、Poisson流（Poisson过程）定义满足以下三个条件的输入流称为Poisson流1、无后效性：不相交的时间区间内到达的顾客数互相独立。2、平稳性：在时间区间[t,t+

t)内到达1个顾客的概率只与

t有关。即

表示单位时间内有一个顾客到达的概率。3、普通性：设在[t,t+

t）内到达多于一个顾客的概率极小，即第37页,共128页，2024年2月25日，星期天Poisson流与Poisson分布定理1

对于一个参数为

的Poisson流，在[0，t]内到达n个顾客的概率为

即服从以

为参数的Poisson分布。

定理1说明如果顾客的到达为Poisson流的话，则到达顾客数的分布恰好为Poisson分布。第38页,共128页，2024年2月25日，星期天

二、负指数分布

在实际的排队系统中服务时间的概率分布可以是各种形式，但在排队论中，最容易进行数学处理、最常用的一种重要分布是负指数分布。

设随机变量T服从以

为参数的负指数分布，它的分布函数为：第39页,共128页，2024年2月25日，星期天负指数分布的性质：

性质1

由条件概率公式容易证明

性质2

当单位时间内的顾客到达数服从以为平均数的泊松分布时，则顾客相继到达的间隔时间T服从负指数分布。

这性质称为无记忆性。若T表示排队系统中顾客到达的时间间隔，那么这个性质说明一个顾客到来所需要的时间与过去一个顾客到来所需要的时间s无关，所以说在这种情形下的顾客到达是纯随机的。

第40页,共128页，2024年2月25日，星期天由性质2可知：

相继到达的间隔时间是独立且为相同参数的负指数分布，与输入过程为泊松流（参数为

）是等价的。

根据负指数分布与泊松流的关系可以推导出，当服务机构对顾客的服务时间服从参数为

的负指数分布，如果服务机构处于忙期，则该服务机构的输出，即服务完毕离开服务机构的顾客数将是服从泊松分布的泊松流。其中

为每个顾客的平均服务时间，也是顾客相继离开的间隔。

第41页,共128页，2024年2月25日，星期天三、k阶爱尔朗分布定理

设v1，v2，…，vk是k个互相独立的随机变量，服从相同参数k

的负指数分布，那么

S=v1+v2+…+vk服从k阶Erlang分布，S的密度函数为第42页,共128页，2024年2月25日，星期天K=1时爱尔朗分布化归为负指数分布，当K→∞时，得到长度为1/

的定长服务。m=1k=1k=2k=4k=8第43页,共128页，2024年2月25日，星期天第三节单服务台负指数分布排队系统的分析第44页,共128页，2024年2月25日，星期天标准排队模型[M/M/1]:[

/

/FCFS]顾客到达的时间间隔是负指数分布，即输入流是参数为

的Poisson流服从参数为μ的负指数分布一个服务台排队系统的容量无限顾客源的容量无限实行先到先服务的一个服务系统第45页,共128页，2024年2月25日，星期天一、系统稳态概率pn的计算

假设在t+

t时刻系统中顾客数为n的概率Pn(t+

t)Pn(t)Pn-1(t)Pn+1(t)Pn(t)Snt+

t时刻SnSnSn+1Sn-1t时刻无到达，无离开无到达，离开一个到达一个，无离开到达一个，离开一个第46页,共128页，2024年2月25日，星期天由于这四种方式互不相容，故由概率的加法定理得：该差分方程组为瞬态解，需求稳态解。第47页,共128页，2024年2月25日，星期天[M/M/1]:[

/

/FCFS]稳态时状态转移图λ012n-1nn+1稳态情况下，系统状态已不随时间发生变化：第48页,共128页，2024年2月25日，星期天稳态情况下，系统状态已不随时间发生变化：第49页,共128页，2024年2月25日，星期天得到

令称

为服务强度，则得第50页,共128页，2024年2月25日，星期天系统的过渡状态与稳定状态过渡稳定第51页,共128页，2024年2月25日，星期天二、系统的数量指标1、服务台空闲的概率和忙的概率：空闲的概率：P0=1-

忙的概率：1-P0=

2、系统中平均顾客数（队长期望值Ls）：第52页,共128页，2024年2月25日，星期天3、系统中等待的平均顾客数（队长期望值Lq）：4、系统中顾客逗留时间的期望值：第53页,共128页，2024年2月25日，星期天5、队列中顾客逗留时间的期望值：现将以上公式归纳如下：它们相互关系如下：第54页,共128页，2024年2月25日，星期天Little公式

下列公式对任何服务系统均成立第55页,共128页，2024年2月25日，星期天例1

高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求1、收费处空闲的概率；2、收费处忙的概率；3、系统中分别有1，2，3辆车的概率。第56页,共128页，2024年2月25日，星期天解：根据题意,

=100辆/小时,1/

=15（秒/辆）=1/240（小时/辆）,即

＝240（辆/小时）。 因此，

=

/

=100/240=5/12。 系统空闲的概率为：

P0=1-

=1-(5/12)=7/12=0.583

系统忙的概率为：

1-P0=1-(1-

)=

=5/12=0.417第57页,共128页，2024年2月25日，星期天系统中有1辆车的概率为：

P1=

(1-

)=0.417×0.583=0.243系统中有2辆车的概率为：

P2=

2(1-

)=0.4172×0.583=0.101系统中有3辆车的概率为：

P3=

3(1-

)=0.4173×0.583=0.0421第58页,共128页，2024年2月25日，星期天例2

高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为200辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求Ls、Lq、Ws和Wq。第59页,共128页，2024年2月25日，星期天解：根据题意，

=200辆/小时，

=240辆/小时，

=

/

=5/6。第60页,共128页，2024年2月25日，星期天有限队列模型[M/M/1]:[N/

/FCFS]

如果系统的最大容量为N时，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。第61页,共128页，2024年2月25日，星期天系统的状态概率平衡方程对于状态0：

P1=

P0

… …对于状态k：

Pk-1+

Pk+1=(

+

)Pk0<k<N… …对于状态N：

PN-1=

PNλ012n-1n第62页,共128页，2024年2月25日，星期天系统的状态概率由得到第63页,共128页，2024年2月25日，星期天系统的运行指标第64页,共128页，2024年2月25日，星期天有效到达率第65页,共128页，2024年2月25日，星期天Little公式第66页,共128页，2024年2月25日，星期天例3

一个单人理发店，除理发椅外，还有4把椅子可供顾客等候。顾客到达发现没有座位空闲，就不再等待而离去。顾客到达的平均速率为4人/小时，理发的平均时间为10分钟/人。顾客到达服从Poisson流，理发时间服从负指数分布。求：1、顾客到达不用等待就可理发的概率；2、理发店里的平均顾客数以及等待理发的平均顾客数；3、顾客来店理发一次平均花费的时间及平均等待的时间；4、顾客到达后因客满而离去的概率；5、增加一张椅子可以减少的顾客损失率。第67页,共128页，2024年2月25日，星期天解：这是一个[M/M/1]:[N/

/FCFS]系统，其中N=4+1=5，

=4人/小时，

=6人/小时，

=2/3。第68页,共128页，2024年2月25日，星期天因客满而离去的概率为0.0048第69页,共128页，2024年2月25日，星期天当N=6时P5-P6=0.0480-0.0311=0.0169=1.69%即增加一张椅子可以减少顾客损失率1.69%第70页,共128页，2024年2月25日，星期天[M/M/1]:[∞/m/FCFS]模型

设顾客总数为m。当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中。如此循环往复。服务台...顾客源需要服务服务完毕队列第71页,共128页，2024年2月25日，星期天顾客源中剩余的顾客数

乘以每个顾客到达的速率0m-112m-2mλ(m-1)λ2λλμμμμmμμ(m-2)λ3λ

假定每一台机器在单位时间内发生故障的平均次数是相同的，设为λ。当正在等待及正在接受维修的机器台数为Ls时，则在单位时间内发生故障的平均机器数为：

λe=λ(m-Ls)第72页,共128页，2024年2月25日，星期天状态转移方程λ0P0=μP1 ……[λn+μ]Pn=μPn+1+λn-1Pn-1

(n=1，2，…，m-1)

……μPm=λm-1Pm-1

(n=1，2，…，m) 第73页,共128页，2024年2月25日，星期天运行指标第74页,共128页，2024年2月25日，星期天(1)修理工空闲的概率；(2)五台机器都出故障的概率；(3)出故障的平均台数；(4)平均停工时间；(5)平均等待修理时间；(6)评价系统运行情况。例4

某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运行时间15分钟。有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求:第75页,共128页，2024年2月25日，星期天解根据题意，m=5，λ=1/15，μ=1/12，ρ=λ/μ=0.8

第76页,共128页，2024年2月25日，星期天第77页,共128页，2024年2月25日，星期天第4节多服务台负指数分布排队系统的分析第78页,共128页，2024年2月25日，星期天多服务台模型[M/M/c]标准的[M/M/c]:[∞/∞/FCFS]模型系统容量有限的[M/M/c]:[N/∞/FCFS]模型有限顾客源的[M/M/c]:[∞/m/FCFS]模型第79页,共128页，2024年2月25日，星期天[M/M/c]:[∞/∞/FCFS]模型服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列

顾客到达后，进入队列尾端；当某一个服务台空闲时，队列中的第一个顾客即到该服务台接收服务；服务完毕后随即离去。各服务台互相独立且服务速率相同，即μ1=μ2=…=μc

第80页,共128页，2024年2月25日，星期天

系统的服务速率与系统中的顾客数有关。当系统中的顾客数k不大于服务台个数，即1≤k≤c时，系统中的顾客全部在服务台中，这时系统的服务速率为kμ；当系统中的顾客数k＞c时，服务台中正在接受服务的顾客数仍为c个，其余顾客在队列中等待服务，这时系统的服务速率为cμ。只有当ρ＜1时系统才不会排成无限的队列。服务强度服务机构平均利用率第81页,共128页，2024年2月25日，星期天状态转移图与状态转移方程对状态0: λP0=μP1

对状态1: λP0+2μP2=(λ+μ)P1 …………对状态c： λPc-1+cμPc+1=(λ+cμ)Pc …………对状态n λPn-1+cμPn+1=(λ+cμ)Pn ………01cn第82页,共128页，2024年2月25日，星期天状态概率第83页,共128页，2024年2月25日，星期天运行指标第84页,共128页，2024年2月25日，星期天例5

某售票处有三个窗口，顾客到达服从Poisson流，到达速率为0.9人／分，售票时间服从负指数分布，每个窗口的平均售票速率为0.4人／分。顾客到达后排成一队，依次到空闲窗口购票。求：(1)所有窗口都空闲的概率；(2)平均队长；(3)平均等待时间及逗留时间；(4)顾客到达后必须等待的概率。第85页,共128页，2024年2月25日，星期天解：λ/μ=2.25，ρ=λ/cμ=0.75(1)所有窗口都空闲的概率，即求P0的值(2)平均队长，即求Ls的值，必须先求Lq

第86页,共128页，2024年2月25日，星期天(3)平均等待时间和平均逗留时间，即求Wq和Ws和的值(4)顾客到达后必须等待，即n≥3第87页,共128页，2024年2月25日，星期天服务台服务台服务台顾客到达顾客离去顾客离去顾客离去

如果在上例中，购票者到达后在每个窗口各自排成一队，即排成3队，且进入队列后不离开，各列间也互不串换，这就形成3个队列，而上例中的其它条件不变。假设每个队列平均到达率相等且为：λ1＝λ2＝λ3＝0.9/3＝0.3（人/分钟）

这样，原来的M/M/3系统就变成了3个M/M/1型的子系统。第88页,共128页，2024年2月25日，星期天 M/M/c和c个M/M/1模型的比较指标（1）M/M/3型（2）M/M/1型售票处空闲的概率0.07480.25（各子系统）购票者必须等待的概率P(N>3)=0.570.75排队长1.7（人）2.25（人）（各子系统）平均队长3.95（人）9（人）（整个系统）平均逗留时间4.39（分钟）10（分钟）平均等待时间1.89（分钟）7.5（分钟）第89页,共128页，2024年2月25日，星期天[M/M/c]:[N/∞/FCFS]模型离开服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列

设系统容量为N(N≥c)。设顾客到达的速率为λ，每个服务台服务的速率为μ，ρ=λ/cμ。由于系统不会无限止地接纳顾客，对ρ不必加以限制。第90页,共128页，2024年2月25日，星期天状态转移图与状态转移方程对状态0: λP0=μP1

对状态1: λP0+2μP2=(λ+μ)P1 …………对状态c： λPc-1+cμPc+1=(λ+cμ)Pc …………对状态N λPN-1=cμPN ………01cN第91页,共128页，2024年2月25日，星期天状态概率第92页,共128页，2024年2月25日，星期天运行指标第93页,共128页，2024年2月25日，星期天例6某旅馆有8个单人房间，旅客到达服从Poisson流，平均速率为6人／天，旅客平均逗留时间为2天，求：(1)每天客房平均占用数；(2)旅馆客满的概率。第94页,共128页，2024年2月25日，星期天解：旅馆8个房间全满的概率为0.423平均占用客房数为6.9间。第95页,共128页，2024年2月25日，星期天[M/M/c]:[∞/m/FCFS]模型顾客到达修理速率μ发生故障等待修理的机器修理速率μ修理速率μ正在修理的机器到达速率(m-n)λ修理速率cμ运行的机器数m-n第96页,共128页，2024年2月25日，星期天状态概率其中第97页,共128页，2024年2月25日，星期天运行指标

有效到达速率λe为单位时间内出现故障的机器数，有

λe=λ(m-Ls)第98页,共128页，2024年2月25日，星期天例7

车间有5台机器，每台机器的故障率为1次／小时，有2个修理工负责修理这5台机器，工作效率相同，为4台／小时。求：(1)等待修理的平均机器数；(2)正在修理的平均机器数；(3)每小时发生故障的平均机器数；(4)平均等待修理的时间；(5)平均停工时间。第99页,共128页，2024年2月25日，星期天解可以计算得到（算式略）：P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.002第100页,共128页，2024年2月25日，星期天由此，计算系统的各项运行指标如下：第101页,共128页，2024年2月25日，星期天第5节一般服务时间M/G/1模型第102页,共128页，2024年2月25日，星期天

服务时间一般分布时，需要知道服务时间的均值和方差。当时，排队系统可以达到平稳状态。P－K公式第103页,共128页，2024年2月25日，星期天1负指数服务时间M/M/1模型只有负指数分布时排队长的一半。2定长服务时间M/D/1模型第104页,共128页，2024年2月25日，星期天3k阶爱尔朗服务时间M/Ek/1模型

若顾客需接受k个串行的服务台的服务后才离开，且每个服务台服务时间服从负指数分布，平均服务时间相等。 则总服务时间服从k阶爱尔朗分布。第105页,共128页，2024年2月25日，星期天Erlang分布的均值和方差总服务时间服从爱尔朗分布：每个服务台的平均服务时间是：第106页,共128页，2024年2月25日，星期天M/Ek/1系统的运行指标第107页,共128页，2024年2月25日，星期天

例8

有一汽车冲洗台，汽车按Poisson流到达，平均每小时到达18辆；冲洗时间T的平均值=0.05小时/辆，方差Var(T)=0.01(小时/辆)2，求该洗车台的运行指标，并对它进行评价。

解：本例是M/G/1系统，且已知第108页,共128页，2024年2月25日，星期天

可见顾客等待时间太长，队列也太长。主要原因是服务时间的方差太大！第109页,共128页，2024年2月25日，星期天例9

某单人裁缝店做西服，每套需经过4个不同的工序，4个工序完成后才开始做另一套。每一工序的时间服从负指数分布，期望值为2小时。顾客到来服从泊松分布，平均订货率为5.5套/周（设一周6天，每天8小时）。问一顾客为等到做好一套西服期望时间有多长？解：λ=5.5套/周1/μ:平均每套所需时间1/4μ:平均每工序所需时间，为2小时μ＝1/8套/小时＝6套/周第110页,共128页，2024年2月25日，星期天顾客为等到做好一套西服期望时间：第111页,共128页，2024年2月25日，星期天排队论练习题第112页,共128页，2024年2月25日，星期天

练习1：某修理店只有一位修理工，来修理的顾客到达过程为Poisson流，平均每小时4人；修理时间服从负指数分布，平均需要6分钟。试求：修理店空闲的概率；店内恰有3位顾客的概率；店内至少有一位顾客的概率；在店内平均顾客数；每位在店内平均逗留时间；等待服务的平均顾客数；每位顾客平均等待服务时间；顾客在店内逗留时间超过10分钟的概率。第113页,共128页，2024年2月25日，星期天解：本例可看成一个M/M/1/

排队问题，其中=4，=1/0.1=10(人/小时），=/=2/5<11、修理店内空闲的概率

P0=1-=(1-2/5)=0.62、店内恰有3个顾客的概率

P3=

3(1-)=(2/5)3(1-2/5)=0.0383、店内至少有1位顾客的概率

P{N

1}=1-P0=1-(1-)==2/5=0.4第114页,共128页，2024年2月25日，星期天4、在店内平均顾客数

L=/(1-)=(2/5)/(1-2/5)=0.67(人）5、每位顾客在店内平均逗留时间

W=L/=0.67/4=10分钟6、等待服务的平均顾客数

Lq=L-=0.67-2/5=0.27(人)7、每个顾客平均等待服务时间

Wq=Lq/=0.27/4=0.0675小时=4分钟第115页,共128页，2024年2月25日，星期天8、顾客在店内逗留时间超过10分钟的概率P{T>10}=e-10(1/6-1/15)=e-1=0.3677P{T>t}=e-(

-

)tt=10分钟,

=10人/小时=10/60=1/6=4人/小时=4/60=1/15第116页,共128页，2024年2月25日，星期天

练习2：考虑一个铁路列车编组站。设待编列车到达时间间隔服从负指数分布，平均每小时到达2列；服务台是编组站，编组时间服从负指数分布，平均每20分钟可编一组。已知编组站上共有2股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求：

1、在平衡状态下系统中列车的平均数；

2、每一列车的平均逗留时间；

3、等待编组的列车平均数；

4、列车在系统中的平均等待编组时间；

5、如果列车因站中2股道均被占用而停在站外或前方站时，每列车每小时费用为a元，求每天由于列车在站外等待而造成的损失。第117页,共128页，2024年2月25日，星期天解：本例可看成一个M/M/1/

排队问题，其中=2，=3，=/=2/3<11、系统中列车的平均数

L=/(1-)=(2/3)/(1-2/3)=2（列）

2、列车在系统中的平均停留时间

W=L/

=2/2=1（小时）

3、系统中等待编组的列车平均数

Lq=L-=2-2/3=4/3（列）

4、列车在系统中的平均等待编组时间

Wq=Lq/=(4/3)/(1/2)=2/3（小时）第118页,共128页，2024年2月25日，星期天5、记列车平均延误（由于站内2股道均被占用而不能进站）时间为W0则

W0=WP{N>2}=W{1-P0-P1-P2}=W{1-(l-)-(l-)1-(l-)2}=1*3=3=(2/3)3=0.296（小时）故每天列车由于等待而支出的平均费用E=24W0a=24*2*0.296*a=14.2a元第119页,共128页，2024年2月25日，星期天

练习3：

(病人候诊问题)某单位医院的一个科室有一位医生值班，经长期观察，每小平均有4个病人，医生每小时平均可诊5个病人，病人的到来服从泊松分布，医生的诊病时间服从负指数分布，试问：

1、该科室平均有病人数；平均排队候诊病人数；看一次病平均所需的时间；排队等候看病的平均时间

2如果满足99%以上的病人有座，此科室至少应设多少座位?3如果该单位每天24小时上班，病人看病1小时因耽误工作单位要损失30元，这样单位平均每天损失多少元? 4如果该科室提高看病速度，每小时平均可诊6个病人，单位每天可减少损失多少?可减少多少座位?第120页,共128页，2024年2月25日，星期天解：该模型为M\M\1该科室平均有病人数为该科室内排队候诊病人数为

看一次病平均所需的时间为排队等候看病的平均时间为为满足99%以上的病人有座，设科室应设m个座位，则m应满足

第121页,共128页，2024年2月25日，星期天

所以该科室至少应设2