排队论基础 主要内容 1.基本概念 2.输入过程和服务时间分布 3.几个排队模型 4.排队系统的优化目标.

Presentation on theme: "排队论基础 主要内容 1.基本概念 2.输入过程和服务时间分布 3.几个排队模型 4.排队系统的优化目标."— Presentation transcript:

1 排队论基础 主要内容 1.基本概念 2.输入过程和服务时间分布 3.几个排队模型 4.排队系统的优化目标

2 排队论(Queuing Theory),也称为随机服
务系统理论(Random Service System Theory), 是一门研究排队和等待服务现象的科学.它在 研究各种排队系统概率规律性的基础上,解决 相应排队系统的最优设计和最优控制问题. 排队论里把要求服务的对象称为“顾客”, 而把提供服务的人或机构称为“服务台”或“服 务员”. 顾客与服务员组成了服务系统.顾客 为了得到某种服务而到达系统,若不能立即获 得服务而又允许排队等待,则加入等待队伍, 待获得服务后离开系统.

3 1909年,丹麦哥本哈根电子 公司电话工程师A. K. Erlang的 开创性论文“概率论和电话通讯 理论”标志此理论的诞生. 排队
论早期研究电话、通信中的问题, 现在它们仍然是排队论的重要应用领域. 近 几十年排队论在计算机通讯网络系统、交通 运输、医疗卫生、库存管理、公共服务等诸 多领域中得到广泛应用. ( )

4 随机性是排队系统的一个普遍特点,顾 客的到达情况(如相继到达时间间隔)与每个 顾客接受服务的时间是随机的.这样的服务 系统称为随机服务系统. 如果为了减少排队而增加服务设施,人 力和物力的支出就大,甚至会出现空闲浪费; 如果服务设施太少,顾客排队等待的时间就 会很长.如何做到既保证一定的服务质量指 标,又使服务设施费用经济合理,这就是随机 服务系统理论—排队论所要研究解决的问题.

5 一.基 本 概 念 (一)排队系统的描述 1.排队系统的特征 (1)请求服务的人或物—顾客； (2)为顾客服务的人或物—服务员或服务 台；
(3)顾客到达系统的时刻是随机的,为每 一位顾客提供服务的时间是随机的,因而整 个排队系统的状态也是随机的.

6 2.排队系统的基本组成部分 排队系统有输入过程、服务规则和服 务台等三个组成部分. 输入过程 指要求服务的顾客按怎样 的规律到达排队系统的过程,也称其为顾客 流.可以从三个方面来描述一个输入过程. (1)顾客总体数 又称顾客源或输入源. 顾客源可以是有限的,也可以是无限的. 例 如,到售票处购票的顾客总数可以认为是无 限的,而某个工厂因故障待修的机床则是有 限的.

7 (2) 顾客到达方式 单个到达或成批到 达.病人到医院看病是顾客单个到达的例子. 在库存问题中如将材料进货或产品入库看作 是顾客,那么这种顾客是成批到达的. (3) 顾客流的概率分布或相继顾客到达 的时间间隔的分布 这是求解排队系统有关 运行指标问题时,首先需要确定的指标,即在 一定的时间间隔内到达k(k=1, 2, …)个顾客的 概率分布. 顾客流的概率分布一般有定长分 布、二项分布、Poisson分布(最简单流)以及 Erlang分布等.

8 服务规则 一般可以分为损失制、等待 制和混合制等三类. (1)损失制 如果顾客到达排队系统时, 所有服务台都已被先来的顾客占用,那么他 们就自动离开系统永不再来.如电话拔号后 出现忙音,顾客不愿等待而自动挂断电话， 如要再打,就需重新拨号,这种服务规则即为 损失制. (2)等待制 当顾客来到系统时,所有服 务台都不空,顾客加入排队行列等待服务.例 如,排队等待售票、故障设备等待维修等.

9 在等待制中,服务台在选择顾客进行服 务时,常有如下四种规则： ①先到先服务 按顾客到达的先后顺序 对顾客进行服务,这是最普遍的情形. ②后到先服务 例如仓库中迭放的钢 材,后迭放上去的先被领走. ③随机服务 即当服务台空闲时,不按照 排队顺序而随意指定某个顾客去接受服务. ④优先权服务 如老人、儿童优先进车 站; 危重病员先就诊;遇到重要数据需要处 理计算机立即中断其他数据的处理等.

