新闻资讯

<主页 > 新闻资讯 >

排队系统_图文_

发布日期:2020-05-16 23:55

  排队系统 通信1班 王锐 1.排队论系统的起源 2.排队论系统的概念 目 录 3. Little公式 4. M/M/1 5.一般混合制的M/M/S(n)系统 6.排队系统的应用 7.例题赏析 1. 排队论的起源 ? 日常生活中存在大量有形和无形的排队或拥挤现象,如旅客购票排队,市 内电话占线等现象。排队论的基本思想是1910年丹麦电话工程师A.K.埃尔朗在 解决自动电话设计问题时开始形成的,当时称为话务理论。他在热力学统计平 衡理论的启发下,成功地建立了电话统计平衡模型,并由此得到一组递推状态 方程,从而导出著名的埃尔朗电线世纪初以来,电话系统的 设计一直在应用这个公式。30年代苏联数学家А.Я.欣钦把处于统计平衡的电话 呼叫流称为最简单流。瑞典数学家巴尔姆又引入有限后效流等概念和定义。他 们用数学方法深入地分析了电话呼叫的本征特性,促进了排队论的研究。50年 代初,美国数学家关于生灭过程的研究、英国数学家D.G.肯德尔提出嵌入马尔 可夫链理论,以及对排队队型的分类方法,为排队论奠定了理论基础。在这以 后,L.塔卡奇等人又将组合方法引进排队论,使它更能适应各种类型的排队问 题。70年代以来,人们开始研究排队网络和复杂排队问题的渐近解等,成为研 究现代排队论的新趋势。 2. 排队系统的概念 在实际应用中,有一大类系统被称之为随机服务系统或排队系统。在这些系统中顾 客到来的时刻与服务时间的长短都是随机的,并且可能会随不同的条件而变化,因而 服务系统的状况也是随机的,会随各种条件而波动。在电信网络中,交换机就可以看 成是一种随机服务系统。对于不同的电信网络,可以使用不同的排队系统模拟不同的 电信业务交换机进行分析。模拟这些系统的排队系统的状态变化实际上是一个生灭过 程。 到来的顾客流 队列 离开的顾客流 服务员 服务机构 图1.排队系统模型 ? 要仔细描述一个排队系统,主要需要描述三个方面的内容:输入过程、服务 时间、排队方式等。下面使用一个随机点移动模型来说明关于排队系统的模型 和假设。 t1 t2 服务员 队列 服务机构 τ1 τ2 图2 排队系统的点移动模型 如果只有一个服务员,在轴上有一些点从左向右做同 速率的匀速直线….表示顾客到达排队系 统的到达间隔,它们均为随机变量;在系统忙时,τ1, τ2…表示不同顾客的服务时间,它们也是随机变量,关于 ti和τi满足下面3个假设: (1)ti独立同分布; (2)τi独立同分布; (3)ti和τi独立。 不同排队系统的记法 排队系统的分析希望指标 采用肯德尔(D.G.Kendall)的记号A/B/C/D/E。 A表示输入过程;B表示服务时间;C表示服务 数目;D表示系统的容量;E表示排队规则,其 中D/E的缺省表示容量无限大和FIFO方式。 ? ? ? (1)队长。队长分布或其各种统计值及其 估计。 (2)等待时间。等待时间分布或其各种统 计值及其估计。 (3)忙期。即服务机构连续繁忙的时期 图3 排队系统模型 3. Little公式 Little 公式描述了任意排队系统满足的关系,下面通过简单描述来说明该公式。 下 面考虑一个任意的排队系统,为了说明 Little 公式,首先定义:A(t)为在(0,t ) 内到达的顾客数;B(t)为在(0,t)内离开的顾客数;那么t时刻系统内的顾客数为 N(t)=A(t)-B(t) 图4到达过程A(t)和离开过程B(t) 列德尔(Little)公式 ? 如果N 表示系统中的平均顾客数,T 表示顾 客在系统中的平均时间(这个时间 有时也 被称为系统时间),λ 表示单位时间到达系 统的顾客数,对于任意排队系统,有 N= T λ 上面结论可以证明对于 任意排队系统都是正确的,直观意义就是 一种平衡关系。 公式证明过程 MM1概述: ? 4 . M/M/1 假设一个随机过程的到达过程是一个参数为λ 的 Poisson 过程,服务时间是参数为? 的负指 数分布,等待的位置有无穷多个,排队的方式是 FIFO,则这个随机过程是 M/M/1。M/M/1 是 简单的排队系统,k8下面通过对这个系统的分析来加深 对排队系统的了解。在求得 M/M/1 的队 长分布和系统时间分布后,对 M/M/1 的稳态分析就基本完 成。在对数据网络进行分析时,将 使用 M/M/1 系统对数据交换机的一个端口进行 建模。 如果到达过程不是 Poisson 过程,或服 务时间不是负指数分布,排队系统的分 析就要复杂一些。在 M/G/1 或 G/M/1 中,为了消除残 余分布的影响,使用嵌入马 尔可夫链来替代连续时间马尔可夫链进行分析。对于 G/G 系统的 分析就更加复杂 和困难。 排队系统除了稳态分析,还有瞬态分析等内容。瞬态分析考虑初始 值的影响, 由于分析依赖微分方程组而稳态分析依赖于线性方程组,瞬态分析的研究将比稳 态分析复杂许多。 定理 2-5:M/M/1 排队系统在稳态时,系统时间 s 服从参数为 λ? ? 的负指数分布。 证明过程 5.一般混合制的M/M/S(n)系统 现在考虑一般的排队系统,这个系统有s个服务员,但系统的容量为n。 呼叫在到达系统时,如果有任何一个空闲的中继线,可以立刻得到服务, 而系统如果已有n个呼叫,新到的呼叫会被拒绝。如果到达的呼叫流为参 数λ的Poisson过程,服务时间服从参数为μ的负指数分布,这个系统是一个 生灭过程。 ? ? 0 ? 1 2? 2 .... k? ? k .... ? s s? .... s? ? n 图3.9 M / M / s(n)状态转移图 6.排队模型的应用 ? 在通信、交通、港口泊位设计、机器维修、库存控制、计算机设计 等各个领域中排队论都获得了广泛应用。 ? ? 通信系统仍然是排队论应用的主要领域,也是其发展的重要推动力 量。经过通信、计算机和应用数学三个领域的研究学者的努力研究, 排队论得到了迅速的发展。 在宽带综合业务数字网中,异步传送模式,统计复用,随机多址接 入中都涉及到许多排队论问题,而且正在研究解决中,如ATM业务 流的数学模型及其排队分析方法。 使用MATLAB分析排队论 由于排队论模型设计大量的数据计算和分析,所以我们可以用MATLAB来进行相关分析。 MATLAB软件具有高精确度、高可靠性的特点,它提供了强大的科学运算、灵活的程序设计 流程、高质量的图形可视化与界面设计、便携的与其他语言程序和语言的接口功能。所以 我们利用MATLAB开发环境实现排队论中一些常用模型的工具箱开发是非常有必要的。 7. 例题赏析 例:验证M/M/1的状态变化为一个生灭过程 谢谢观看!