运筹学课件制作,北京理工大学 吴祈宗等
2
第六章 排队论基本概念输入过程和服务时间分布泊松输入 ——指数服务排队模型其他模型选介排队系统的优化目标与最优化问题本章内容重点
3
排队论 (Queuing Theory)，
又称随机服务系统理论 (Random
Service System Theory),是一门研究拥挤现象 (排队,等待 )的科学 。 具体地说,它是在研究各种排队系统概率规律性的基础上,
解决相应排队系统的最优设计和最优控制问题 。
前 言
4
排队是我们在日常生活和生产中经常遇到的现象 。 例如,上,下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象 。 除了上述有形的排队之外,
还有大量的所谓,无形,排队现象,如几个顾客打电话到出租汽车站要求派车,如果出租汽车站无足够车辆,则部分顾客只得在各自的要车处等待,他们分散在不同地方,却形成了一个无形队列在等待派车 。 排队的不一定是人,
也可以是物：
前 言
5
例如,通讯卫星与地面若干待传递的信息；生产线上的原料,
半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等 。
前 言
6
显然,上述各种问题虽互不相同,
但却都有要求得到某种服务的人或物和提供服务的人或机构 。 排队论里把要求服务的对象统称为,顾客,,而把提供服务的人或机构称为,服务台,或,服务员,。 不同的顾客与服务组成了各式各样的服务系统 。 顾客为了得到某种服务而到达系统,若不能立即获得服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统,见图 6-1至图 6-5。
前 言
7
不同的顾客与服务组成了各式各样的服务系统 。 顾客为了得到某种服务而到达系统,若不能立即获得服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统,见图 6-1至图 6-5。
图 6-1 单服务台排队系统前 言
8
图 6-2 单队列 —— S个服务台并联的排队系统图 6-3 S个队列 —— S个服务台的并联排队系统前 言
9
图 6-4 单队 —— 多个服务台的串联排队系统图 6-5 多队 —— 多服务台混联、网络系统前 言
10
图 6-6 随机服务系统前 言一般的排队系统,都可由下面图 6-6加以描述 。
11
通常称由图 6-6表示的系统为一随机聚散服务系统,任一排队系统都是一个随机聚散服务系统 。 这里,,聚,表示顾客的到达,,散,表示顾客的离去 。 所谓随机性则是排队系统的一个普遍特点,是指顾客的到达情况 (如相继到达时间间隔 )与每个顾客接受服务的时间往往是事先无法确切知道的,或者说是随机的 。 一般来说,
排队论所研究的排队系统中,顾客到来的时刻和服务台提供服务的时间长短都是随机的,因此这样的服务系统被称为随机服务系统 。
前 言
12
面对拥挤现象,人们总是希望尽量设法减少排队,通常的做法是增加服务设施 。
但是增加的数量越多,人力,物力的支出就越大,甚至会出现空闲浪费,如果服务设施太少,顾客排队等待的时间就会很长,
这样对顾客会带来不良影响 。 于是,顾客排队时间的长短与服务设施规模的大小,
就构成了设计随机服务系统中的一对矛盾 。
如何做到既保证一定的服务质量指标,又使服务设施费用经济合理,恰当地解决顾客排队时间与服务设施费用大小这对矛盾,
这就是随机服务系统理论 —— 排队论所要研究解决的问题 。
前 言
13
排队论是 1909年由丹麦工程师爱尔朗 (A.K,Erlang)在研究电活系统时创立的,几十年来排队论的应用领域越来越广泛,理论也日渐完善 。 特别是自二十世纪 60年代以来,
由于计算机的飞速发展,更为排队论的应用开拓了宽阔的前景 。
前 言
14
1.基 本 概 念一 排队系统的描述
（一）系统特征和基本排队过程实际的排队系统虽然千差万别，但是它们有以下的共同特征：
(1)有请求服务的人或物 —— 顾客 ；
(2)有为顾客服务的人或物，即服务员或服务台 ；
(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个 排队系统的状态也是随机的 。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员 (台 )又空闲无事。
15
任何一个排队问题的基本排队过程都可以用图 6-6表示 。 从图 6-6
可知,每个顾客由顾客源按一定方式到达服务系统,首先加入队列排队等待接受服务,然后服务台按一定规则从队列中选择顾客进行服务,
获得服务的顾客立即离开 。
1.基 本 概 念
16
（ 二 ） 排队系统的基本组成部分通常,排队系统都有输入过程,服务规则和服务台等 3个组成部分：
1,输入过程,这是指要求服务的顾客是按怎样的规律到达排队系统的过程,有时也把它称为顾客流,一般可以从 3个方面来描述 — 个输入过程 。
(1)顾客总体数,又称顾客源,输入源 。 这是指顾客的来源 。 顾客源可以是有限的,也可以是无限的 。 例如,到售票处购票的顾客总数可以认为是无限的,而某个工厂因故障待修的机床则是有限的 。
1.基 本 概 念
17
(2)顾客到达方式 。 这是描述顾客是怎样来到系统的,他们是单个到达,还是成批到达 。
病人到医院看病是顾客单个到达的例子 。 在库存问题中如将生产器材进货或产品入库看作是顾客,那么这种顾客则是成批到达的 。
(3)顾客流的概率分布,或称 相继顾客到达的时间间隔的分布 。 这是求解排队系统有关运行指标问题时,首先需要确定的指标 。 这也可以理解为在一定的时间间隔内到达 K个顾客
(K=1,2,? )的概率是多大 。 顾客流的概率分布一般有定长分布,二项分布,泊松流 (最简单流 ),爱尔朗分布等若干种 。
1.基 本 概 念
18
2.服务规则 。 这是指服务台从队列中选取顾客进行服务的顺序 。 一般可以分为损失制,
等待制和混合制等 3大类 。
(1)损失制 。 这是指如果顾客到达排队系统时,所有服务台都已被先来的顾客占用,那么他们就自动离开系统永不再来 。 典型例子是,
如电话拔号后出现忙音,顾客不愿等待而自动挂断电话,如要再打,就需重新拔号,这种服务规则即为损失制 。
1.基 本 概 念
19
(2)等待制 。 这是指当顾客来到系统时,所有服务台都不空,顾客加入排队行列等待服务 。 例如,排队等待售票,
故障设备等待维修等 。 等待制中,服务台在选择顾客进行服务时,常有如下四种规则：
① 先到先服务 。 按顾客到达的先后顺序对顾客进行服务,这是最普遍的情形 。
② 后到先服务 。 仓库中迭放的钢材,
后迭放上去的都先被领走,就属于这种情况 。
1.基 本 概 念
20
③ 随机服务 。 即当服务台空闲时,
不按照排队序列而随意指定某个顾客去接受服务,如电话交换台接通呼叫电话就是一例 。
④ 优先权服务 。 如老人,儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等,均属于此种服务规则 。
1.基 本 概 念
21
(3)混合制,这是等待制与损失制相结合的一种服务规则,一般是指允许排队,
但又不允许队列无限长下去 。 具体说来,
大致有三种：
① 队长有限 。 当排队等待服务的顾客人数超过规定数量时,后来的顾客就自动离去,另求服务,即系统的等待空间是有限的 。 例如最多只能容纳 K个顾客在系统中,当新顾客到达时,若系统中的顾客数 (又称为队长 )小于 K,则可进入系统排队或接受服务；否则,便离开系统,并不再回来 。 如水库的库容是有限的,旅馆的床位是有限的 。
1.基 本 概 念
22
② 等待时间有限 。 即顾客在系统中的等待时间不超过某一给定的长度 T，
当等待时间超过 T时,顾客将自动离去,
并不再回来 。 如易损坏的电子元器件的库存问题,超过一定存储时间的元器件被自动认为失效 。 又如顾客到饭馆就餐,
等了一定时间后不愿再等而自动离去另找饭店用餐 。
1.基 本 概 念
23
③ 逗留时间 (等待时间与服务时间之和 )有限 。 例如用高射炮射击敌机,
当敌机飞越高射炮射击有效区域的时间为 t时,若在这个时间内未被击落,也就不可能再被击落了 。
不难注意到,损失制和等待制可看成是混合制的特殊情形，如记 s为系统中服务台的个数，则当 K=s时，混合制即成为损失制；当 K=∞ 时，混合制即成为等待制。
1.基 本 概 念
24
3,服务台情况 。 服务台可以从以下 3方面来描述：
(1) 服务台数量及构成形式 。从数量上说，
服务台有单服务台和多服务台之分。从构成形式上看，服务台有：
①单队 —— 单服务台式；
②单队 —— 多服务台并联式；
③多队 —— 多服务台并联式；
④单队 —— 多服务台串联式；
⑤单队 —— 多服务台并串联混合式,以及多队 —— 多服务台并串联混合式等等。
见前面图 6-1至图 6-5所示。
1.基 本 概 念
25
(2) 服务方式 。 这是指在某一时刻接受服务的顾客数,它有单个服务和成批服务两种 。 如公共汽车一次就可装载一批乘客就属于成批服务 。
(3) 服务时间的分布 。 一般来说,
在多数情况下,对每一个顾客的服务时间是一随机变量,其概率分布有定长分布,负指数分布,K级爱尔良分布,一般分布 (所有顾客的服务时间都是独立同分布的 )等等 。
1.基 本 概 念
26
（ 三 ） 排队系统的描述符号与分类为了区别各种排队系统,根据输入过程,排队规则和服务机制的变化对排队模型进行描述或分类,可给出很多排队模型 。 为了方便对众多模型的描述,
肯道尔 （ D,G,Kendall） 提出了一种目 前 在 排 队 论 中 被 广 泛 采 用 的
,Kendall记号,,完整的表达方式通常用到 6个符号并取如下固定格式：
A/B/C/D/E/F
各符号的意义为：
1.基 本 概 念
27
A— 表示顾客相继到达间隔时间分布,常用下列符号：
M—— 表示到达过程为泊松过程或负指数分布；
D—— 表示定长输入；
Ek—— 表示 k阶爱尔朗分布；
G—— 表示一般相互独立的随机分布 。
B— 表示服务时间分布,所用符号与表示顾客到达间隔时间分布相同 。
M—— 表示服务过程为泊松过程或负指数分布；
D—— 表示定长分布；
Ek —— 表示 k阶爱尔朗分布；
G—— 表示一般相互独立的随机分布 。
1.基 本 概 念
28
C— 表示服务台 (员 )个数：,1”则表示单个服务台,,s”。 (s＞ 1)表示多个服务台 。
D— 表示系统中顾客容量限额,或称等待空间容量； 如系统有 K个等待位子,则 0<K<∞,
当 K=0 时,说明系统不允许等待,即为损失制 。 K=∞ 时为等待制系统,此时 ∞ 般省略不写 。 K为有限整数时,表示为混合制系统 。
E— 表示顾客源限额,分有限与无限两种,∞
表示顾客源无限,此时一般 ∞ 也可省略不写 。
1.基 本 概 念
29
F— 表示服务规则,常用下列符号：
FCFS：表示先到先服务的排队规则；
LCFS：表示后到先服务的排队规则；
PR：表示优先权服务的排队规则 。
例如：某排队问题为 M／ M／ S／ ∞ ／ ∞ ／ FCFS／,
则表示顾客到达间隔时间为负指数分布 (泊松流 )；
服务时间为负指数分布；有 s(s＞ 1)个服务台；系统等待空间容量无限 (等待制 )；顾客源无限,采用先到先服务规则 。
某些情况下,排队问题仅用上述表达形式中的前 3个,4个,5个符号 。 如不特别说明则均理解为系统等待空间容量无限；顾客源无限,先到先服务,单个服务的等待制系统 。
1.基 本 概 念
30
二,排队系统的主要数量指标研究排队系统的目的是通过了解系统运行的状况,对系统进行调整和控制,使系统处于最优运行状态 。 因此,首先需要弄清系统的运行状况 。 描述一个排队系统运行状况的主要数量指标有：
1.基 本 概 念
31
1.队长和排队长 （ 队列长 ）
队长 是指系统中的平均顾客数 (排队等待的顾客数与正在接受服务的顾客数之和 )，
排队长 是指系统中正在排队等待服务的平均顾客数 。
队长和排队长一般都是随机变量 。
我们希望能确定它们的分布,或至少能确定它们的平均值 (即平均队长和平均排队长 )及有关的矩 (如方差等 )。 队长的分布是顾客和服务员都关心的,特别是对系统设计人员来说,如果能知道队长的分布,
就能确定队长超过某个数的概率,从而确定合理的等待空间 。
1.基 本 概 念
32
2,等待时间和逗留时间从顾客到达时刻起到他开始接受服务止这段时间称为 等待时间,是随机变量,也是顾客最关心的指标,因为顾客通常希望等待时间越短越好 。 从顾客到达时刻起到他接受服务完成止这段时间称为 逗留时间,也是随机变量,同样为顾客非常关心 。 对这两个指标的研究当然是希望能确定它们的分布,或至少能知道顾客的平均等待时间和平均逗留时间 。
1.基 本 概 念
33
3,忙期和闲期忙期 是指从顾客到达空闲着的服务机构起,到服务机构再次成为空闲止的这段时间,即服务机构连续忙的时间 。 这是个随机变量,是服务员最为关心的指标,因为它关系到服务员的服务强度 。 与忙期相对的是 闲期,即服务机构连续保持空闲的时间 。 在排队系统中,忙期和闲期总是交替出现的 。
除了上述几个基本数量指标外,还会用到其他一些重要的指标,如在损失制或系统容量有限的情况下,由于顾客被拒绝,
而使服务系统受到损失的顾客损失率及服务强度等,也都是十分重要的数量指标 。
1.基 本 概 念
34
4.一些数量指标的常用记号
(1)主要数量指标
N(t)：时刻 t系统中的顾客数 (又称为系统的状态 ),即队长；
Nq(t)：时刻 t系统中排队的顾客数,
即排队长；
T(t)：时刻 t到达系统的顾客在系统中的逗留时间；
Tq(t)：时刻 t到达系统的顾客在系统中的等待时间 。
1.基 本 概 念
35
上面给出的这些数量指标一般都是和系统运行的时间有关的随机变量,求这些随机变量的瞬时分布一般是很困难的 。 为了分析上的简便,并注意到相当一部分排队系统在运行了一定时间后,都会趋于一个平衡状态 (或称平稳状态 )。 在平衡状态下,队长的分布,等待时间的分布和忙期的分布都和系统所处的时刻无关,而且系统的初始状态的影响也会消失 。 因此,我们 在本章中将主要讨论与系统所处时刻无关的性质,即统计平衡性质 。
1.基 本 概 念
36
L或 Ls—— 平均队长,即稳态系统任一时刻的所有顾客数的期望值；
Lq—— 平均等待队长或队列长,即稳态系统任一时刻的等待服务的顾客数的期望值；
W或 Ws—— 平均逗留时间,即 (在任意时刻 )进入稳态系统的顾客逗留时间的期望值；
Wq—— 平均等待时间,即 (在任意时刻 )进入稳态系统的顾客等待时间的期望值 。
这四项主要性能指标 (又称主要工作指标 )的值越小,说明系统排队越少,等待时间越少,因而系统性能越好 。 显然,
它们是顾客与服务系统的管理者都很关注的 。
1.基 本 概 念
37
(2)其他常用数量指标
s—— 系统中并联服务台的数目；
( 或? )—— 平均到达率；
1/?( 或 1/? )—— 平均到达间隔 。
( 或? )—— 平均服务率；
1/?( 或 1/? )—— 平均服务时间 。
—— 服务强度,即每个服务台单位时间内的平均服务时间；一般有?=?/(s?) ；
N—— 稳态系统任一时刻的状态 (即系统中所有顾客数 )；
U—— 任一顾客在稳态系统中的逗留时间；
1.基 本 概 念
38
Q—— 任一顾客在稳态系统中的等待时间 。
N,U,Q都是随机变量 。
Pn=P{N=n},稳态系统任一时刻状态为 n的概率；特别当 n=0时,Pn即 P0,而
P0即稳态系统所有服务台全部空闲 (因系统中顾客数为 0)的概率 。
对于损失制和混合制的排队系统,顾客在到达服务系统时,若系统容量已满,
则自行消失 。 这就是说,到达的顾客不一定全部进入系统,为此引入：
1.基 本 概 念
39
e( 或?e )—— 有效平均到达率,即每单位时间内进入系统的平均顾客数 （ 期望值 ） ； 这时?就是期望每单位时间内来到系统 (包括未进入系统 )的平均顾客数
（ 期望值 ）
对于等待制的排队系统,有?e=? 。
在系统达到稳态时,假定平均到达率为常数?,则 有 下 面 的 李 特 尔 (John
D,C,Little)公式：
1.基 本 概 念
WL e
qeq WL
(6-1a)
(6-1b)
40
又假定平均服务时间为常数 1／?,则有
(6-1c)
(6-ld)
因此,只要知道 L,Lq,W,Wq四者之一,则其余三者就可由 (6— 1)式求得 。 另外还有
1.基 本 概 念
1
qWW
e
qLL
0n
nnPL (6-2)
41
(6-3)
因此,只要知道 Pn(n=0,1,2… ),则 L
或 Lq就可由 (6-2)或 (6-3)式求得,从而再由 (6-1)式就能求得四项主要工作指标 。
1.基 本 概 念
sn n
msnq nPPsnL
0
)(
42
一,输入过程由前所述,输入过程是描述各种类型的顾客以怎样的规律到达系统,一般用相继两顾客到达时间间隔?来描述系统输入特征 。 主要输入过程有：
1,定长输入 。 这是指顾客有规则地等距到达,每隔时间?到达一个顾客 。 这时相继顾客到达间隔?的分布函数 F(t)为：
2.输入过程和服务时间分布
t
ttPtF
,0
,1}{)( (6-4)
例如,生产自动线上产品从传送带上进入包装箱就是这种情况,
43
2,泊松 (poisson)输入,又称最简单流 。
满足下面 3个条件的输入称之为最简单流 。
(1) 平稳性 。 又称作输入过程是平稳的,
指在长度为 t的时段内恰好到达 k个顾客的概率仅与时段长度有关,而与时段起点无关 。
即对任意?∈ (0,∞),在 (?,?+t]或 (0,t)内恰好到达 k个顾客的概率相等：
设初始条件为,且有 。
)(})({})0()({})()({ tVktPktPkataP k
0
1
K
KV1)0(0?V
2.输入过程和服务时间分布
44
(2)无后效性 。 指在任意几个不相交的时间区间内,各自到达的顾客数是相互独立的 。 通俗地说就是以前到达的顾客情况,
对以后顾客的到来没有影响 。 否则就是关联的 。
(3)单个性又称普通性 。 指在充分小的时段内最多到达一个顾客 。 因为泊松流实际应用最广,也最容易处理,因而研究得也较多,可以证明,对于泊松流,在长度为 t的时间内到达 K个顾客的概率 vk(t)服从泊松分布,即
2.输入过程和服务时间分布
45
其中参数?>0为一常数,表示单位时间内到达顾客的平均数,又称为顾客的平均到达率 。
对于泊松流,不难证明其相继顾客到达时间间隔?i,i=1,2,… 是相互独立同分布的,其分布函数为负指数分布：
（ 6-6）
!
)()(
K
tetV Kt
k
,2,1,0?K （ 6-5）
0,0
0,1)(
t
tetF t
i
),2,1(i
2.输入过程和服务时间分布
46
3.爱尔朗输入,这是指相继顾客到达时间间隔?相互独立,具有相同的分布,其分布密度为
（ 6-7）
其中 k为非负整数 。
可以证明,在参数为?的泊松输人中,对任意的
j与 k,设第 j与第 j+k个顾客之间的到达间隔为 。 则随机变量 Tk的分布必遵从参数为?的爱尔朗分布,其分布密度为：
0)!1( )()(
1
teK tta t
K
)( 21 kkk TT
2.输入过程和服务时间分布
47
例某排队系统有并联的 k个服务台,顾客流为泊松流,规定第 i,K+i,2K+i…个顾客排入第 i号台 (i=1,2,…,K),则第 K台所获得的顾客流,即为爱尔朗输入流,其他各台,从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流 。
此外,爱尔朗分布中,当 K＝ 1时将化为负指数分布 。
0)!1( )()(
1
teK tta t
K
2.输入过程和服务时间分布
48
4.一般独立输入,即相继顾客到达时间间隔相互独立,同分布,分布函数
F(t)是任意分布,因此,上面所述的所有输入都是一般独立分布的特例 。
5.成批到达的输入 。 这时排队系统每次到达的顾客不一定是一个,而可能是一批,每批顾客的数目 n是一个随机变量 。 其分布为：
到达时间间隔可能是上述几类输入中的一种 。
2.输入过程和服务时间分布
（ 6-8）
kaknP }{?,2,1,0?K
49
二,服务时间分布
1,定长分布 。 每一个顾客的服务时间 都是常数?,此时服务时间 t的分布函数 为：
（ 6-9）
2,负指数分布 。 即各个顾客的服务时间相互独立,具有相同的负指数分布：
(6-10)
其中?>0为一常数，服务时间 t的数学期望称为平均服务时间。显然，对于负指数分布
2.输入过程和服务时间分布
x
xxtPxB
0
1)()(
0,0
0,1)(
x
xexB x?
50
3.爱尔朗分布,即每个顾客的服务时间相互独立,具有相同的爱尔朗分布 。 其密度函数为其中?>0为一常数,此种的平均服务时间为：
K=1时爱尔朗分布化归为负指数分布当 K→∞
时,得到长度为 1/?的定长服务 。
2.输入过程和服务时间分布
0 0 1)()( dxxexx d BtE mx(6-11)
(6-12) 0,
)!1(
)()( 1?
xek xkkxb xk
k
0 1)()(?dxxxbtE (6-13)
51
4.一般服务分布 。 所有顾客的服务时间都是相互独立具有相同分布的随机变量,其分布函数记 B(X),前面所述的各种服务分布都是一般服务分布的特例 。
5.多个服务台的服务分布 。 可以假定各个服务台的服务分布参数不同或分布类型不同 。
6.服务时间依赖于队长的情况 。 指服务员排队的人愈多,服务的速度也就愈快 。
2.输入过程和服务时间分布
52
三,排队论研究的基本问题排队论研究的首要问题是排队系统主要数量指标的概率规律,即研究系统的整体性质,然后进一步研究系统的优化问题 。 与这两个问题相关的还包括排队系统的统计推断问题 。
(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征,
了解系统运行的基本特征 。
(2)统计推断问题,建立适当的排队模型是排队论研究的第一步,建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等 。
2.输入过程和服务时间分布
53
(3)系统优化问题,又称为系统控制问题或系统运营问题,其基本目的是使系统处于最优或最合理的状态 。 系统优化问题包括最优设计问题和最优运营问题,其内容很多,
有最少费用问题,服务率的控制问题,服务台的开关策略,顾客 (或服务 )根据优先权的最优排序等方面的问题 。
对于一般的排队系统运行情况的分析,
通常是在给定输入与服务条件下,通过求解系统状态为 n(有 n个顾客 )的概率 Pn(t),再进行计算其主要的运行指标,
2.输入过程和服务时间分布
54
① 系统中顾客数 (队长 )的期望值 L或 Ls；
② 排队等待的顾客数 (排队长 )的期望值 Lq；
③ 顾客在系统中全部时间 (逗留时间 )的期望值 W或 Ws；
④ 顾客排队等待时间的期望值 Wq。
排队系统中,由于顾客到达分布和服务时间分布是多种多样的,加之服务台数 。 顾客源有限无限,排队容量有限无限等的不同组合,
就会有不胜枚举的不同排队模型,若对所有排队模型都进行分析与计算,不但十分繁杂而且也没有必要 。 下面拟分析几种常见排队系统模型 。
2.输入过程和服务时间分布
55
对于泊松输入 — 负指数分布服务的排队系统的一般决策过程：
① 根据已知条件绘制状态转移速度图。
② 依据状态转移速度图写出各稳态概率之间的关系。
③ 求出 P0 及 Pn 。
3.泊松输入 — 指数服务排队模型
56
④ 计算各项数量运行指标。
⑤ 用系统运行指标构造目标函数，对系统进行优化。
典型分布 —— 泊松分布及其性质，负指数分布及其性质泊松分布 (平稳状态）? > 0 为单位时间平均到达的顾客数
P{ I = n }=?n e-? / n!
(n=0,1,2,… )
3.泊松输入 — 指数服务排队模型
57
负指数分布? 为平均服务率，即单位时间服务的顾客数。
P（服务时间 ≤ t ) = 1- e-? t t ≥ 0
系统状态概率分布及状态转移速度图 —— 基本的概率分布推导
3.泊松输入 — 指数服务排队模型
58
系统状态概率分布：
λ n：系统状态为 n时,顾客进入系统的平均速度 。
μ n：系统状态为 n时,顾客离开系统的平均速度 。
Pn(t):t时刻,系统内有几个顾客的概率 。
(t,t+Δ t)有一个顾客到达概率 λ nΔ t，
无顾客到达的概率 1-λ nΔ t（ 近似 ）
3.泊松输入 — 指数服务排队模型各种方式发生概率表3.泊松输入 — 指数服务排队模型
60
Pn(t+Δ t)=Pn(t)(1-λ nΔ t)(1-μ nΔ t)
+Pn-1(t)λ n-1Δ t(1-μ n-1Δ t)+Pn+1(t)(1-
λ n+1Δ t)μ n+1Δ t+Pn(t)λ nΔ tμ nΔ t
(dPn(t)/dt)=limΔt -0(Pn(t+Δ t)-Pn(t)/Δ t)
(Δ t2 项 都 变 为 零 )=Pn-1(t)λ n-1-
Pn(t)(λ n+μ n)+Pn-1(t)μ n-1
3.泊松输入 — 指数服务排队模型方式 1,2,3,4互不相容且完备，于是：
61
当 n=0时,只有方式 1和 3,4发生,且方式 1中无离去的概率为 1,则
dP0(t)/dt=-P0(t)λ 0+P1(t)μ 1
我们假设系统是稳态的,即与时刻无关,于是可得,dPn(t)/dt=0； -λ 0P0+μ 1P1=0
λn -1Pn-1-(μ n+λ n)Pn+μ n+1Pn+1=0
n=1,2,3……
λ 0P0=μ 1P1,P1=λ 0/μ 1P0
λ 0P0-(λ 1+μ 1)P1+μ 2P2=0
μ 1 P1-(λ 1+μ 1)P1+μ 2P2=0
P2=(λ 1/μ 2)P1=(λ 0λ 1/μ 1μ 2)P0
Pn=(λ n-1/μ n)Pn-1=(∏ i=0n-1λ i/∏ j=1nuj)p0
3.泊松输入 — 指数服务排队模型
62
λ 0P0-(λ 1+μ 1)P1+μ 2P2=0
μ 1 P1-(λ 1+μ 1)P1+μ 2P2=0
P2=(λ 1/μ 2)P1=(λ 0λ 1/μ 1μ 2)P0
n-1 nP
n=(λ n-1/μ n)Pn-1=(∏ λ i / ∏ uj)p0
i=0 j=1
又知,?Pn=1 (各事件两两不相容,且完备 ）
P0+(λ 0/μ 1)P0+(λ 1λ 0/μ 2 μ 1)P0+… +
n-1 n(∏ λ
i / ∏ uj)p0=1i=0 j=1
3,泊松输入 — 指数服务排队模型
63
状态转移速度图由此图易得：转入率 =转出率
n=0时,λ0P0=μ1P1
n一般,λn-1Pn-1+μn+1Pn+1=(λn+μn)Pn
同样可得下列公式,n = 1,2,…
n-1 nP
n=(λ n-1/μ n)Pn-1=(∏ λ i / ∏ uj)p0
i=0 j=1
0 n1 2 3
λ0 λ2λ1 λn-1 λn
μ1 μnμ3μ2 μn+1
3,泊松输入 — 指数服务排队模型
64
∞
L=∑kPk
k=0
Lq=∑(k-c)Pk c为服务台数
k>c
有效到达率 λe,有效离去 μe在平稳状态下：
λe=μe=∑λnPn=∑μnPn
关系,Little公式：
系统运行指标：
3,泊松输入 — 指数服务排队模型
65
系统的运行指标,(稳态时）
1.系统中顾客数的期望值：
∞
L=∑KPk
k=0
2.排队等待的顾客数的期望值：
Lq=∑(K-C) Pk
k>c
3,泊松输入 — 指数服务排队模型
66
3.有效到达率 λe:
稳态情况下,单位时间内进入系统的顾客数的期望值等于单位时间内离开系统的顾客数的期望值即,λe=μe
当系统中有 n个顾客时,每单位时间进入系统的顾客平均数为 λn,每单位时间离开系统的顾客平均数为 μn
λe=∑λnPn
μe=∑μnPn
3,泊松输入 — 指数服务排队模型
67
4.L,L q,λe,W,Wq之间的关系：
Little证明了：
W=L/λe,Wq=Lq/λe
几何解释,稳态时,一个顾客,进入系统后,每单位时间,平均到达 λe顾客 。
λe λe λe λe λe
进入时刻 离开时刻总时间 Ws
队长 Ls由时间段内个 λe组成的 Ls=λeWs
3,泊松输入 — 指数服务排队模型
68
同理,Lq=λeWq
又 W=Wq+（ 1/μ）
-------W与 Wq只相差一段平均服务时间 1/μ
L=Lq+(λe/μ)
3,泊松输入 — 指数服务排队模型
69
M/M/1 无限源系统稳态概率方程：
Pn= (λ/μ)Pn-1=…… = (λ/μ)nP0 1?n? N
0 N-11 2 N-2
λ λ λ λ
μ μμ μ
N
1,M/M/1/N/∞ 参数 λ,μ
系统状态转移速度：
70
由 ∑ Pn=1
n=0
M/M/1 无限源系统
N∑( λ/μ )nP
0=1
n=0
N
P0=1/[∑( λ/μ )n]=
n=0 (1- λ/μ )/
[(1- (λ/μ )N+1]λ?μ
1/(N +1) λ =μ
Pn=
1/(N +1) λ =μ
(1- λ/μ )(λ/μ )n/[(1- (λ/μ )N+1]
λ?μ
71
N
L=∑ nPn
n=0
M/M/1 无限源系统各计算公式：
λ e=∑ λ nPn=λ (1-PN)+0PN
(只有 Pn不再进人,故 λ n=0,其余均为 λ )
μ e =∑ μ nPn=0P0+μ (1-P0)（ 同理 ）
W =L/λ e,Wq=W -(1/μ ),Lq=Wqλ e
72
其他指标：
λ损 =λ-λe=λPN
P忙 =1-P0,P闲 =P0 （ 只有一个服务台 ）
平均服务台忙期的长度 T忙,
平均服务台闲期的长度 T闲,
T忙 / T闲 = P忙 / P闲 =(1- P0)/ P0
T闲 =1/λ(是从一个顾客到下一个顾客到达的平均间隔时间 )
于是 T忙 =(1- P0)/ λP0
M/M/1 无限源系统
73
2.M/M/1/∞/∞,λ μ
M/M/1 无限源系统稳态概率方程：
Pn=（ λ/μ） Pn-1=(λ/μ)nP0 令 ρ =λ/μ
0 n1 2 n-1
λ λ λ λ
μ μμ μ
λ
μ
∞
当 ρ? 1时,∑ρn不收敛，故应 ρ<1,
n=0即 λ<μ
74
∞P
0=1/(∑ρn)= 1-ρ 或 P0=1-λ/μn=0
M/M/1 无限源系统
Pn=ρn(1-ρ) 或 Pn=(λ/μ)n(1-λ/μ)
75
M/M/1 无限源系统进而：
∞L =
∑ n(ρn - ρn+1)
n=1
∞ ∞=
∑nρn - ∑nρn+1
n=1 n=1∞ ∞
=ρ+ ∑ nρn -∑ nρn +1
n=2 n=1∞
= ρ+∑ ρn +1
n=1
= ρ+ρ2/(1-ρ) = ρ/(1-ρ)
= λ/(μ-λ) (ρ=λ/μ)
取出第一项 写成∞∑ （ n+1） ρn+1
n=1与后一项合并
76
这里,
λe=μ(1-P0)=λ
W=L/λe=1/（ μ-λ）
Wq=W-1/μ=λ/[μ(μ-λ)]
Lq=λWq=λ2/[μ(μ-λ)]
系统内顾客数多于 k个的概率
P( N > k ) =?k+1
顾客逗留时间超过 t的概率
P( U > t ) = e-()t
M/M/1 无限源系统
77
P1=λ/（ μ+λ）
P损 =P忙 =P1= λ /（ μ+λ）
P闲 =P0= μ /（ μ+λ）
M/M/1 无限源系统
3.损失制 M/M/1/1,顾客到达若服务台被占用立即离开 。
直接可得：
P0= (1-ρ) / (1-ρ)2
= 1 / (1+ρ)
=μ / (μ+λ) P0+P1=1
78
1..M/M/C/N
M/M/C 无限源系统
0 N-11 2 N-2
λ λ λ λ
μ cμ2μ cμ
NCC-1
λ λ
cμ cμ
C+1
3μ
λ
(c-1)μ
λ
cμcμ
λ λ
稳态概率应满足的关系：
当 n<c时,Pn=[λ/(nμ) ]Pn-1
当 n?c时,Pn =[λ/(cμ)] Pn-1
令 ρ=λ/（ cμ） 系统负荷强度系数
79
c/nρPn-1=… =cn/n﹗ ρnP0
n<c
ρPn-1=… =cc/c﹗ ρnP0
c?n? N
M/M/C 无限源系统于是
Pn=
N
由 ∑ Pn=1 可得
n=0
C-1 N
∑ cn/n!ρnP0+ ∑ cc/c!ρnP0=1
n=0 n=c
c-1 P
0=[∑ cn/n!ρn+ (cc/c!)*((ρc-ρN+1)/(1-ρ))]-1
n=0
80
N
Lq=∑( n-c)Pn
n=c+1
=…
=(cc/c! ρc+1P0)/{ [1-(N-c+1) ρN-c
+(N-c) ρN-c+1]/(1-ρ)2}
M/M/C 无限源系统运行指标：
81
λe=λ(1-PN)
Wq=Lq/λe
W=Wq+1/μ
L=Wλe=Lq+λe/μ
2.M/M/C 等待系统 （ M/M/C/∞/∞）
此即上面的 M/M/C/N系统中,N->∞的情形
ρ=λ/(cμ)?1时,不收敛,设 ρ<1,
M/M/C 无限源系统
c-1
P0=[∑c n /n﹗ ρn+c c /c﹗ (ρc /1-ρ)]-1
n=0
82
(cn / n!)ρnP0 n<c
(cc/c!)ρnP0 n? c
M/M/C 无限源系统
Pn=
Lq = ccρc+1P0 / [c! (1-ρ)2]
λe =λ
Wq = Lq/λ
W = Wq+ 1/μ
L=λW= Lq+λ/μ
83
3.M/M/C 损失制系统 （ M/M/C/C/∞）
此即 M/M/C/N中 N=C 的情形
M/M/C 无限源系统
c
P0= [∑cn / n!ρn]-1
n=0
Pn= cn / n!ρnP0
λe=λ(1-Pc)
Lq=0,Wq=0(不等待 )
W=1/μ
L=λeW=λe/μ=(λ/μ) (1-Pc)
λ损 =λ-λe=λPc
84
例 6.1:某火车站售票处有三个窗口,
同时售各车次的车票 。 顾客到达服从泊松分布,平均每分钟到达 λ=0.9（ 人 ）,
服务时间服从负指数分布,平均服务率
μ=24（ 人 /h）,分两种情况：
1,顾客排成一队,依次购票；
2.顾客在每个窗口排一队,不准串队 。
求,（ 1） 售票处空闲的概率 。
（ 2） 平均等待时间和逗留时间 。
（ 3） 队长和队列长 。
例 题 解 析
85
例 题 解 析
稳态概率：
当 n<3时 Pn=[λ /（ nμ ） ]Pn-1=(λ n/n!)ρ nP0
=3n/n!ρ nP0
当 n?3时 Pn=[λ /（ cμ ） ]Pn-1=(33/3!)ρ nP0
=4.5ρ nP0
解,1,M/M/3/∞/∞
0 31 2
λ λ λ λ
μ 3μ2μ 3μ
4
λ
3μ
单位应相同：
μ=0.4（人 /分钟）
记 ρ= λ/（ 3μ）
ρ =0.9/(0.4*3)=0.75
86
例 题 解 析
∞
P0+3*0.75 P0+4.5*0.752 P0+∑4.5ρn P0 =1
n=3
∞
由 ∑ Pn=1
n=0
P0= 1/(1+2.25+2.53125+4.5ρ3/(1-ρ))
=1/13.375
=0.0748
P1=0.1683 P2=0.1893
∞ ∞
Lq=∑( n-c)Pn=33/3!ρ4 P0 ∑( n-3)ρn-3-1
n =c+1 n = 4
87
例 题 解 析
S= dF/ dρ=[(1-ρ)+ρ]/(1-ρ)2
于是：
Lq=4.5ρ 4P0/(1-ρ )2=1.704 λ e=λ
Wq=Lq/λ e=1.704/0.9=1.893分钟
∞ ∞
F=? S dρ=∑?(n-3)ρn-3-1dρ= ∑ ρn-3
n=4 n=4
=ρ/(1-ρ)
∞
S=∑ (n-3)ρn-3-1
n=4
88
例 题 解 析
Ws=Wq+ 1/μ =1.893+2.5=4.393分钟
Ls=λW s=3.954
故：
售票处的空闲的概率为 0.0748
平均等待时间 Wq=1.893分钟,
平均逗留时间 W=4.393分钟队长 Ls=3.954(人 ) Lq=1.704(人 )
89
2.M/M/1/∞/∞ 三个系统并联：
λ =0.3 μ =0.4 ρ =λ/μ =0.75
P0=1-ρ =0.25
三个服务台都有空的时候,
P03=0.0156
Ls=ρ /(1-ρ )=3 λ e=λ =0.3
Lq=Ls-λ /μ =2.25
Ws=Ls/λ =10
Wq=Ws-1/μ =7.5
例 题 解 析
90
故售票处空闲的概率为 0.0156
例 题 解 析平均等待时间 Wq=7.5分钟平均逗留时间 Ws=10分钟队长 Ls=3 三个队 共 3+3+3=9
队列长 Lq=2.25 共 6.75（ 人 ）
相比之下,排一队共享三个服务台效率好 。
91
顾客源有限的排队系统
1.M/M/1/m/m系统顾客源是 m个,那么系统容量实质上最多有 m个足够 。
0 m-11 2 m-2
mλ (m-1)λ 2λ λ
μ μμ μ
m
μ μ
(m-2)λ 3λ
顾客源中剩余的顾客数乘以每个顾客到达的概率
92
顾客源有限的排队系统
Pn={ [m-(n-1)]λ/μ}Pn-1 1?n?m
反复推得：
Pn=m!/(m-n)!(λ/μ)nP0 1?n?m
m
代入 ∑Pn=1
n=0m
∑m!/(m-n)!(λ/μ)nP0 =1
n=0
m
P0=[∑ m!/(m-n)!(λ/μ)n]-1
n=0
93
顾客源有限的排队系统 m
Pn=m!/(m-n)!(λ/μ)n[∑m!/(m-k)!(λ/μ)k]-1
k=0
由 λ(m-L)=μ(1-P0)
得 L=m-μ/λ(1-P0)
W=L/λe
Wq=W-1/μ
Lq=Wqλe
λe=λ(m-L)
m m
λe =∑ λnPn =λ ∑( m-n)Pn
n=0 n=0
m m
=λ (∑ m Pn-∑ n Pn)]
n=0 n=0
μe= μ(1-P0)
94
2,M/M/c/m/m系统顾客源有限的排队系统
0 m-11 2 m-2
mλ (m-1)λ 2λ λ
μ cμ2μ cμ
mCC-1
(m(c-1)λ
cμ
顾客源还有 m-(c-1)
个顾客每个顾客可到达的概率 λ
稳态概率方程
Pn=
[(m-n+1)λ/nμ]Pn-1 n?c
[(m-n+1)λ/cμ]Pn-1 c<n? m
95
m
代入 ∑Pn=1 得 (整理后 )
n=0
顾客源有限的排队系统反复代入得：
Pn=
m!/[n!(m-n)!](λ/μ )nP0 n?c
m!/[c!(m-n)!cn-c](λ/μ)nP0 c<n?m
c m
P0=[∑ m!/(m-n)!(λ/μ)n+∑ m!/(c!(m-n)!
n=0 n=c+1
cn-c)(λ/μ)n]-1
96
于是可得,
m
Lq=∑(n-c)Pn
n=c+1
λe=λ(m-L)
顾客源有限的排队系统又 L=Lq+λe/μ=Lq+λ/μ(m-L) 整理得：
L=(L+λ/μm)/(1+λ/μ)
Wq=Lq/λe,W=L/λe
97
应 用 举 例例 6.2:某汽车加油站有两台加油泵为汽车加油,加油站内最多能容纳 6辆汽车 。 已知顾客到达的时间间隔服从负指数分布,平均每小时到达 18辆汽车 。 若 加油站中已有 K辆车,当 K?2时,有 K/6的顾客将自动离去 。 加油时间服从负指数分布,
平均每辆车需要 5分钟 。 试求：
非标准的 M/M/2/N模型
98
应 用 举 例
（ 1）系统空闲的概率为多少？ P0
（ 2）求系统满的概率是多少？ P6
（ 3）求系统服务台不空的概率
P2+P3+P4+P5+P6=1- P0-P1
（ 4）若服务一个顾客,加油站可以获得利润 10元,问平均每小时可获得利润为多少元？ 10μe
（ 5）求每小时损失掉的顾客数？
λ损 =λ-λe
（ 6）加油站平均有多少辆车在等待加油？ Lq 平均有多少个车位被占用？ L
（ 7）进入加油站的顾客需要等多长的时间才能开始加油？ Wq 进入加油站的顾客需要多长时间才能离去？ W
99
稳态概率关系：
P1=λ/μP0=1.5P0 =(3/2)P0
P2=λ/(2μ)P1=0.75*1.5P0 =(9/8)P0
应 用 举 例解,状态转移速度图以小时为单位 λ=18 μ=60/5=12
λ
μ 2μ2μ 2μ2μ
0 51 2 4 63
2μ
(1-2/6)λ (1-3/6) λ (1-4/6) λλ (1-5/6) λ
应 用 举 例
P3=[(4/6)λ/(2μ)]P2=(1/2)(9/8)P0= (9/16)P
P4=[(3/6)λ/(3μ)]P3=(3/8)(9/16)P0= (27/128)P0
P5=[(2/6)λ/(2μ)]P4=(1/4)(27/512)P0 = (27/2048)P0
P6=[(1/6)λ/(2μ)]P5=(1/8)(27/512)P0= (27/4096)P0
由 P0=P1+P2+P3+P4+P5+P6=1
解得,P0=0.22433
P1 P2 P3 P4 P5 P6
0.33649 0.25237 0.12618 0.04732 0.01183 0.00148
101
运行指标：
(1) P0=0.22433
(2) P6=0.00148
(3) P忙 =1-P0-P1=0.43918
(4)μe=0P0+μP1+2μ(P2+P3+P4+P5+P6)
=14.578（ 辆 /h）
10μe= 145.78(元 /小时 ）
应 用 举 例
102
(5)λ 损 =λ -λ e
=18-14.5782
=3.4218（ 辆 /h）
应 用 举 例
(6) Lq=(3-2)P3+(4-2)P4+(5-2)P5+(6-2)P6
=0.26223
L=Lq+λ e/μ
=0.26223+1.21485
=1.47708
103
应 用 举 例
(7) Wq=Lq/λ e
=0.018h
=1.08分钟
W=Wq+1/μ
=0.101h
=6.08分钟
104
例 6.3:某车站候车室在某段时间旅客到达服从泊松流分布,平均速度为 50人 /h,每位旅客在候车室内停留的时间服从负指数分布,平均停留时间为 0.5h,问候车室内平均人数为多少？ （ L)
应 用 举 例解：把旅客停留在候车室看做服务,
于是系统为 M/M/∞/∞/∞
λ=50 μ=1/0.5=2
105
稳态概率关系：
Pn=λ/(nμ)Pn-1=…,=1/n!(λ/μ)nP0
记 ρ=λ/μ=50/2 =25
应 用 举 例
0 n1 2 n-1
λ λ λ λ
μ nμ2μ (n+1)μ
n+1
λ λ
3μ (n-1)μ
λ
(n+2)μ
状态转移速度图,
106
应 用 举 例
∞
P0=(∑1/n!ρn)-1= e-ρ
n=0
∞
L=∑nPn
n=1 ∞
= e-ρ∑1/(n-1)!ρn
n=1 ∞
=ρe-ρ∑1/n!ρn=ρ=25(人 )
n=0
∞
代入 ∑Pn=1
n=0
107
其他模型选介
M/G/1排队系统设顾客单位时间到达数为?，服务时间为随机变量 V，且 E(V) = 1 /
D(V) =?2
那么，服务强度，当? < 1时
P0 = 1 -?
根据波拉切克 -欣钦 （ Pollaczek-Khinchine） 公式可导出
Lq = (?2+) / [2(1-?)]
其它量的计算同前。
108
其他模型选介
M/D/1排队系统设顾客单位时间到达数为?，服务时间为一个常数 v，则 E( v ) = v = 1 /?
D( v ) = 0
那么，服务强度，当? < 1时
P0 = 1 -?
根据上一模型的公式可直接得到
Lq =?2 / [2(1-?)]
其它量的计算同前。
109
4.排队系统的优化目标与最优化问题以完全消除排队现象为研究目标是不现实的,那会造成服务人员和设施的严重浪费,但是设施的不足和低水平的服务,又将引起太多的等待,从而导致生产和社会性损失 。 从经济角度考虑,
排队系统的费用应该包含以下两个方面：
一个是服务费用,它是服务水平的递增函数；另一个是顾客等待的机会损失
(费用 ),它是服务水平的递减函数 。 两者的总和呈一条 U形曲线 。
110
4.排队系统的优化目标与最优化问题系统最优化的目标就是寻求上述合成费用曲线的最小点 。 在这种意义下,
排队系统的最优化问题通常分为两类：
一类称之系统的静态最优设计,目的在于使设备达到最大效益,或者说,在保证一定服务质量指标的前题下,要求机构最为经济；另一类叫作系统动态最优运营,是指一个给定排队系统,如何运营可使某个目标函数得到最优 。 归纳起来,排队系统常见的优化问题在于：
111
4.排队系统的优化目标与最优化问题
(1)确定最优服务率?*；
(2)确定最佳服务台数量 c*；
(3)选择最为合适的服务规则；
(4)或是确定上述几个量的最优组合 。
研究排队系统的根本目的在于以最少的设备得到最大的效益,或者说,在一定的服务质量的指标下要求机构最为经济 。 排队系统的最优化问题分为两大类：
112
4.排队系统的优化目标与最优化问题系统的静态最优设计问题和系统的动态最优控制问题 。 由于系统动态最优控制问题涉及更多的数学知识,
因此,本章只讨论系统静态的最优设计问题 。 这类问题一般可以借助于前面所得到的一些表达式来解决 。
本节仅就?,c 这两个决策变量的分别单独优化,介绍两个较简单的模型,以便读者了解排队系统优化设计的基本思想 。
113
4.排队系统的优化目标与最优化问题一,M／ M／ 1／ ∞ 系统的最优平均服务率?*
设
C1—— 当?=1时服务系统单位时间的平均费
CW—— 平均每个顾客在系统逗留单位时间的损失；
y—— 整个系统单位时间的平均总费用 。
其中 C1,C2 均为可知 (下同 )。 则目标函数为
(6-52)Lccy
w1
114
4.排队系统的优化目标与最优化问题将 L=?／ (? -?),代入上式,得易见 y是关于决策变量?的一元非线性函数由一阶条件解得驻点
(6-53)
11 wccy
0
)(
1
21 wccd
dy
1* / cc w
115
4.排队系统的优化目标与最优化问题根号前取正号是为了保证?<1,即
*>?,这样,系统才能达到稳态 。 又由二阶条件
(因?>? ）
可知 (6-53)给出的?*为 (?,∞) 上的全局唯一最小点 。 将?*代入 (6-52)中,可得最小总平均费用
0)( 2 32
2
wcd yd
wcccy 11* 2 （ 6-54）
116
4.排队系统的优化目标与最优化问题另外,若设 cw为平均每个顾客在队列中等待单位时间的损失,则需用式 (6-26)给出的 取代式 (6-52)中的,这时类似可得一阶条件：
这是一个关于?的四次方程,尽管它有求根公式,但由于形式太复杂,实际并不应用 。 一般采用数值法 (如牛顿法 )确定其根?*。
)(
2
qL
022 322213141 ww ccccc
117
4.排队系统的优化目标与最优化问题二,M／ M／ s／ ∞ 系统的最优服务台数 s*
设目标函数为
(6-55)
其中：
s—— 并联服务台的个数 (待定 )；
f(s)—— 整个系统单位时间的平均总费用,它是关于服务台数 s的函数；
c2—— 单位时间内平均每个服务台的费用；
)()( 2 sLcscsf w
118
4.排队系统的优化目标与最优化问题
cw—— 平均每个顾客在系统中逗留 (或等待 )单位时间的损失；
L(s)—— 平均队长 (或平均等待队长 ),它是关于服务台数 s的函数；
我们要确定最优服务台数 s*∈ {1,2,… }，
使由于 s取值离散,不能采用微分法或非线性规划的方法,因此我们采用差分法 。 显然有
（ 6-56）
)()(m in)( 2* sLcscsfsf w
)1()(
)1()(
**
**
sfsf
sfsf
119
4.排队系统的优化目标与最优化问题把式 （ 6-55） 代人式 (6-56) 中,得由此可得令
(6-57)
依次计算 s=1,2,… 时的 L(s)值及每一差值 L(s)-L(s+1),根据?落在哪两个差值之间就可确定 s*。
)1()1()(
)1()1()(
**
2
**
2
**
2
**
2
sLcscsLcsc
sLcscsLcsc
ww
ww
)()1()1()( **2** sLsLccsLsL
w
wc
c 2
120
例 6.4:兴建一座港口码头,只有一个装卸船只的泊位 。 要求设计装卸能力 。
装卸能力单位为 （ 只 /日 ） 船数 。 已知：
单位装卸能力的平均生产费用 a=2千元,
船只逗留每日损失 b=1.5千元 。 船只到达服从泊松分布,平均速率 λ=3只 /日 。 船只装卸时间服从负指数分布 。 目标是每日总支出最少 。
应 用 举 例解,λ=3 μ待定 模型 M/M/1/∞/∞
队长 Ls =λ/(μ-λ)
总费用 C=aμ+bLs=aμ+bλ/(μ-λ)
求极值 （ 最小值 ）
应 用 举 例求导 dc/du=a+(-bλ )/(μ -λ )2 = 0
得,μ -λ =+ - (bλ/a )1/2（ 根据题意舍负 ）
所以 μ=λ+(bλ/a)1/2=3+(2.25)1/2=4.5(只 /日 )
122
例 6.4,建造一口码头,要求设计装卸船只的泊位数 。 已知,预计到达
λ=3只 /天,泊松流；装卸 μ=2只 /天,
负指数分布 。 装卸费每泊位每天 a=2
千元,停留损失费 b=1.5千元 /日 。 目标是总费用最少 。
应 用 举 例
解,模型 M/M/c/∞/∞ c待定
总费用,F=ac+bLs（ c） 离散,无法用求导来解 。
123
应 用 举 例考虑,M/M/c/∞/∞
要求,ρ=λ/(cμ) <1 即 c>(λ/μ)=1.5
讨论 c=2,3,4…
c-1
P0=[∑cn/n﹗ ρn+cc/c!ρc/(1- ρ)]-1
n=0
Lq= ccρc+1/c!(1-ρ)2 P0
L=Lq+λ/μ
124
应 用 举 例结论,c=3 即设计三个装卸泊位可使每天的总费用最少为 8.60526千元 。
M /M/ 2/? /? M /M/ 3/? /? M /M/ 4/? /?
P
0
1/7=0.142 86 4/19=0.21 053 40/181=0,22099
Lq 27/14=1.9 2857 9/83=0.23 684 81/1810=0,04475
Ls 24/7=3.42 857 33/19=1.7 3684 1398/905= 1.5447 5
F 64/7=9.14 286 327/38=8,60526 9337/905= 10.317 13
ρ =1/2ρ =3/4 ρ =3/8
125
4.排队系统的优化目标与最优化问题例 6.6:某市政府的上访接待室每天平均接待来访 48次,来访者为泊松流,每天上访所造成的损失为平均每次 20元 。 该室每设置一名接待员的服务成本为平均每天 8
元,接待时间为指数分布,平均每天可接待 25次 。 问应设置几名接待员能使平均总费用为最小?
解,由题意知,这是一个 M／ M／ s／ ∞
系统,有
126
4.排队系统的优化目标与最优化问题
c2＝ 8元／人天,cw＝ 20元／天次,?＝ 48
次／天,?＝ 25次／天,
则按式 (6-57)得
＝ 0.4
另有
20
8
92.12548
s
s
ssss
92.192.111,92.1
127
4.排队系统的优化目标与最优化问题把 代入式 (6-15),得又由式 (6-17),式 (6-18) 得把,P0代入上式,整理可得
1,,
11
0
0 )92.1()!1(
)92.1(
!
)92.1(
s
k
sk
sskP
02)1(! PsL
s
1,,
128
4.排队系统的优化目标与最优化问题而当 S=1时,?=?=1.92＞ 1,不满足系统达到稳态的条件?＜ 1,故这时 L(1)=∞ 。
依次计算当 s＝ 2,3,… 时的值及其差值
L(s)-L(s+1)上,如表 6-3所示 。
由表 6-3及所落位置,对应可知：
S*＝ 4(人 )
92.1
)92.1(
!
)92.1()92.1()!1()92.1(
)92.1()(
1
0
1
s
k
s
k
s
k
sss
sL
,3,2?s
129
据此按 (6-55)式可得最小总平均费用：
(元／天 )
故该室应设置 4名接待员可使每天总平均费用达到最小,为 73,26元 。
表 6-3 s＝ 2,3,… 时的 L(s)值及其差值上 L(s)-L(s+1)
(下页）
4.排队系统的优化目标与最优化问题
26.730 6 3.22048)4( *sf
130
4.排队系统的优化目标与最优化问题
)(sL?
)1()( sLsL?
S 1 2 3 4 5 …
24.
490
2.64
5
2.06
3
1.9
52
…
21.8
45
0.58
2
0.11
1
…
4.0
2
第六章 排队论基本概念输入过程和服务时间分布泊松输入 ——指数服务排队模型其他模型选介排队系统的优化目标与最优化问题本章内容重点
3
排队论 (Queuing Theory)，
又称随机服务系统理论 (Random
Service System Theory),是一门研究拥挤现象 (排队,等待 )的科学 。 具体地说,它是在研究各种排队系统概率规律性的基础上,
解决相应排队系统的最优设计和最优控制问题 。
前 言
4
排队是我们在日常生活和生产中经常遇到的现象 。 例如,上,下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象 。 除了上述有形的排队之外,
还有大量的所谓,无形,排队现象,如几个顾客打电话到出租汽车站要求派车,如果出租汽车站无足够车辆,则部分顾客只得在各自的要车处等待,他们分散在不同地方,却形成了一个无形队列在等待派车 。 排队的不一定是人,
也可以是物：
前 言
5
例如,通讯卫星与地面若干待传递的信息；生产线上的原料,
半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等 。
前 言
6
显然,上述各种问题虽互不相同,
但却都有要求得到某种服务的人或物和提供服务的人或机构 。 排队论里把要求服务的对象统称为,顾客,,而把提供服务的人或机构称为,服务台,或,服务员,。 不同的顾客与服务组成了各式各样的服务系统 。 顾客为了得到某种服务而到达系统,若不能立即获得服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统,见图 6-1至图 6-5。
前 言
7
不同的顾客与服务组成了各式各样的服务系统 。 顾客为了得到某种服务而到达系统,若不能立即获得服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统,见图 6-1至图 6-5。
图 6-1 单服务台排队系统前 言
8
图 6-2 单队列 —— S个服务台并联的排队系统图 6-3 S个队列 —— S个服务台的并联排队系统前 言
9
图 6-4 单队 —— 多个服务台的串联排队系统图 6-5 多队 —— 多服务台混联、网络系统前 言
10
图 6-6 随机服务系统前 言一般的排队系统,都可由下面图 6-6加以描述 。
11
通常称由图 6-6表示的系统为一随机聚散服务系统,任一排队系统都是一个随机聚散服务系统 。 这里,,聚,表示顾客的到达,,散,表示顾客的离去 。 所谓随机性则是排队系统的一个普遍特点,是指顾客的到达情况 (如相继到达时间间隔 )与每个顾客接受服务的时间往往是事先无法确切知道的,或者说是随机的 。 一般来说,
排队论所研究的排队系统中,顾客到来的时刻和服务台提供服务的时间长短都是随机的,因此这样的服务系统被称为随机服务系统 。
前 言
12
面对拥挤现象,人们总是希望尽量设法减少排队,通常的做法是增加服务设施 。
但是增加的数量越多,人力,物力的支出就越大,甚至会出现空闲浪费,如果服务设施太少,顾客排队等待的时间就会很长,
这样对顾客会带来不良影响 。 于是,顾客排队时间的长短与服务设施规模的大小,
就构成了设计随机服务系统中的一对矛盾 。
如何做到既保证一定的服务质量指标,又使服务设施费用经济合理,恰当地解决顾客排队时间与服务设施费用大小这对矛盾,
这就是随机服务系统理论 —— 排队论所要研究解决的问题 。
前 言
13
排队论是 1909年由丹麦工程师爱尔朗 (A.K,Erlang)在研究电活系统时创立的,几十年来排队论的应用领域越来越广泛,理论也日渐完善 。 特别是自二十世纪 60年代以来,
由于计算机的飞速发展,更为排队论的应用开拓了宽阔的前景 。
前 言
14
1.基 本 概 念一 排队系统的描述
（一）系统特征和基本排队过程实际的排队系统虽然千差万别，但是它们有以下的共同特征：
(1)有请求服务的人或物 —— 顾客 ；
(2)有为顾客服务的人或物，即服务员或服务台 ；
(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个 排队系统的状态也是随机的 。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员 (台 )又空闲无事。
15
任何一个排队问题的基本排队过程都可以用图 6-6表示 。 从图 6-6
可知,每个顾客由顾客源按一定方式到达服务系统,首先加入队列排队等待接受服务,然后服务台按一定规则从队列中选择顾客进行服务,
获得服务的顾客立即离开 。
1.基 本 概 念
16
（ 二 ） 排队系统的基本组成部分通常,排队系统都有输入过程,服务规则和服务台等 3个组成部分：
1,输入过程,这是指要求服务的顾客是按怎样的规律到达排队系统的过程,有时也把它称为顾客流,一般可以从 3个方面来描述 — 个输入过程 。
(1)顾客总体数,又称顾客源,输入源 。 这是指顾客的来源 。 顾客源可以是有限的,也可以是无限的 。 例如,到售票处购票的顾客总数可以认为是无限的,而某个工厂因故障待修的机床则是有限的 。
1.基 本 概 念
17
(2)顾客到达方式 。 这是描述顾客是怎样来到系统的,他们是单个到达,还是成批到达 。
病人到医院看病是顾客单个到达的例子 。 在库存问题中如将生产器材进货或产品入库看作是顾客,那么这种顾客则是成批到达的 。
(3)顾客流的概率分布,或称 相继顾客到达的时间间隔的分布 。 这是求解排队系统有关运行指标问题时,首先需要确定的指标 。 这也可以理解为在一定的时间间隔内到达 K个顾客
(K=1,2,? )的概率是多大 。 顾客流的概率分布一般有定长分布,二项分布,泊松流 (最简单流 ),爱尔朗分布等若干种 。
1.基 本 概 念
18
2.服务规则 。 这是指服务台从队列中选取顾客进行服务的顺序 。 一般可以分为损失制,
等待制和混合制等 3大类 。
(1)损失制 。 这是指如果顾客到达排队系统时,所有服务台都已被先来的顾客占用,那么他们就自动离开系统永不再来 。 典型例子是,
如电话拔号后出现忙音,顾客不愿等待而自动挂断电话,如要再打,就需重新拔号,这种服务规则即为损失制 。
1.基 本 概 念
19
(2)等待制 。 这是指当顾客来到系统时,所有服务台都不空,顾客加入排队行列等待服务 。 例如,排队等待售票,
故障设备等待维修等 。 等待制中,服务台在选择顾客进行服务时,常有如下四种规则：
① 先到先服务 。 按顾客到达的先后顺序对顾客进行服务,这是最普遍的情形 。
② 后到先服务 。 仓库中迭放的钢材,
后迭放上去的都先被领走,就属于这种情况 。
1.基 本 概 念
20
③ 随机服务 。 即当服务台空闲时,
不按照排队序列而随意指定某个顾客去接受服务,如电话交换台接通呼叫电话就是一例 。
④ 优先权服务 。 如老人,儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等,均属于此种服务规则 。
1.基 本 概 念
21
(3)混合制,这是等待制与损失制相结合的一种服务规则,一般是指允许排队,
但又不允许队列无限长下去 。 具体说来,
大致有三种：
① 队长有限 。 当排队等待服务的顾客人数超过规定数量时,后来的顾客就自动离去,另求服务,即系统的等待空间是有限的 。 例如最多只能容纳 K个顾客在系统中,当新顾客到达时,若系统中的顾客数 (又称为队长 )小于 K,则可进入系统排队或接受服务；否则,便离开系统,并不再回来 。 如水库的库容是有限的,旅馆的床位是有限的 。
1.基 本 概 念
22
② 等待时间有限 。 即顾客在系统中的等待时间不超过某一给定的长度 T，
当等待时间超过 T时,顾客将自动离去,
并不再回来 。 如易损坏的电子元器件的库存问题,超过一定存储时间的元器件被自动认为失效 。 又如顾客到饭馆就餐,
等了一定时间后不愿再等而自动离去另找饭店用餐 。
1.基 本 概 念
23
③ 逗留时间 (等待时间与服务时间之和 )有限 。 例如用高射炮射击敌机,
当敌机飞越高射炮射击有效区域的时间为 t时,若在这个时间内未被击落,也就不可能再被击落了 。
不难注意到,损失制和等待制可看成是混合制的特殊情形，如记 s为系统中服务台的个数，则当 K=s时，混合制即成为损失制；当 K=∞ 时，混合制即成为等待制。
1.基 本 概 念
24
3,服务台情况 。 服务台可以从以下 3方面来描述：
(1) 服务台数量及构成形式 。从数量上说，
服务台有单服务台和多服务台之分。从构成形式上看，服务台有：
①单队 —— 单服务台式；
②单队 —— 多服务台并联式；
③多队 —— 多服务台并联式；
④单队 —— 多服务台串联式；
⑤单队 —— 多服务台并串联混合式,以及多队 —— 多服务台并串联混合式等等。
见前面图 6-1至图 6-5所示。
1.基 本 概 念
25
(2) 服务方式 。 这是指在某一时刻接受服务的顾客数,它有单个服务和成批服务两种 。 如公共汽车一次就可装载一批乘客就属于成批服务 。
(3) 服务时间的分布 。 一般来说,
在多数情况下,对每一个顾客的服务时间是一随机变量,其概率分布有定长分布,负指数分布,K级爱尔良分布,一般分布 (所有顾客的服务时间都是独立同分布的 )等等 。
1.基 本 概 念
26
（ 三 ） 排队系统的描述符号与分类为了区别各种排队系统,根据输入过程,排队规则和服务机制的变化对排队模型进行描述或分类,可给出很多排队模型 。 为了方便对众多模型的描述,
肯道尔 （ D,G,Kendall） 提出了一种目 前 在 排 队 论 中 被 广 泛 采 用 的
,Kendall记号,,完整的表达方式通常用到 6个符号并取如下固定格式：
A/B/C/D/E/F
各符号的意义为：
1.基 本 概 念
27
A— 表示顾客相继到达间隔时间分布,常用下列符号：
M—— 表示到达过程为泊松过程或负指数分布；
D—— 表示定长输入；
Ek—— 表示 k阶爱尔朗分布；
G—— 表示一般相互独立的随机分布 。
B— 表示服务时间分布,所用符号与表示顾客到达间隔时间分布相同 。
M—— 表示服务过程为泊松过程或负指数分布；
D—— 表示定长分布；
Ek —— 表示 k阶爱尔朗分布；
G—— 表示一般相互独立的随机分布 。
1.基 本 概 念
28
C— 表示服务台 (员 )个数：,1”则表示单个服务台,,s”。 (s＞ 1)表示多个服务台 。
D— 表示系统中顾客容量限额,或称等待空间容量； 如系统有 K个等待位子,则 0<K<∞,
当 K=0 时,说明系统不允许等待,即为损失制 。 K=∞ 时为等待制系统,此时 ∞ 般省略不写 。 K为有限整数时,表示为混合制系统 。
E— 表示顾客源限额,分有限与无限两种,∞
表示顾客源无限,此时一般 ∞ 也可省略不写 。
1.基 本 概 念
29
F— 表示服务规则,常用下列符号：
FCFS：表示先到先服务的排队规则；
LCFS：表示后到先服务的排队规则；
PR：表示优先权服务的排队规则 。
例如：某排队问题为 M／ M／ S／ ∞ ／ ∞ ／ FCFS／,
则表示顾客到达间隔时间为负指数分布 (泊松流 )；
服务时间为负指数分布；有 s(s＞ 1)个服务台；系统等待空间容量无限 (等待制 )；顾客源无限,采用先到先服务规则 。
某些情况下,排队问题仅用上述表达形式中的前 3个,4个,5个符号 。 如不特别说明则均理解为系统等待空间容量无限；顾客源无限,先到先服务,单个服务的等待制系统 。
1.基 本 概 念
30
二,排队系统的主要数量指标研究排队系统的目的是通过了解系统运行的状况,对系统进行调整和控制,使系统处于最优运行状态 。 因此,首先需要弄清系统的运行状况 。 描述一个排队系统运行状况的主要数量指标有：
1.基 本 概 念
31
1.队长和排队长 （ 队列长 ）
队长 是指系统中的平均顾客数 (排队等待的顾客数与正在接受服务的顾客数之和 )，
排队长 是指系统中正在排队等待服务的平均顾客数 。
队长和排队长一般都是随机变量 。
我们希望能确定它们的分布,或至少能确定它们的平均值 (即平均队长和平均排队长 )及有关的矩 (如方差等 )。 队长的分布是顾客和服务员都关心的,特别是对系统设计人员来说,如果能知道队长的分布,
就能确定队长超过某个数的概率,从而确定合理的等待空间 。
1.基 本 概 念
32
2,等待时间和逗留时间从顾客到达时刻起到他开始接受服务止这段时间称为 等待时间,是随机变量,也是顾客最关心的指标,因为顾客通常希望等待时间越短越好 。 从顾客到达时刻起到他接受服务完成止这段时间称为 逗留时间,也是随机变量,同样为顾客非常关心 。 对这两个指标的研究当然是希望能确定它们的分布,或至少能知道顾客的平均等待时间和平均逗留时间 。
1.基 本 概 念
33
3,忙期和闲期忙期 是指从顾客到达空闲着的服务机构起,到服务机构再次成为空闲止的这段时间,即服务机构连续忙的时间 。 这是个随机变量,是服务员最为关心的指标,因为它关系到服务员的服务强度 。 与忙期相对的是 闲期,即服务机构连续保持空闲的时间 。 在排队系统中,忙期和闲期总是交替出现的 。
除了上述几个基本数量指标外,还会用到其他一些重要的指标,如在损失制或系统容量有限的情况下,由于顾客被拒绝,
而使服务系统受到损失的顾客损失率及服务强度等,也都是十分重要的数量指标 。
1.基 本 概 念
34
4.一些数量指标的常用记号
(1)主要数量指标
N(t)：时刻 t系统中的顾客数 (又称为系统的状态 ),即队长；
Nq(t)：时刻 t系统中排队的顾客数,
即排队长；
T(t)：时刻 t到达系统的顾客在系统中的逗留时间；
Tq(t)：时刻 t到达系统的顾客在系统中的等待时间 。
1.基 本 概 念
35
上面给出的这些数量指标一般都是和系统运行的时间有关的随机变量,求这些随机变量的瞬时分布一般是很困难的 。 为了分析上的简便,并注意到相当一部分排队系统在运行了一定时间后,都会趋于一个平衡状态 (或称平稳状态 )。 在平衡状态下,队长的分布,等待时间的分布和忙期的分布都和系统所处的时刻无关,而且系统的初始状态的影响也会消失 。 因此,我们 在本章中将主要讨论与系统所处时刻无关的性质,即统计平衡性质 。
1.基 本 概 念
36
L或 Ls—— 平均队长,即稳态系统任一时刻的所有顾客数的期望值；
Lq—— 平均等待队长或队列长,即稳态系统任一时刻的等待服务的顾客数的期望值；
W或 Ws—— 平均逗留时间,即 (在任意时刻 )进入稳态系统的顾客逗留时间的期望值；
Wq—— 平均等待时间,即 (在任意时刻 )进入稳态系统的顾客等待时间的期望值 。
这四项主要性能指标 (又称主要工作指标 )的值越小,说明系统排队越少,等待时间越少,因而系统性能越好 。 显然,
它们是顾客与服务系统的管理者都很关注的 。
1.基 本 概 念
37
(2)其他常用数量指标
s—— 系统中并联服务台的数目；
( 或? )—— 平均到达率；
1/?( 或 1/? )—— 平均到达间隔 。
( 或? )—— 平均服务率；
1/?( 或 1/? )—— 平均服务时间 。
—— 服务强度,即每个服务台单位时间内的平均服务时间；一般有?=?/(s?) ；
N—— 稳态系统任一时刻的状态 (即系统中所有顾客数 )；
U—— 任一顾客在稳态系统中的逗留时间；
1.基 本 概 念
38
Q—— 任一顾客在稳态系统中的等待时间 。
N,U,Q都是随机变量 。
Pn=P{N=n},稳态系统任一时刻状态为 n的概率；特别当 n=0时,Pn即 P0,而
P0即稳态系统所有服务台全部空闲 (因系统中顾客数为 0)的概率 。
对于损失制和混合制的排队系统,顾客在到达服务系统时,若系统容量已满,
则自行消失 。 这就是说,到达的顾客不一定全部进入系统,为此引入：
1.基 本 概 念
39
e( 或?e )—— 有效平均到达率,即每单位时间内进入系统的平均顾客数 （ 期望值 ） ； 这时?就是期望每单位时间内来到系统 (包括未进入系统 )的平均顾客数
（ 期望值 ）
对于等待制的排队系统,有?e=? 。
在系统达到稳态时,假定平均到达率为常数?,则 有 下 面 的 李 特 尔 (John
D,C,Little)公式：
1.基 本 概 念
WL e
qeq WL
(6-1a)
(6-1b)
40
又假定平均服务时间为常数 1／?,则有
(6-1c)
(6-ld)
因此,只要知道 L,Lq,W,Wq四者之一,则其余三者就可由 (6— 1)式求得 。 另外还有
1.基 本 概 念
1
qWW
e
qLL
0n
nnPL (6-2)
41
(6-3)
因此,只要知道 Pn(n=0,1,2… ),则 L
或 Lq就可由 (6-2)或 (6-3)式求得,从而再由 (6-1)式就能求得四项主要工作指标 。
1.基 本 概 念
sn n
msnq nPPsnL
0
)(
42
一,输入过程由前所述,输入过程是描述各种类型的顾客以怎样的规律到达系统,一般用相继两顾客到达时间间隔?来描述系统输入特征 。 主要输入过程有：
1,定长输入 。 这是指顾客有规则地等距到达,每隔时间?到达一个顾客 。 这时相继顾客到达间隔?的分布函数 F(t)为：
2.输入过程和服务时间分布
t
ttPtF
,0
,1}{)( (6-4)
例如,生产自动线上产品从传送带上进入包装箱就是这种情况,
43
2,泊松 (poisson)输入,又称最简单流 。
满足下面 3个条件的输入称之为最简单流 。
(1) 平稳性 。 又称作输入过程是平稳的,
指在长度为 t的时段内恰好到达 k个顾客的概率仅与时段长度有关,而与时段起点无关 。
即对任意?∈ (0,∞),在 (?,?+t]或 (0,t)内恰好到达 k个顾客的概率相等：
设初始条件为,且有 。
)(})({})0()({})()({ tVktPktPkataP k
0
1
K
KV1)0(0?V
2.输入过程和服务时间分布
44
(2)无后效性 。 指在任意几个不相交的时间区间内,各自到达的顾客数是相互独立的 。 通俗地说就是以前到达的顾客情况,
对以后顾客的到来没有影响 。 否则就是关联的 。
(3)单个性又称普通性 。 指在充分小的时段内最多到达一个顾客 。 因为泊松流实际应用最广,也最容易处理,因而研究得也较多,可以证明,对于泊松流,在长度为 t的时间内到达 K个顾客的概率 vk(t)服从泊松分布,即
2.输入过程和服务时间分布
45
其中参数?>0为一常数,表示单位时间内到达顾客的平均数,又称为顾客的平均到达率 。
对于泊松流,不难证明其相继顾客到达时间间隔?i,i=1,2,… 是相互独立同分布的,其分布函数为负指数分布：
（ 6-6）
!
)()(
K
tetV Kt
k
,2,1,0?K （ 6-5）
0,0
0,1)(
t
tetF t
i
),2,1(i
2.输入过程和服务时间分布
46
3.爱尔朗输入,这是指相继顾客到达时间间隔?相互独立,具有相同的分布,其分布密度为
（ 6-7）
其中 k为非负整数 。
可以证明,在参数为?的泊松输人中,对任意的
j与 k,设第 j与第 j+k个顾客之间的到达间隔为 。 则随机变量 Tk的分布必遵从参数为?的爱尔朗分布,其分布密度为：
0)!1( )()(
1
teK tta t
K
)( 21 kkk TT
2.输入过程和服务时间分布
47
例某排队系统有并联的 k个服务台,顾客流为泊松流,规定第 i,K+i,2K+i…个顾客排入第 i号台 (i=1,2,…,K),则第 K台所获得的顾客流,即为爱尔朗输入流,其他各台,从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流 。
此外,爱尔朗分布中,当 K＝ 1时将化为负指数分布 。
0)!1( )()(
1
teK tta t
K
2.输入过程和服务时间分布
48
4.一般独立输入,即相继顾客到达时间间隔相互独立,同分布,分布函数
F(t)是任意分布,因此,上面所述的所有输入都是一般独立分布的特例 。
5.成批到达的输入 。 这时排队系统每次到达的顾客不一定是一个,而可能是一批,每批顾客的数目 n是一个随机变量 。 其分布为：
到达时间间隔可能是上述几类输入中的一种 。
2.输入过程和服务时间分布
（ 6-8）
kaknP }{?,2,1,0?K
49
二,服务时间分布
1,定长分布 。 每一个顾客的服务时间 都是常数?,此时服务时间 t的分布函数 为：
（ 6-9）
2,负指数分布 。 即各个顾客的服务时间相互独立,具有相同的负指数分布：
(6-10)
其中?>0为一常数，服务时间 t的数学期望称为平均服务时间。显然，对于负指数分布
2.输入过程和服务时间分布
x
xxtPxB
0
1)()(
0,0
0,1)(
x
xexB x?
50
3.爱尔朗分布,即每个顾客的服务时间相互独立,具有相同的爱尔朗分布 。 其密度函数为其中?>0为一常数,此种的平均服务时间为：
K=1时爱尔朗分布化归为负指数分布当 K→∞
时,得到长度为 1/?的定长服务 。
2.输入过程和服务时间分布
0 0 1)()( dxxexx d BtE mx(6-11)
(6-12) 0,
)!1(
)()( 1?
xek xkkxb xk
k
0 1)()(?dxxxbtE (6-13)
51
4.一般服务分布 。 所有顾客的服务时间都是相互独立具有相同分布的随机变量,其分布函数记 B(X),前面所述的各种服务分布都是一般服务分布的特例 。
5.多个服务台的服务分布 。 可以假定各个服务台的服务分布参数不同或分布类型不同 。
6.服务时间依赖于队长的情况 。 指服务员排队的人愈多,服务的速度也就愈快 。
2.输入过程和服务时间分布
52
三,排队论研究的基本问题排队论研究的首要问题是排队系统主要数量指标的概率规律,即研究系统的整体性质,然后进一步研究系统的优化问题 。 与这两个问题相关的还包括排队系统的统计推断问题 。
(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征,
了解系统运行的基本特征 。
(2)统计推断问题,建立适当的排队模型是排队论研究的第一步,建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等 。
2.输入过程和服务时间分布
53
(3)系统优化问题,又称为系统控制问题或系统运营问题,其基本目的是使系统处于最优或最合理的状态 。 系统优化问题包括最优设计问题和最优运营问题,其内容很多,
有最少费用问题,服务率的控制问题,服务台的开关策略,顾客 (或服务 )根据优先权的最优排序等方面的问题 。
对于一般的排队系统运行情况的分析,
通常是在给定输入与服务条件下,通过求解系统状态为 n(有 n个顾客 )的概率 Pn(t),再进行计算其主要的运行指标,
2.输入过程和服务时间分布
54
① 系统中顾客数 (队长 )的期望值 L或 Ls；
② 排队等待的顾客数 (排队长 )的期望值 Lq；
③ 顾客在系统中全部时间 (逗留时间 )的期望值 W或 Ws；
④ 顾客排队等待时间的期望值 Wq。
排队系统中,由于顾客到达分布和服务时间分布是多种多样的,加之服务台数 。 顾客源有限无限,排队容量有限无限等的不同组合,
就会有不胜枚举的不同排队模型,若对所有排队模型都进行分析与计算,不但十分繁杂而且也没有必要 。 下面拟分析几种常见排队系统模型 。
2.输入过程和服务时间分布
55
对于泊松输入 — 负指数分布服务的排队系统的一般决策过程：
① 根据已知条件绘制状态转移速度图。
② 依据状态转移速度图写出各稳态概率之间的关系。
③ 求出 P0 及 Pn 。
3.泊松输入 — 指数服务排队模型
56
④ 计算各项数量运行指标。
⑤ 用系统运行指标构造目标函数，对系统进行优化。
典型分布 —— 泊松分布及其性质，负指数分布及其性质泊松分布 (平稳状态）? > 0 为单位时间平均到达的顾客数
P{ I = n }=?n e-? / n!
(n=0,1,2,… )
3.泊松输入 — 指数服务排队模型
57
负指数分布? 为平均服务率，即单位时间服务的顾客数。
P（服务时间 ≤ t ) = 1- e-? t t ≥ 0
系统状态概率分布及状态转移速度图 —— 基本的概率分布推导
3.泊松输入 — 指数服务排队模型
58
系统状态概率分布：
λ n：系统状态为 n时,顾客进入系统的平均速度 。
μ n：系统状态为 n时,顾客离开系统的平均速度 。
Pn(t):t时刻,系统内有几个顾客的概率 。
(t,t+Δ t)有一个顾客到达概率 λ nΔ t，
无顾客到达的概率 1-λ nΔ t（ 近似 ）
3.泊松输入 — 指数服务排队模型各种方式发生概率表3.泊松输入 — 指数服务排队模型
60
Pn(t+Δ t)=Pn(t)(1-λ nΔ t)(1-μ nΔ t)
+Pn-1(t)λ n-1Δ t(1-μ n-1Δ t)+Pn+1(t)(1-
λ n+1Δ t)μ n+1Δ t+Pn(t)λ nΔ tμ nΔ t
(dPn(t)/dt)=limΔt -0(Pn(t+Δ t)-Pn(t)/Δ t)
(Δ t2 项 都 变 为 零 )=Pn-1(t)λ n-1-
Pn(t)(λ n+μ n)+Pn-1(t)μ n-1
3.泊松输入 — 指数服务排队模型方式 1,2,3,4互不相容且完备，于是：
61
当 n=0时,只有方式 1和 3,4发生,且方式 1中无离去的概率为 1,则
dP0(t)/dt=-P0(t)λ 0+P1(t)μ 1
我们假设系统是稳态的,即与时刻无关,于是可得,dPn(t)/dt=0； -λ 0P0+μ 1P1=0
λn -1Pn-1-(μ n+λ n)Pn+μ n+1Pn+1=0
n=1,2,3……
λ 0P0=μ 1P1,P1=λ 0/μ 1P0
λ 0P0-(λ 1+μ 1)P1+μ 2P2=0
μ 1 P1-(λ 1+μ 1)P1+μ 2P2=0
P2=(λ 1/μ 2)P1=(λ 0λ 1/μ 1μ 2)P0
Pn=(λ n-1/μ n)Pn-1=(∏ i=0n-1λ i/∏ j=1nuj)p0
3.泊松输入 — 指数服务排队模型
62
λ 0P0-(λ 1+μ 1)P1+μ 2P2=0
μ 1 P1-(λ 1+μ 1)P1+μ 2P2=0
P2=(λ 1/μ 2)P1=(λ 0λ 1/μ 1μ 2)P0
n-1 nP
n=(λ n-1/μ n)Pn-1=(∏ λ i / ∏ uj)p0
i=0 j=1
又知,?Pn=1 (各事件两两不相容,且完备 ）
P0+(λ 0/μ 1)P0+(λ 1λ 0/μ 2 μ 1)P0+… +
n-1 n(∏ λ
i / ∏ uj)p0=1i=0 j=1
3,泊松输入 — 指数服务排队模型
63
状态转移速度图由此图易得：转入率 =转出率
n=0时,λ0P0=μ1P1
n一般,λn-1Pn-1+μn+1Pn+1=(λn+μn)Pn
同样可得下列公式,n = 1,2,…
n-1 nP
n=(λ n-1/μ n)Pn-1=(∏ λ i / ∏ uj)p0
i=0 j=1
0 n1 2 3
λ0 λ2λ1 λn-1 λn
μ1 μnμ3μ2 μn+1
3,泊松输入 — 指数服务排队模型
64
∞
L=∑kPk
k=0
Lq=∑(k-c)Pk c为服务台数
k>c
有效到达率 λe,有效离去 μe在平稳状态下：
λe=μe=∑λnPn=∑μnPn
关系,Little公式：
系统运行指标：
3,泊松输入 — 指数服务排队模型
65
系统的运行指标,(稳态时）
1.系统中顾客数的期望值：
∞
L=∑KPk
k=0
2.排队等待的顾客数的期望值：
Lq=∑(K-C) Pk
k>c
3,泊松输入 — 指数服务排队模型
66
3.有效到达率 λe:
稳态情况下,单位时间内进入系统的顾客数的期望值等于单位时间内离开系统的顾客数的期望值即,λe=μe
当系统中有 n个顾客时,每单位时间进入系统的顾客平均数为 λn,每单位时间离开系统的顾客平均数为 μn
λe=∑λnPn
μe=∑μnPn
3,泊松输入 — 指数服务排队模型
67
4.L,L q,λe,W,Wq之间的关系：
Little证明了：
W=L/λe,Wq=Lq/λe
几何解释,稳态时,一个顾客,进入系统后,每单位时间,平均到达 λe顾客 。
λe λe λe λe λe
进入时刻 离开时刻总时间 Ws
队长 Ls由时间段内个 λe组成的 Ls=λeWs
3,泊松输入 — 指数服务排队模型
68
同理,Lq=λeWq
又 W=Wq+（ 1/μ）
-------W与 Wq只相差一段平均服务时间 1/μ
L=Lq+(λe/μ)
3,泊松输入 — 指数服务排队模型
69
M/M/1 无限源系统稳态概率方程：
Pn= (λ/μ)Pn-1=…… = (λ/μ)nP0 1?n? N
0 N-11 2 N-2
λ λ λ λ
μ μμ μ
N
1,M/M/1/N/∞ 参数 λ,μ
系统状态转移速度：
70
由 ∑ Pn=1
n=0
M/M/1 无限源系统
N∑( λ/μ )nP
0=1
n=0
N
P0=1/[∑( λ/μ )n]=
n=0 (1- λ/μ )/
[(1- (λ/μ )N+1]λ?μ
1/(N +1) λ =μ
Pn=
1/(N +1) λ =μ
(1- λ/μ )(λ/μ )n/[(1- (λ/μ )N+1]
λ?μ
71
N
L=∑ nPn
n=0
M/M/1 无限源系统各计算公式：
λ e=∑ λ nPn=λ (1-PN)+0PN
(只有 Pn不再进人,故 λ n=0,其余均为 λ )
μ e =∑ μ nPn=0P0+μ (1-P0)（ 同理 ）
W =L/λ e,Wq=W -(1/μ ),Lq=Wqλ e
72
其他指标：
λ损 =λ-λe=λPN
P忙 =1-P0,P闲 =P0 （ 只有一个服务台 ）
平均服务台忙期的长度 T忙,
平均服务台闲期的长度 T闲,
T忙 / T闲 = P忙 / P闲 =(1- P0)/ P0
T闲 =1/λ(是从一个顾客到下一个顾客到达的平均间隔时间 )
于是 T忙 =(1- P0)/ λP0
M/M/1 无限源系统
73
2.M/M/1/∞/∞,λ μ
M/M/1 无限源系统稳态概率方程：
Pn=（ λ/μ） Pn-1=(λ/μ)nP0 令 ρ =λ/μ
0 n1 2 n-1
λ λ λ λ
μ μμ μ
λ
μ
∞
当 ρ? 1时,∑ρn不收敛，故应 ρ<1,
n=0即 λ<μ
74
∞P
0=1/(∑ρn)= 1-ρ 或 P0=1-λ/μn=0
M/M/1 无限源系统
Pn=ρn(1-ρ) 或 Pn=(λ/μ)n(1-λ/μ)
75
M/M/1 无限源系统进而：
∞L =
∑ n(ρn - ρn+1)
n=1
∞ ∞=
∑nρn - ∑nρn+1
n=1 n=1∞ ∞
=ρ+ ∑ nρn -∑ nρn +1
n=2 n=1∞
= ρ+∑ ρn +1
n=1
= ρ+ρ2/(1-ρ) = ρ/(1-ρ)
= λ/(μ-λ) (ρ=λ/μ)
取出第一项 写成∞∑ （ n+1） ρn+1
n=1与后一项合并
76
这里,
λe=μ(1-P0)=λ
W=L/λe=1/（ μ-λ）
Wq=W-1/μ=λ/[μ(μ-λ)]
Lq=λWq=λ2/[μ(μ-λ)]
系统内顾客数多于 k个的概率
P( N > k ) =?k+1
顾客逗留时间超过 t的概率
P( U > t ) = e-()t
M/M/1 无限源系统
77
P1=λ/（ μ+λ）
P损 =P忙 =P1= λ /（ μ+λ）
P闲 =P0= μ /（ μ+λ）
M/M/1 无限源系统
3.损失制 M/M/1/1,顾客到达若服务台被占用立即离开 。
直接可得：
P0= (1-ρ) / (1-ρ)2
= 1 / (1+ρ)
=μ / (μ+λ) P0+P1=1
78
1..M/M/C/N
M/M/C 无限源系统
0 N-11 2 N-2
λ λ λ λ
μ cμ2μ cμ
NCC-1
λ λ
cμ cμ
C+1
3μ
λ
(c-1)μ
λ
cμcμ
λ λ
稳态概率应满足的关系：
当 n<c时,Pn=[λ/(nμ) ]Pn-1
当 n?c时,Pn =[λ/(cμ)] Pn-1
令 ρ=λ/（ cμ） 系统负荷强度系数
79
c/nρPn-1=… =cn/n﹗ ρnP0
n<c
ρPn-1=… =cc/c﹗ ρnP0
c?n? N
M/M/C 无限源系统于是
Pn=
N
由 ∑ Pn=1 可得
n=0
C-1 N
∑ cn/n!ρnP0+ ∑ cc/c!ρnP0=1
n=0 n=c
c-1 P
0=[∑ cn/n!ρn+ (cc/c!)*((ρc-ρN+1)/(1-ρ))]-1
n=0
80
N
Lq=∑( n-c)Pn
n=c+1
=…
=(cc/c! ρc+1P0)/{ [1-(N-c+1) ρN-c
+(N-c) ρN-c+1]/(1-ρ)2}
M/M/C 无限源系统运行指标：
81
λe=λ(1-PN)
Wq=Lq/λe
W=Wq+1/μ
L=Wλe=Lq+λe/μ
2.M/M/C 等待系统 （ M/M/C/∞/∞）
此即上面的 M/M/C/N系统中,N->∞的情形
ρ=λ/(cμ)?1时,不收敛,设 ρ<1,
M/M/C 无限源系统
c-1
P0=[∑c n /n﹗ ρn+c c /c﹗ (ρc /1-ρ)]-1
n=0
82
(cn / n!)ρnP0 n<c
(cc/c!)ρnP0 n? c
M/M/C 无限源系统
Pn=
Lq = ccρc+1P0 / [c! (1-ρ)2]
λe =λ
Wq = Lq/λ
W = Wq+ 1/μ
L=λW= Lq+λ/μ
83
3.M/M/C 损失制系统 （ M/M/C/C/∞）
此即 M/M/C/N中 N=C 的情形
M/M/C 无限源系统
c
P0= [∑cn / n!ρn]-1
n=0
Pn= cn / n!ρnP0
λe=λ(1-Pc)
Lq=0,Wq=0(不等待 )
W=1/μ
L=λeW=λe/μ=(λ/μ) (1-Pc)
λ损 =λ-λe=λPc
84
例 6.1:某火车站售票处有三个窗口,
同时售各车次的车票 。 顾客到达服从泊松分布,平均每分钟到达 λ=0.9（ 人 ）,
服务时间服从负指数分布,平均服务率
μ=24（ 人 /h）,分两种情况：
1,顾客排成一队,依次购票；
2.顾客在每个窗口排一队,不准串队 。
求,（ 1） 售票处空闲的概率 。
（ 2） 平均等待时间和逗留时间 。
（ 3） 队长和队列长 。
例 题 解 析
85
例 题 解 析
稳态概率：
当 n<3时 Pn=[λ /（ nμ ） ]Pn-1=(λ n/n!)ρ nP0
=3n/n!ρ nP0
当 n?3时 Pn=[λ /（ cμ ） ]Pn-1=(33/3!)ρ nP0
=4.5ρ nP0
解,1,M/M/3/∞/∞
0 31 2
λ λ λ λ
μ 3μ2μ 3μ
4
λ
3μ
单位应相同：
μ=0.4（人 /分钟）
记 ρ= λ/（ 3μ）
ρ =0.9/(0.4*3)=0.75
86
例 题 解 析
∞
P0+3*0.75 P0+4.5*0.752 P0+∑4.5ρn P0 =1
n=3
∞
由 ∑ Pn=1
n=0
P0= 1/(1+2.25+2.53125+4.5ρ3/(1-ρ))
=1/13.375
=0.0748
P1=0.1683 P2=0.1893
∞ ∞
Lq=∑( n-c)Pn=33/3!ρ4 P0 ∑( n-3)ρn-3-1
n =c+1 n = 4
87
例 题 解 析
S= dF/ dρ=[(1-ρ)+ρ]/(1-ρ)2
于是：
Lq=4.5ρ 4P0/(1-ρ )2=1.704 λ e=λ
Wq=Lq/λ e=1.704/0.9=1.893分钟
∞ ∞
F=? S dρ=∑?(n-3)ρn-3-1dρ= ∑ ρn-3
n=4 n=4
=ρ/(1-ρ)
∞
S=∑ (n-3)ρn-3-1
n=4
88
例 题 解 析
Ws=Wq+ 1/μ =1.893+2.5=4.393分钟
Ls=λW s=3.954
故：
售票处的空闲的概率为 0.0748
平均等待时间 Wq=1.893分钟,
平均逗留时间 W=4.393分钟队长 Ls=3.954(人 ) Lq=1.704(人 )
89
2.M/M/1/∞/∞ 三个系统并联：
λ =0.3 μ =0.4 ρ =λ/μ =0.75
P0=1-ρ =0.25
三个服务台都有空的时候,
P03=0.0156
Ls=ρ /(1-ρ )=3 λ e=λ =0.3
Lq=Ls-λ /μ =2.25
Ws=Ls/λ =10
Wq=Ws-1/μ =7.5
例 题 解 析
90
故售票处空闲的概率为 0.0156
例 题 解 析平均等待时间 Wq=7.5分钟平均逗留时间 Ws=10分钟队长 Ls=3 三个队 共 3+3+3=9
队列长 Lq=2.25 共 6.75（ 人 ）
相比之下,排一队共享三个服务台效率好 。
91
顾客源有限的排队系统
1.M/M/1/m/m系统顾客源是 m个,那么系统容量实质上最多有 m个足够 。
0 m-11 2 m-2
mλ (m-1)λ 2λ λ
μ μμ μ
m
μ μ
(m-2)λ 3λ
顾客源中剩余的顾客数乘以每个顾客到达的概率
92
顾客源有限的排队系统
Pn={ [m-(n-1)]λ/μ}Pn-1 1?n?m
反复推得：
Pn=m!/(m-n)!(λ/μ)nP0 1?n?m
m
代入 ∑Pn=1
n=0m
∑m!/(m-n)!(λ/μ)nP0 =1
n=0
m
P0=[∑ m!/(m-n)!(λ/μ)n]-1
n=0
93
顾客源有限的排队系统 m
Pn=m!/(m-n)!(λ/μ)n[∑m!/(m-k)!(λ/μ)k]-1
k=0
由 λ(m-L)=μ(1-P0)
得 L=m-μ/λ(1-P0)
W=L/λe
Wq=W-1/μ
Lq=Wqλe
λe=λ(m-L)
m m
λe =∑ λnPn =λ ∑( m-n)Pn
n=0 n=0
m m
=λ (∑ m Pn-∑ n Pn)]
n=0 n=0
μe= μ(1-P0)
94
2,M/M/c/m/m系统顾客源有限的排队系统
0 m-11 2 m-2
mλ (m-1)λ 2λ λ
μ cμ2μ cμ
mCC-1
(m(c-1)λ
cμ
顾客源还有 m-(c-1)
个顾客每个顾客可到达的概率 λ
稳态概率方程
Pn=
[(m-n+1)λ/nμ]Pn-1 n?c
[(m-n+1)λ/cμ]Pn-1 c<n? m
95
m
代入 ∑Pn=1 得 (整理后 )
n=0
顾客源有限的排队系统反复代入得：
Pn=
m!/[n!(m-n)!](λ/μ )nP0 n?c
m!/[c!(m-n)!cn-c](λ/μ)nP0 c<n?m
c m
P0=[∑ m!/(m-n)!(λ/μ)n+∑ m!/(c!(m-n)!
n=0 n=c+1
cn-c)(λ/μ)n]-1
96
于是可得,
m
Lq=∑(n-c)Pn
n=c+1
λe=λ(m-L)
顾客源有限的排队系统又 L=Lq+λe/μ=Lq+λ/μ(m-L) 整理得：
L=(L+λ/μm)/(1+λ/μ)
Wq=Lq/λe,W=L/λe
97
应 用 举 例例 6.2:某汽车加油站有两台加油泵为汽车加油,加油站内最多能容纳 6辆汽车 。 已知顾客到达的时间间隔服从负指数分布,平均每小时到达 18辆汽车 。 若 加油站中已有 K辆车,当 K?2时,有 K/6的顾客将自动离去 。 加油时间服从负指数分布,
平均每辆车需要 5分钟 。 试求：
非标准的 M/M/2/N模型
98
应 用 举 例
（ 1）系统空闲的概率为多少？ P0
（ 2）求系统满的概率是多少？ P6
（ 3）求系统服务台不空的概率
P2+P3+P4+P5+P6=1- P0-P1
（ 4）若服务一个顾客,加油站可以获得利润 10元,问平均每小时可获得利润为多少元？ 10μe
（ 5）求每小时损失掉的顾客数？
λ损 =λ-λe
（ 6）加油站平均有多少辆车在等待加油？ Lq 平均有多少个车位被占用？ L
（ 7）进入加油站的顾客需要等多长的时间才能开始加油？ Wq 进入加油站的顾客需要多长时间才能离去？ W
99
稳态概率关系：
P1=λ/μP0=1.5P0 =(3/2)P0
P2=λ/(2μ)P1=0.75*1.5P0 =(9/8)P0
应 用 举 例解,状态转移速度图以小时为单位 λ=18 μ=60/5=12
λ
μ 2μ2μ 2μ2μ
0 51 2 4 63
2μ
(1-2/6)λ (1-3/6) λ (1-4/6) λλ (1-5/6) λ
应 用 举 例
P3=[(4/6)λ/(2μ)]P2=(1/2)(9/8)P0= (9/16)P
P4=[(3/6)λ/(3μ)]P3=(3/8)(9/16)P0= (27/128)P0
P5=[(2/6)λ/(2μ)]P4=(1/4)(27/512)P0 = (27/2048)P0
P6=[(1/6)λ/(2μ)]P5=(1/8)(27/512)P0= (27/4096)P0
由 P0=P1+P2+P3+P4+P5+P6=1
解得,P0=0.22433
P1 P2 P3 P4 P5 P6
0.33649 0.25237 0.12618 0.04732 0.01183 0.00148
101
运行指标：
(1) P0=0.22433
(2) P6=0.00148
(3) P忙 =1-P0-P1=0.43918
(4)μe=0P0+μP1+2μ(P2+P3+P4+P5+P6)
=14.578（ 辆 /h）
10μe= 145.78(元 /小时 ）
应 用 举 例
102
(5)λ 损 =λ -λ e
=18-14.5782
=3.4218（ 辆 /h）
应 用 举 例
(6) Lq=(3-2)P3+(4-2)P4+(5-2)P5+(6-2)P6
=0.26223
L=Lq+λ e/μ
=0.26223+1.21485
=1.47708
103
应 用 举 例
(7) Wq=Lq/λ e
=0.018h
=1.08分钟
W=Wq+1/μ
=0.101h
=6.08分钟
104
例 6.3:某车站候车室在某段时间旅客到达服从泊松流分布,平均速度为 50人 /h,每位旅客在候车室内停留的时间服从负指数分布,平均停留时间为 0.5h,问候车室内平均人数为多少？ （ L)
应 用 举 例解：把旅客停留在候车室看做服务,
于是系统为 M/M/∞/∞/∞
λ=50 μ=1/0.5=2
105
稳态概率关系：
Pn=λ/(nμ)Pn-1=…,=1/n!(λ/μ)nP0
记 ρ=λ/μ=50/2 =25
应 用 举 例
0 n1 2 n-1
λ λ λ λ
μ nμ2μ (n+1)μ
n+1
λ λ
3μ (n-1)μ
λ
(n+2)μ
状态转移速度图,
106
应 用 举 例
∞
P0=(∑1/n!ρn)-1= e-ρ
n=0
∞
L=∑nPn
n=1 ∞
= e-ρ∑1/(n-1)!ρn
n=1 ∞
=ρe-ρ∑1/n!ρn=ρ=25(人 )
n=0
∞
代入 ∑Pn=1
n=0
107
其他模型选介
M/G/1排队系统设顾客单位时间到达数为?，服务时间为随机变量 V，且 E(V) = 1 /
D(V) =?2
那么，服务强度，当? < 1时
P0 = 1 -?
根据波拉切克 -欣钦 （ Pollaczek-Khinchine） 公式可导出
Lq = (?2+) / [2(1-?)]
其它量的计算同前。
108
其他模型选介
M/D/1排队系统设顾客单位时间到达数为?，服务时间为一个常数 v，则 E( v ) = v = 1 /?
D( v ) = 0
那么，服务强度，当? < 1时
P0 = 1 -?
根据上一模型的公式可直接得到
Lq =?2 / [2(1-?)]
其它量的计算同前。
109
4.排队系统的优化目标与最优化问题以完全消除排队现象为研究目标是不现实的,那会造成服务人员和设施的严重浪费,但是设施的不足和低水平的服务,又将引起太多的等待,从而导致生产和社会性损失 。 从经济角度考虑,
排队系统的费用应该包含以下两个方面：
一个是服务费用,它是服务水平的递增函数；另一个是顾客等待的机会损失
(费用 ),它是服务水平的递减函数 。 两者的总和呈一条 U形曲线 。
110
4.排队系统的优化目标与最优化问题系统最优化的目标就是寻求上述合成费用曲线的最小点 。 在这种意义下,
排队系统的最优化问题通常分为两类：
一类称之系统的静态最优设计,目的在于使设备达到最大效益,或者说,在保证一定服务质量指标的前题下,要求机构最为经济；另一类叫作系统动态最优运营,是指一个给定排队系统,如何运营可使某个目标函数得到最优 。 归纳起来,排队系统常见的优化问题在于：
111
4.排队系统的优化目标与最优化问题
(1)确定最优服务率?*；
(2)确定最佳服务台数量 c*；
(3)选择最为合适的服务规则；
(4)或是确定上述几个量的最优组合 。
研究排队系统的根本目的在于以最少的设备得到最大的效益,或者说,在一定的服务质量的指标下要求机构最为经济 。 排队系统的最优化问题分为两大类：
112
4.排队系统的优化目标与最优化问题系统的静态最优设计问题和系统的动态最优控制问题 。 由于系统动态最优控制问题涉及更多的数学知识,
因此,本章只讨论系统静态的最优设计问题 。 这类问题一般可以借助于前面所得到的一些表达式来解决 。
本节仅就?,c 这两个决策变量的分别单独优化,介绍两个较简单的模型,以便读者了解排队系统优化设计的基本思想 。
113
4.排队系统的优化目标与最优化问题一,M／ M／ 1／ ∞ 系统的最优平均服务率?*
设
C1—— 当?=1时服务系统单位时间的平均费
CW—— 平均每个顾客在系统逗留单位时间的损失；
y—— 整个系统单位时间的平均总费用 。
其中 C1,C2 均为可知 (下同 )。 则目标函数为
(6-52)Lccy
w1
114
4.排队系统的优化目标与最优化问题将 L=?／ (? -?),代入上式,得易见 y是关于决策变量?的一元非线性函数由一阶条件解得驻点
(6-53)
11 wccy
0
)(
1
21 wccd
dy
1* / cc w
115
4.排队系统的优化目标与最优化问题根号前取正号是为了保证?<1,即
*>?,这样,系统才能达到稳态 。 又由二阶条件
(因?>? ）
可知 (6-53)给出的?*为 (?,∞) 上的全局唯一最小点 。 将?*代入 (6-52)中,可得最小总平均费用
0)( 2 32
2
wcd yd
wcccy 11* 2 （ 6-54）
116
4.排队系统的优化目标与最优化问题另外,若设 cw为平均每个顾客在队列中等待单位时间的损失,则需用式 (6-26)给出的 取代式 (6-52)中的,这时类似可得一阶条件：
这是一个关于?的四次方程,尽管它有求根公式,但由于形式太复杂,实际并不应用 。 一般采用数值法 (如牛顿法 )确定其根?*。
)(
2
qL
022 322213141 ww ccccc
117
4.排队系统的优化目标与最优化问题二,M／ M／ s／ ∞ 系统的最优服务台数 s*
设目标函数为
(6-55)
其中：
s—— 并联服务台的个数 (待定 )；
f(s)—— 整个系统单位时间的平均总费用,它是关于服务台数 s的函数；
c2—— 单位时间内平均每个服务台的费用；
)()( 2 sLcscsf w
118
4.排队系统的优化目标与最优化问题
cw—— 平均每个顾客在系统中逗留 (或等待 )单位时间的损失；
L(s)—— 平均队长 (或平均等待队长 ),它是关于服务台数 s的函数；
我们要确定最优服务台数 s*∈ {1,2,… }，
使由于 s取值离散,不能采用微分法或非线性规划的方法,因此我们采用差分法 。 显然有
（ 6-56）
)()(m in)( 2* sLcscsfsf w
)1()(
)1()(
**
**
sfsf
sfsf
119
4.排队系统的优化目标与最优化问题把式 （ 6-55） 代人式 (6-56) 中,得由此可得令
(6-57)
依次计算 s=1,2,… 时的 L(s)值及每一差值 L(s)-L(s+1),根据?落在哪两个差值之间就可确定 s*。
)1()1()(
)1()1()(
**
2
**
2
**
2
**
2
sLcscsLcsc
sLcscsLcsc
ww
ww
)()1()1()( **2** sLsLccsLsL
w
wc
c 2
120
例 6.4:兴建一座港口码头,只有一个装卸船只的泊位 。 要求设计装卸能力 。
装卸能力单位为 （ 只 /日 ） 船数 。 已知：
单位装卸能力的平均生产费用 a=2千元,
船只逗留每日损失 b=1.5千元 。 船只到达服从泊松分布,平均速率 λ=3只 /日 。 船只装卸时间服从负指数分布 。 目标是每日总支出最少 。
应 用 举 例解,λ=3 μ待定 模型 M/M/1/∞/∞
队长 Ls =λ/(μ-λ)
总费用 C=aμ+bLs=aμ+bλ/(μ-λ)
求极值 （ 最小值 ）
应 用 举 例求导 dc/du=a+(-bλ )/(μ -λ )2 = 0
得,μ -λ =+ - (bλ/a )1/2（ 根据题意舍负 ）
所以 μ=λ+(bλ/a)1/2=3+(2.25)1/2=4.5(只 /日 )
122
例 6.4,建造一口码头,要求设计装卸船只的泊位数 。 已知,预计到达
λ=3只 /天,泊松流；装卸 μ=2只 /天,
负指数分布 。 装卸费每泊位每天 a=2
千元,停留损失费 b=1.5千元 /日 。 目标是总费用最少 。
应 用 举 例
解,模型 M/M/c/∞/∞ c待定
总费用,F=ac+bLs（ c） 离散,无法用求导来解 。
123
应 用 举 例考虑,M/M/c/∞/∞
要求,ρ=λ/(cμ) <1 即 c>(λ/μ)=1.5
讨论 c=2,3,4…
c-1
P0=[∑cn/n﹗ ρn+cc/c!ρc/(1- ρ)]-1
n=0
Lq= ccρc+1/c!(1-ρ)2 P0
L=Lq+λ/μ
124
应 用 举 例结论,c=3 即设计三个装卸泊位可使每天的总费用最少为 8.60526千元 。
M /M/ 2/? /? M /M/ 3/? /? M /M/ 4/? /?
P
0
1/7=0.142 86 4/19=0.21 053 40/181=0,22099
Lq 27/14=1.9 2857 9/83=0.23 684 81/1810=0,04475
Ls 24/7=3.42 857 33/19=1.7 3684 1398/905= 1.5447 5
F 64/7=9.14 286 327/38=8,60526 9337/905= 10.317 13
ρ =1/2ρ =3/4 ρ =3/8
125
4.排队系统的优化目标与最优化问题例 6.6:某市政府的上访接待室每天平均接待来访 48次,来访者为泊松流,每天上访所造成的损失为平均每次 20元 。 该室每设置一名接待员的服务成本为平均每天 8
元,接待时间为指数分布,平均每天可接待 25次 。 问应设置几名接待员能使平均总费用为最小?
解,由题意知,这是一个 M／ M／ s／ ∞
系统,有
126
4.排队系统的优化目标与最优化问题
c2＝ 8元／人天,cw＝ 20元／天次,?＝ 48
次／天,?＝ 25次／天,
则按式 (6-57)得
＝ 0.4
另有
20
8
92.12548
s
s
ssss
92.192.111,92.1
127
4.排队系统的优化目标与最优化问题把 代入式 (6-15),得又由式 (6-17),式 (6-18) 得把,P0代入上式,整理可得
1,,
11
0
0 )92.1()!1(
)92.1(
!
)92.1(
s
k
sk
sskP
02)1(! PsL
s
1,,
128
4.排队系统的优化目标与最优化问题而当 S=1时,?=?=1.92＞ 1,不满足系统达到稳态的条件?＜ 1,故这时 L(1)=∞ 。
依次计算当 s＝ 2,3,… 时的值及其差值
L(s)-L(s+1)上,如表 6-3所示 。
由表 6-3及所落位置,对应可知：
S*＝ 4(人 )
92.1
)92.1(
!
)92.1()92.1()!1()92.1(
)92.1()(
1
0
1
s
k
s
k
s
k
sss
sL
,3,2?s
129
据此按 (6-55)式可得最小总平均费用：
(元／天 )
故该室应设置 4名接待员可使每天总平均费用达到最小,为 73,26元 。
表 6-3 s＝ 2,3,… 时的 L(s)值及其差值上 L(s)-L(s+1)
(下页）
4.排队系统的优化目标与最优化问题
26.730 6 3.22048)4( *sf
130
4.排队系统的优化目标与最优化问题
)(sL?
)1()( sLsL?
S 1 2 3 4 5 …
24.
490
2.64
5
2.06
3
1.9
52
…
21.8
45
0.58
2
0.11
1
…
4.0