10 (3)混合制 这是等待制与损失制相结 合的一种服务规则,一般指允许排队,但不 允许队列无限长.一般有三种情形： ①队长有限 当排队等待服务的顾客人 数超过规定数量时,后来的顾客自动离去, 即系统的等待空间是有限的. 如在最多只能容纳m个顾客的系统中, 当新顾客到达时,若系统中的顾客数(称为 队长)小于m, 则可进入系统排队或接受服 务;否则,便离开系统,并不再回来.如水库 的库容是有限的,旅馆的床位是有限的.

11 ②等待时间有限 即顾客在系统中的等 待时间不超过某一给定的长度T,当等待时 间超过T时,顾客将自动离去,并不再回来. 如在易损坏的电子元件库存问题中,超过一 定存储时间的元件被自动认为失效. ③逗留时间(等待时间与服务时间之和) 有限 例如用高射炮射击飞机,飞机越过高射 炮射击有效区域的时间有限.

12 服务台 从三个方面来描述： (1)服务台数量及构成形式 从数量上来 看,服务台有单服务台和多服务台之分.从构 成形式上来看,服务台有： ①单队——单服务台式； ②单队——多服务台并联式； ③多队——多服务台并联式； ④单队——多服务台串联式； ⑤单队——多服务台并串联混合式,以及 多队——多服务台并串联混合式等等.

13 ①单服务台排队系统 ②单队列—n个服务台并联的排队系统

14 ③n个队列—n个服务台的并联排队系统 ④单队—多个服务台的串联排队系统

15 ⑤多队—多服务台混联、网络系统 一般排队系统的描述

16 (2)服务方式 在某一时刻接受服务的顾 客数,它有单个服务和成批服务两种. (3)服务时间的分布 一般情况下,对每一 个顾客的服务时间是一随机变量,其概率分布 有定长分布、负指数分布、k级Erlang分布、 一般分布(所有顾客的服务时间都是独立同分 布的)等等. 3. 排队系统的描述符号与分类 为了区别各种排队系统,根据输入过程、 服务规则和服务台的变化对排队模型进行描 述或分类,1953年英国统计学家D.G.Kendall

17 ( )提出了一种目前在排队论中被广 泛采用的记号, 后来又被扩充为如下的表达 方式：X/Y/Z/A/B/C 各符号的意义为： X—表示顾客相继到达间隔时间分布, 常用下列符号： M——表示到达过程为Poisson过程或负指数分布； D——表示定长输入； Ek——表示k阶Erlang分布； G——表示一般相互独立的随机分布.

18 Y—表示服务时间分布, 所用符号与表示顾客到达间隔时间分布相同.
Z—表示服务台(员)个数. A—表示系统中顾客容量限额: 如系统容量为m(m>0), 有n个服务台，当m=n时, 说明系统不允许等待, 即为损失制. m=∞时为等待制系统, 此时∞一般省略不写. n<m<∞时为混合制系统. B—表示顾客源限额, 分有限与无限两种, ∞表示顾客源无限, 此时∞一般也省略不写.

19 C—表示服务规则，常用下列符号： FCFS ——表示先到先服务的排队规则； LCFS ——表示后到先服务的排队规则； PR ——表示优先权服务的排队规则. 例如：排队问题 M/M/n/∞/∞/FCFS 表示顾客到达间隔时间为Poisson流(负指数 分布), 服务时间为负指数分布, 有n个服务台, 系统等待空间容量无限(等待制), 顾客源无 限, 采用先到先服务规则.

20 在很多情况下, 排队问题仅用上述表达 形式中的前3个、4个或5个符号. 如不特别 说明, 均理解为系统等待空间容量无限, 顾 客源无限, 先到先服务, 单个服务的等待制 系统. (二) 排队系统的主要运行指标 研究排队系统目的是通过了解系统运 行的状况, 对系统进行调整和控制, 使系统 处于最优运行状态. 因此, 首先需要描述系 统的运行状况, 主要运行指标有：

