新闻资讯

<主页 > 新闻资讯 >

第3讲 排队系统的基本概念

发布日期:2020-05-10 09:34

  第3讲 排队系统的基本概念_工学_高等教育_教育专区。2011/9/29 系统建模与仿真 系统建模与仿真 排队系统 ? 知识回顾 1. 离散事件系统(DEDS或DES)基本概念、基 本要素 2. DES系统举例 3. 离散事件系统仿线 系统建模与仿真 系统建模与仿真 排队系统 ? 知识回顾 1. 离散事件系统(DEDS或DES)基本概念、基 本要素 2. DES系统举例 3. 离散事件系统仿线. 离散事件系统策略 5. 手工仿真 排队系统 系统建模与仿真 第三讲 排队系统的基本概念 1 2 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 排队系统 系统建模与仿真 排队系统 一.排队系统的特征 1. ? ? 二.排队系统的形式 1. 单服务台的排队系统 排队除了有形的队列外,还可以是无形的队 列。 电话预定租车服务; 网络传输; 2. ? ? ? ? 排队的可以是人,也可以是物。 生产线上的原材料、半成品; 故障待修的机器; 要进站的火车由于展台被占而等待; 网络打印 3 顾客到达 队列 ... 完成服务后离去 服务台 正在接受服务的顾客 单服务台排队系统 4 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 排队系统 系统建模与仿真 排队系统 二.排队系统的形式 2. S 个服务台,一个队列的排队系统 二.排队系统的形式 3. S 个服务台,S个队列的排队系统 队列 1 服务台 1 ... 完成服务后离去 完成服务后离去 服务台 1 完成服务后离去 服务台 2 完成服务后离去 服务台 3 顾客到达 队列 ... 服务台 2 服务台 3 S 个服务台,一个队列的排队系统 顾客到达 队列 2 ... 队列 3 ... S 个服务台,S个队列的排队系统 5 6 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 1 2011/9/29 系统建模与仿真 排队系统 系统建模与仿真 排队系统 二.排队系统的形式 4. 多个服务台的串联排队 顾客到达 队列 三.排队系统描述 实际中的排队系统各不相同,但概括起 来都由三个基本部分组成:输入过程、 排队及排队规则和服务机制。 ... 队列 服务台 ... 完成服务后离去 服务台 多个服务台的串联排队 7 8 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 排队系统 系统建模与仿线. 输入过程 说明顾客是按什么样的规律到达系统,需 要从三个方面来描述: ? ? ? 顾客总数。可以是有限的,也可以是无限的; 到达方式。单个到达还是成批到达。库存问题中的进 货为成批到达; 顾客相继到达时间间隔的分布。 ? 定长分布(D)。 ? 最简流(Poission流)(M):顾客相继到达的时间间隔 为独立的,且同负指数分布,其密度函数为: 2. 排队及排队规则 a) 排队 ① 无限排队:系统中的顾客是无限的,队列可 以排到无限长,顾客到达系统后均可以进入 系统排队或接受服务。 ??e ? ?t a(t ) ? ? ? 0 t?0 t?0 (2.1) 9 10 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 排队系统 系统建模与仿线. a) ② 排队及排队规则 排队 有限排队:排队系统中的顾客数是有限的,即系统 的空间是有限的,当系统被占后,后面再来的顾客 不能进入系统接受服务。又可以分为以下两种: a) b) 损失制排队系统。当顾客到达系统时,如果所有的服务 均被占用,则自动离去,并不再回来。 混合制排队系统。等待制和损失制的结合,有以下三种: I. II. III. 队长有限,即系统的等待空间是有限的(即队长容量为K) 等待时间有限。即顾客在系统中的等待时间超过给定的 等待时间长度T后,即离去并不再回来。 逗留时间有限(等待时间和服务时间之和) 2. 排队及排队规则 a) 排队规则 ① 先来先服务(FCFS) ② 后来先服务(LCFS):如堆栈 ③ 具有优先权的服务(PS) 损失制和等待制都可以看成混合制的特殊情形。 如记s为系统中服务台的个数,则当K=s时,混合 制即成为损失制;当K=∞时,即为等待制。 11 12 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 2 2011/9/29 系统建模与仿真 排队系统 系统建模与仿真 ? 排队系统 ? 服务机制 排队系统的服务机制主要包括:服务员的数量及其 连接形式(串联或并联);顾客是单个还是成批接受服 务;服务时间的分布。在这些因素中,服务时间的分布 更为重要。常见的分布有: ? ? 定长分布(D):即每个顾客接受服务的时间是一个确定的 常数。 负指数分布(M):即每个顾客接受服务的时间相互独立, 具有相同的负指数分布: K阶爱尔朗分布(E k ):每个顾客接受服务的时间服务K阶爱尔朗 分布,其密度函数为 b(t ) ? k? (k? t ) k ? 1 ? k? t e (k ? 1)! (2.3) 爱尔朗分布比负指数分布更具有广泛的适应性。当k=1时,爱 尔朗分布为负指数分布;当k增加时,爱尔朗分布逐渐变为对称的。 事实上,当k≥30以后,爱尔朗分布近似于正态分布。当k→∞时, 由方差 K阶爱尔朗分布可看成完全随机(k=1)与完全非随机之间的分布, 能更广泛的适应于现实世界。 1 k? 2 ?? e ? ? b(t ) ? ? ? 0 t t?0 t?0 (2.2) 为可知,方差将趋近于零,即为完全非随机的。所以, 13 14 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 排队系统 系统建模与仿真 排队系统 (FIFS/LIFS) 四. 排队系统的符号表示 根据输入过程、排队规则和服务机制的变化对排队模型进行描 述或分类,可以给出很多的排队模型。为了方便对众多的模型的 描述,D.G.Kendall提出了一种目前在排队论中被广泛采用的 “Kendall 记号”,一般形式为: 四.排队系统的符号表示 1. 2. 3. M/M/1/∞/∞/FCFS M/M/1 M/M/s/K X/Y/Z/A/B/C X 表示顾客相继达到时间间隔的分布; Y Z A B C 表示服务时间的分布 表示服务台的个数 表示系统容量,即可容纳的最多顾客数 表示顾客源的数目 表示服务规则 15 16 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 排队系统的数据指标 系统建模与仿真 排队系统的数据指标 五.排队系统的主要数量指标和记号 研究排队系统的目的是通过了解系统的 运行的状况,对系统进行调整和控制,使系统 处于最优的运行状态。因此,首先需要弄清系 统的运行状况。描述一个排队系统的主要数量 指标有: 1. 2. 3. 队长和排队长 等待时间和逗留时间 忙期和闲期 ? 队长和排队长 1. 队长是指系统中的顾客数(排队等待的顾客 数与正在接受服务的顾客数之和), 2. 排队长是指系统中正在排队等待服务的顾客 数。 3. 队长和排队长一般都是随机变量。 17 18 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 3 2011/9/29 系统建模与仿真 排队系统的数据指标 系统建模与仿真 排队系统的数据指标 ? 等待时间和逗留时间 1. 等待时间:从顾客到达时刻起到他接受服务 止这段时间。 2. 逗留时间:从顾客到达时刻起到接受服务完 成止这段时间。 3. 等待时间、逗留时间都是随机变量 ? 忙期和闲期 1. 忙期是指从顾客到达空闲着的服务机构起, 到服务机构再次称为空闲止的这段时间 。 2. 闲期是与忙期相对的,是服务机构连续保持 空闲的时间。 3. 忙期和闲期都是随机变量 19 20 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 排队系统的数据指标 系统建模与仿真 排队系统的数据指标 ? 上述指标的常用记号 – N (t ) :时刻t 系统中的顾客数(又称为系统的状 态),即队长。 – N q (t ) :时刻t 系统中排队的顾客数,即排队长。 – T (t ) :时刻t 到达系统的顾客在系统中的逗留时 间。 – Tq (t ) :时刻t 到达系统的顾客在系统中的等待时 间。 ? 平衡状态下的指标 – 当系统达到平衡时处于状态n的概率,记为 ,又记: pn ? N:系统处于平衡状态时的队长,其均值为L,称为平均队长; ? N q :系统处于平衡状态时的排队长,其均值为,称为平均排队长; ? T :系统处于平衡状态时顾客的逗留时间,其均值为W,称为平均逗 留时间; ? T :系统处于平衡状态时顾客的等待时间,其均值为,称为平均等待 q 时间; ? ? ? n :当系统处于状态n时,新来顾客的平均到达率(单位时间内新来 到系统的平均顾客数); 服务完的顾客数); ? n :当系统处于状态n时,整个系统的平均服务率(单位时间内可以 21 22 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 排队系统的数据指标 系统建模与仿真 排队系统的数据指标 ? 系统的服务强度 当 ? 为常数时,记为 ? ;当每个服务台的平 n ? 忙期和闲期 – 忙期为B,闲期为I,平均忙期和平均闲期为 B ? 和 I ,s为系统中并行的服务台数。 ? 均服务率 ? 为常数时, 记每个服务台的服务率为 n ? ,则当 n ? s 时,有 ? n ? s? 。因此,顾客相继达到的 平均时间间隔为 1/ ? ,平均服务时间为 1/ ? 。令 ? ? ? / s? ,称 ? 为系统的服务强度。 23 24 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 4 2011/9/29 系统建模与仿真 排队系统的基本问题 系统建模与仿真 生灭过程 六. 排队系统研究的基本问题 排队系统研究的首要问题是排队系统的主要数量指标的概率规 律,即研究系统的整体性质,然后进一步研究系统的优化问题。 1. 2. 通过研究主要数据指标在瞬时或平衡状态下的概率分布及其数 字特征,了解系统运行的基本特征。 统计推断问题,建立适当的排队模型。在建立模型的过程中经 常会碰到如下问题:检验系统是否已经到达平衡状态;检验顾 客的相继达到时间间隔的相互独立性;确定服务时间的分布及 其参数等。 系统优化问题,又称为系统控制问题或系统运营问题,其基本 目的是使系统处于最优或最合理的状态。系统优化问题包括最 优设计问题和最优运营问题,其内容很多,有最少费用问题、 服务率控制问题、服务台的开关策略、顾客(或服务)根据优 先权的最优排序问题。 25 ? 生灭过程简介 一类非常重要且广泛存在的排队系统是生灭 过程排队系统。k8,生灭过程是一类特殊的随机过程, 在生物学、物理学、运筹学中有广泛的应用。在 排队系统中,如果用N(t)表示时刻t系统中的顾客 数,则{N(t),t≥0}就构成了一个随机过程。如 果用“生”表示顾客的到达,“灭”表示顾客的 离去,则对许多排队过程来说,{N(t),t≥0}就 是一类特殊的随机过程 - 生灭过程。 26 3. 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 生灭过程 系统建模与仿真 生灭过程 ? 定义 1: 设{N(t),t≥0}为一个随机过程。 若N(t)的概率分布有如下性质: 1. 假设N(t)=n,则从时刻t起到下一个顾客到达 的时刻止的时间服从参数为 ? n 的负指数分布, n=0,1,2,…。 2. 假设N(t)=n,则从时刻t起到下一个顾客离去 的时刻止的时间服从参数为 ? n 的负指数分布, n=0,1,2,…。 3. 同一时刻只有一个顾客到达或者离去。 ? 一般说来,得到N(t)的分布 p{N (t ) ? n}(n ? 0,1,2...) 是比较困难的,因此通常是求当系统达到 平衡状态后的状态分布,记为: pn, n ? 0,1,2,... 则称{N(t),t≥0}是一个生灭过程。 27 28 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 生灭过程 系统建模与仿线 ? 求解状态n的概率 pn, n ? 0,1,2,... 为求平稳分布,考虑系统可能处的任一状态n。 假设记录了一段时间内进入状态n和离开状态n的 次数,则因为“进入”和“离开”是交替发生的, 所以这两个数要么相等,要么相差为1。但就这两 种事件的平均发生概率是相等的。即当系统运行 相当时间到达平稳状态后,对任一状态n来说,单 位时间内进入该状态的平均次数和单位时间内离 开该状态的平均次数是相等的,这就是系统在统 计平衡下的“流入=流出”原理。根据这一原理, 可得到任一状态下的平衡方程如下: 29 ?0 p0 ? ? 2 p2 ? (?1 ? ?1 ) p1 ?1 p1 ? ?3 p3 ? (?2 ? ? 2 ) p2 ┇ (2.4) ?n?2 pn?2 ? ? n pn ? (?n?1 ? ? n?1 ) pn?1 n ?n?1 pn?1 ? ? n?1 pn?1 ? (?n ? ? n ) pn 30 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 5 2011/9/29 系统建模与仿线 系统建模与仿真 记: 生灭过程 Cn ? 0 1 ? ? ?? 1 p 2 ? 1 p1 ? ( ?1 p1 ? ?0 p0 ) ? 1 p1 ? 1 2 p0 ?2 ?2 ?2 ? 2 ?1 p3 ? ?n ?1?n 2 ...?0 ? n ? n ?1 ...?1 (2.5) 则平稳状态的分布为: 2 ? ?? ?2 p 2 ? 2 1 0 p0 ?3 ? 3 ? 2 ?1 ┇ p n ? C n p0 (2.6) 由概率的要求: ┇ n-1 ?p n ?0 ? n ?1 即: ?1 ? ? ? ?C n ?1 ? n ? ? p0 ? 1 ? pn ? ?n?1 ? ? ...? p n?1 ? n?1 n 2 0 p0 ?n ? n ? n?1 ...?1 ?n ? ? ...? p n ? n n?1 0 p0 ? n?1 ? n?1 ? n ...?1 31 于是: p0 ? 1 1 ? ? Cn n ?1 ? (2.7) n p n ?1 ? 32 北京邮电大学自动化学院物流工程 苏志远 北京邮电大学自动化学院物流工程 苏志远 系统建模与仿真 实验课安排 ? 以下周四上课时间在院办机房上课 1. 2. 3. 4. 5. 6. 10.13 10.20 11.3 11.10 11.24 12.22 ? 或者上网查询: 1. 自动化学院的网址上找“实验课表查询” 2. 北京邮电大学自动化学院物流工程 苏志远 6