21 1.队长和等待队长 队长是指系统中的顾客数(排队等待的 顾客数与正在接受服务的顾客数之和).等待 队长是指系统中正在排队等待服务的顾客数. 队长和等待队长一般都是随机变量, 我 们希望能确定它们的分布，或至少能确定它 们的期望值(即平均队长和平均等待队长). 队长的分布是顾客和服务员都关心的,特别 对系统设计人员来说,如果能知道队长的分 布,就能确定队长超过某个值的概率,从而确 定合理的等待空间.

22 2.等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止 的这段时间称为等待时间, 是随机变量, 也 是顾客最关心的指标, 因为顾客通常希望等 待时间越短越好. 从顾客到达时刻起到他接 受服务完成止的这段时间称为逗留时间, 也 是随机变量, 顾客同样非常关心. 对于这两 个指标的研究当然是希望能够确定它们的 分布, 或至少能够知道顾客的平均等待时间 和平均逗留时间.

23 除了上述几个主要运行指标外, 还会用 到其他一些重要的指标. 如在损失制或系统 容量有限的情况下, 由于顾客被拒绝, 而使服
务系统受到损失的顾客损失率及系统强度等. 由于相当一部分排队系统在运行了一定 时间后, 都会趋于一个平稳状态, 在平稳状态 下, 运行指标与系统所处的时刻无关, 而且系 统初始状态的影响也会消失. 我们将主要讨 论系统平稳状态的性质. (三)一些常用记号 Pn —稳态系统任一时刻状态为n的概率.  —平均到达率；1/ —平均到达间隔.

24 Ls—平均队长 稳态系统任一时刻的所有顾客数的期望值； Lq—平均等待队长 稳态系统任一时刻的等待服务的顾客数的期望值；
 —平均服务率；1/ —平均服务时间. Ls—平均队长 稳态系统任一时刻的所有顾客数的期望值； Lq—平均等待队长 稳态系统任一时刻的等待服务的顾客数的期望值； Ws—平均逗留时间 在任意时刻进入稳态系统的顾客逗留时间的期望值； Wq—平均等待时间 在任意时刻进入稳态系统的顾客等待时间的期望值. 对于损失制和混合制的排队系统,顾客在到达 服务系统时,若系统容量已满则离去,到达的顾客 不一定全部进入系统，为此引入有效平均到达率.

25 e —有效平均到达率 每单位时间内进 入系统的平均顾客数(期望值). 这时就是每 单位时间内来到系统(包括未进入系统)的平 均顾客数(期望值). 对于等待制的排队系统, 有e=. (四)Little公式 在系统达到稳态时，有效平均到达率为 常数e，则有下面的John D.C. Little (美国, 1928-)公式：

26 二.输入过程和服务时间分布 (一)输入过程 输入过程描述顾客以怎样的规律到达系 统，一般用相继两顾客到达时间间隔来描述
系统输入特征. 主要输入过程有： 1. 定长输入. 顾客有规则地等距到达，每 隔时间到达一个顾客. 这时相继顾客到达间 隔的分布函数F(t)为：

27 2. Poisson输入，又称最简单流. 满足下 面三个条件的输入称之为最简单流. (1) 平稳性. 又称输入过程是平稳的，指 在长度为t的时段内恰好到达k个顾客的概率 仅与时段长度有关，而与时段起点无关, 即 对任意∈(0,∞)，在(,+t]或(0, t)内恰好到 达k个顾客的概率相等： 设初始条件为 , 且有

28 可以证明, 对于Poisson流, 随机变量N(t) 服从Poisson分布, 即在长度为t的时间内到达 k个顾客的概率为
(2)无后效性. 在任意几个不相交的时间 区间内，各自到达的顾客数是相互独立的. 通俗地说就是以前到达的顾客情况，对以后 顾客的到来没有影响. (3)单个性又称普通性. 在充分小的时段 内最多到达一个顾客. 可以证明, 对于Poisson流, 随机变量N(t) 服从Poisson分布, 即在长度为t的时间内到达 k个顾客的概率为

29 其中参数>0为一常数，表示单位时间内到
达顾客的平均数，又称为顾客的平均到达 率. 对于Poisson流，可以证明其相继顾客 到达时间间隔i，i=1, 2, …是相互独立同分 布的，服从负指数分布，其分布函数和分 布密度分别为：

30 对任意的j与k, 设第j与第j+k个顾客之间的到达间 隔为 , 可以证明，随机变量 Tk服从参数为的k阶Erlang分布其分布密度为：
3.k阶Erlang输入. 在参数为的Poisson输入中, 对任意的j与k, 设第j与第j+k个顾客之间的到达间 隔为 , 可以证明，随机变量 Tk服从参数为的k阶Erlang分布其分布密度为： 其中k为非负整数. 例如某排队系统有并联的k个服务台, 顾客流 为Poisson流，规定第i, k+i, 2k+i, …个顾客排入第i 号台(i=1, 2, …, k), 则第k台所获得的顾客流, 即为 k阶Erlang输入流, 其他各台, 从它的第一个顾客到 达以后开始所获得的流也为k阶Erlang输入流.

31 一定是一个, 而可能是一批, 每批顾客的数目n是一 个随机变量, 其分布为: (二)服务时间分布
4.成批到达的输入. 排队系统每次到达的顾客不 一定是一个, 而可能是一批, 每批顾客的数目n是一 个随机变量, 其分布为: (二)服务时间分布 1.定长分布. 每一个顾客的被服务时间都是常 数，此时服务时间t的分布函数为： 2.负指数分布. 各个顾客的被服务时间相互独 立, 具有相同的负指数分布, 分布函数为

32 其中>0为一常数，服务时间t的数学期望1/ 为平
均被服务时间. 3. k阶Erlang分布. 每个顾客的被服务时间相 互独立，具有相同的Erlang分布, 密度函数为 其中>0为一常数，平均服务时间为 当k=1时, Erlang分布化归为负指数分布. 当k→∞ 时，得到长度为1/的定长分布.

33 排队论研究的首要问题是排队系统主要 运行指标的概率规律，即研究系统的整体性 质，然后进一步研究系统的优化问题. 与这
(三)排队论研究的基本问题 排队论研究的首要问题是排队系统主要 运行指标的概率规律，即研究系统的整体性 质，然后进一步研究系统的优化问题. 与这 两个问题相关的还包括排队系统的统计推断 问题. 1.通过研究主要运行指标在瞬时或平稳 状态下的概率分布及其数字特征，了解系统 运行的基本特征. 2.统计推断问题. 建立适当的排队模型 是排队论研究的第一步，建立模型过程中经

34 常要考虑如下问题：检验系统是否达到平稳 状态；检验顾客相继到达时间间隔的相互独 立性；确定服务时间的分布及有关参数等. 3.系统优化问题,又称为系统控制问题或 系统运营问题，基本目的是使系统处于最优 或最合理的状态. 系统优化问题包括最优设 计问题和最优运营问题, 例如有最少费用问 题、服务率的控制问题、服务台的开关策 略、顾客(或服务)根据优先权的最优排序等 方面的问题.

35 三. 几个排队模型 排队系统的一般决策过程： ① 根据已知条件绘制状态转移速度图; ② 依据状态转移速度图写出各稳态概率之 间的关系;
③ 求出 P0 及 Pn ; ④ 计算各项运行指标; ⑤ 用系统运行指标构造目标函数，对系统 进行优化.

36 (一) M/M/n/n排队模型 顾客到达的间隔时间——负指数分布，参数为 顾客接受服务的时间——负指数分布，参数为 系统有n个服务台 系统最多容纳n个顾客 系统的状态空间

37 1. M/M/n/n状态转移图 2. 稳态概率之间的关系(令 ,称为系统 负荷水平或强度) 对0状态, 有 故 对1状态, 有 故
k-1 2 1 k   2 3 (k-1) k n-1 n n (n-1) 2. 稳态概率之间的关系(令 ,称为系统 负荷水平或强度) 对0状态, 有 故 对1状态, 有 故 对k-1状态, 有 故 对n-1状态, 有 故 正则条件

38 3. 求出平稳分布 4. 运行指标 (1) 系统损失概率 (2) 单位时间内平均损失的顾客数 (3) 有效平均到达率

39 (4) 占用服务台的均值 显然 (5) 顾客在系统中平均逗留时间 客的平均被服务时间. (6) 服务台的效率
根据Little公式可得 即等于顾 客的平均被服务时间. (6) 服务台的效率

40 例1 某计算机有5个终端, 用户按Possion 流到达, 平均每分钟到达0.2个用户, 每个用 户平均用机时间为15分钟, 用机时间服从负 指数分布, 当5个终端被占用时, 后来的用户 只能到其他计算机处接受服务. 求系统的运 行指标. 解 这是M/M/5/5排队模型.平均到达率 =12户/小时, 平均服务率=4户/小时, 系统 强度 (1) 系统损失概率

41 (2) 每小时内平均损失的用户数 (3) 用户有效平均到达率 (4) 占用终端的均值或系统平均队长 (5) 用户在系统中平均逗留时间
(户) (3) 用户有效平均到达率 (户/小时) (4) 占用终端的均值或系统平均队长 (个) (5) 用户在系统中平均逗留时间 (小时) (6) 终端的服务效率

42 (二) M/M/n排队模型 顾客到达的间隔时间——负指数分布，参数为 顾客接受服务的时间——负指数分布，参数为 系统有n个服务台 系统容量没有限制 系统的状态空间

43 1. M/M/n状态转移图 2. 稳态概率之间的关系(其中 ) 对0状态, 有 故 对1状态, 有 故 对n-1状态, 有 故
n-1 2 1 n   2 3 (n-1) n n+1 n+2 2. 稳态概率之间的关系(其中 ) 对0状态, 有 故 对1状态, 有 故 对n-1状态, 有 故 对n状态, 有 故 对n+r-1状态,有 故 正则条件

44 3. 求出平稳分布 当 时, 由正则条件可得 4. 运行指标 (1) 平均等待队长

45 (2) 占用服务台的均值 (3) 平均队长

46 (4) 平均等待时间 根据Little公式可得 (5) 平均逗留时间 根据Little公式可得 (6) 必须排队等待的概率

47 例2 某城市火车站有4台电子触摸屏供旅 客查询, 旅客按Possion流到达, 每位旅客在 触摸屏查询时间服从负指数分布, 平均查询 时间为3分钟, 如果所有触摸屏被占用时就排 队等待, 根据以往统计资料知道触摸屏被占 用的均值为1.5台. 求系统的运行指标. 解 这是M/M/4排队模型.由条件可知平 均服务率=1/3位/分钟, 台, 因此 .

48 (1) 平均等待队长 (2) 平均队长 (3) 平均等待时间 (4) 平均逗留时间 (5) 必须排队等待的概率 (人) (人) (分钟)

49 (三) M/M/n/m(m>n)排队模型
顾客到达的间隔时间——负指数分布，参数为 顾客接受服务的时间——负指数分布，参数为 系统有n个服务台 系统最多容纳m个顾客 系统的状态空间

50 1. M/M/n/m状态转移图 2. 稳态概率之间的关系(其中 ) 对0状态, 有 故 对1状态, 有 故 对n-1状态, 有 故
n-1 2 1 n   2 3 (n-1) n n+1 m 2. 稳态概率之间的关系(其中 ) 对0状态, 有 故 对1状态, 有 故 对n-1状态, 有 故 对n状态, 有 故 对m-1状态,有 故 正则条件

51 3. 求出平稳分布 由正则条件可得

52 4. 运行指标 (1) 系统损失概率 (2) 单位时间内平均损失的顾客数 (3) 有效平均到达率 (4) 占用服务台的均值

53 从而 (5) 平均等待队长 当 时, 当 时,

54 (6) 平均队长 (7) 平均等待时间 根据Little公式可得 (8) 平均逗留时间 根据Little公式可得 注 若m=n时, 即是M/M/n/n排队模型; 若 令 ,则成为M/M/n/n排队 模型.

55 例3 某加油站有两条加油管, 汽车按平均 每2分钟1辆的Possion流到达, 加油时间服从 负指数分布, 参数=0.5辆/分钟, 除加油的车 外, 站内最多只能停放3辆车等待, 如果当汽 车到达时发现位置已满, 它即往别处加油. 求 系统的运行指标. 解 这是M/M/2/5排队模型. 由条件可知 ==0.5, 加油站的空闲率

56