《第八章 排队论.ppt》由会员分享，可在线阅读，更多相关《第八章 排队论.ppt（112页珍藏版）》请在金锄头文库上搜索。
1、第七章连续时间马尔科夫过程 第七章连续时间马尔科夫过程 7 1 Ito过程 7 2 增量过程 7 3 泊松过程 7 4 排队论与生灭过程 7 4 排队论与生灭过程 排队论 Queuingtheory 又称随机服务系统 是通过研究各种服务系统在排队等待现象中的概率特性 解决服务系统最优设计与最优控制的一种理论 4 排队论起源于20世纪初的电话通话 909 1920年丹麦数学家 电气工程师爱尔朗 A K Erlang 用概率论方法研究电话通话问题 20世纪30年代 费勒 W Feller 引进了生灭过程20世纪50年代 D G Kendall用嵌入马尔柯夫链方法研究排队论 7 4 排队论与生灭过程
2、 7 4 排队论与生灭过程 排队系统的例子 1 单服务台单队 图7 4 1单服务台单队系统 7 4 排队论与生灭过程 根据服务台的数量及排队方式 排队系统可以分为四类 2 多服务台单队 顾客到达 服务台 顾客离去 服务台 服务台 图7 4 2多服务台单队系统 7 4 排队论与生灭过程 根据服务台的数量及排队方式 排队系统可以分为四类 3 多队多服务台 图7 4 3多服务台多队系统 顾客到达 服务台 顾客离去 服务台 服务台 7 4 排队论与生灭过程 根据服务台的数量及排队方式 排队系统可以分为四类 4 多服务台串联服务 图7 4 4多服务台串联系统 顾客到达 顾客离去 7 4 排队论与生灭过程
3、 根据服务台的数量及排队方式 排队系统可以分为四类 排队过程的组成部分 实际中的排队系统各有不同 但概括起来都由三个基本部分组成 输入过程 排队及排队规则 服务机制 7 4 排队论与生灭过程 排队过程的组成部分 1 输入过程 1 顾客总体数 又称顾客源 输入源 顾客源可以是有限的 也可以是无限的 如到售票处购票的顾客总数可以认为是无限的 而某个工厂因故障待修的机床则是有限的 7 4 排队论与生灭过程 排队过程的组成部分 1 输入过程 1 顾客总体数 又称顾客源 输入源 2 顾客到达的形式 单个到达 还是成批到达 如大学生到图书馆借书是单个到达 而购买的材料入库则可以看成成批到达 7 4 排队论
4、与生灭过程 排队过程的组成部分 1 输入过程 顾客总体数 又称顾客源 输入源 顾客到达的形式 顾客流的概率分布 即单位时间内到达的顾客数 也可用顾客相继到达的时间间隔描述 这是刻画输入过程的最重要的内容 排队论中常用的分布 定长分布 D 这种分布顾客相继到达的时间间隔是确定的 如产品通过传送带进入包装箱就是定长分布的例子 泊松流 M 在一定时间区间内 恰好到达k个顾客的概率仅与区间长度有关 而与区间起始时刻无关 7 4 排队论与生灭过程 排队过程的组成部分 2 排队规则 排队系统 7 4 排队论与生灭过程 排队分为有限排队和无限排队两类 前者是指系统的空间是有限的 当系统被占满时 后面再来的顾
5、客将不能进入系统 后者是指系统中的顾客数可以是无限的 队列可以排到无限长 顾客到达后均可进入系统排队或接受服务 具体又分为 等待制 即无限排队 损失制 这种系统是指排队空间为零的系统 实际上是不允许排队 当顾客到大系统时 如果所有服务台均被占用 则自动离去 并不再回来 这部分顾客就被损失掉了 混合制 该系统是等待制和损失制系统的结合 一般是指允许排队 但又不允许队列无限长下去 排队过程的组成部分 2 排队规则 排队规则 7 4 排队论与生灭过程 先来先服务 FCFS 后来先服务 LCFS 在许多库存系统中会出现这种情形 如钢板存入仓库后 需要时总是从最上面的取出 又如在情报系统中 后来到达的信
6、息往往更加重要 应首先加以分析和利用 具有优先权的服务 PS 如病危的患者应优先治疗 加急的电报电话应优先处理等 随机服务 SIRO 排队过程的组成部分 3 服务机制 服务员的数量及构成形式 7 4 排队论与生灭过程 从数量上说 服务台有单台和多台之分 从构成形式上看 有单队单服务台式 单队多服务台并联式 多队多服务台并联式 单队多服务台串联式等 排队过程的组成部分 3 服务机制 服务员的数量及构成形式 7 4 排队论与生灭过程 服务方式 指在某一时刻接受服务的顾客数 有单个服务和成批服务两种 排队过程的组成部分 3 服务机制 服务员的数量及构成形式 7 4 排队论与生灭过程 服务方式 服务时
7、间的分布 定长分布 D 指每个顾客接受服务的时间是一个确定的常数 排队过程的组成部分 3 服务机制 服务员的数量及构成形式 7 4 排队论与生灭过程 服务方式 服务时间的分布 定长分布 D 负指数分布 M 负指数概率分布能较好地描述一些排队系统里服务时间的概率分布情况 在负指数分布里 服务时间小于或等于时间长度t的概率 F t P 服务时间 t 1 e t这里的 为单位时间里被服务完的平均顾客数 排队过程的组成部分 3 服务机制 服务员的数量及构成形式 7 4 排队论与生灭过程 服务方式 服务时间的分布 定长分布 D 负指数分布 M K阶爱尔朗分布 K阶爱尔朗分布设X1 X2 Xk是k个互相独
8、立的 具有相同参数 的负指数分布随机变量 则随机变量 X X1 X2 X3 Xk服从k阶爱尔朗分布 X的密度函数为 随机变量X的均值和方差分别为 E X 1 Var X 1 k 2如果顾客连续接受串联的k个服务台的服务 各服务台的服务时间相互独立 且均服从参数为 的负指数分布 则顾客接受k个服务台总共所需的时间就服从k阶爱尔朗分布 7 4 排队论与生灭过程 当一个排队服务系统开始运转时 系统状态很大程度上取决于系统的初始状态和运转经历的时间 但过了一段时间后 系统的状态将独立于初始状态及经历的时间 这时称系统处于平稳状态 由于对系统的瞬时状态研究分析起来很困难 所以排队论中主要研究系统处于平稳
9、状态的工作情况 排队过程的平稳状态 7 4 排队论与生灭过程 X Y Z A B C这里的X记顾客相继到达的时间间隔的分布 M表示服从泊松分布或负指数分布 D表示定长分布 Ek表示爱尔朗分布 G表示一般相互独立任意分布 Y记服务时间的分布 类型同X Z记服务台数目 取正整数 A记系统的容量 表示系统中顾客容量限额 若系统中有k个等待位子 0 k 当k 0时 说明系统不允许等待 即为损失制 k 为等待制系统 k为有限整数时 则为混合制 B记顾客源的数目 可取正整数或 即有限与无限 C记排队服务规则 FCFS先到先服务 LCFS后到先服务 SIRO随机服务 PR有优先权的服务 排队过程的符号表示
10、7 4 排队论与生灭过程 研究排队系统的目的是通过了解系统运行的状况 对系统进行调整和控制 使系统处于最优运行状态 因此 首先需要弄清系统的运行状况 描述一个排队系统运行状况的主要数量指标有 Pn 系统中恰好有n个顾客的概率 这n个顾客包括排队和正在被服务的顾客 在系统里没有顾客的概率 即所有服务设施空闲的概率 记为P0 Pw顾客到达系统时 得不到及时服务 必须排队等待服务的概率 7 4 排队论与生灭过程 排队过程的主要数量指标 Ls在系统里的平均顾客数 包括排队的顾客数和正在被服务的顾客数 Lq排队的平均长度 即排队的平均顾客数 Wq平均一位顾客花在排队上的时间 Ws平均一位顾客在系统里的平
11、均逗留时间 它包括排队时间和被服务的时间 Little公式 L W 为单位时间内到达的顾客数 7 4 排队论与生灭过程 排队过程的主要数量指标 生灭过程生灭过程是一类非常简单具有广泛应用的一类随机过程 很多排队模型中都假设其状态过程为生灭过程 这样的排队子系统如 M M C和M M C R 我们也可称之为生灭过程的排队系统 在这样的排队系统中 一个新顾客的到达看作 生 一个顾客服务完之后离开系统看作是 死 设N t 的任意时刻t排队系统的状态 即排队子系统中的总顾客数 则对M M C K系统N t 具有有限个状态0 1 k 对M M C来说N t 具有可列个状态0 1 2 7 4 排队论与生灭
12、过程 生灭过程排队论 若排队系统具有下列性质 1 顾客到达为泊松流 时间间隔服从参数为 n的负指数分布 2 顾客服务时间服从参数为 n的负指数分布 则排队系统的随机过程 N t t 0 具有马尔可夫性质 为一个生灭过程 7 4 排队论与生灭过程 生灭过程排队论 设某系统具有状态集S 0 1 2 或S 0 1 2 k N t 表示系统在时刻t t 0 的状态 若在N t n的条件下 随机过程 N t t 0 满足以下条件 1 N t t 转移到 n 1 的概率为Pn n 1 t n t 2 N t t 转移到 n 1 的概率为Pn n 1 t n t 3 N t t 转移到其他状态 S n 1
13、n 1 的概率为o t 高阶无穷小 则称随机过程 N t t 0 为生灭过程 Definition7 2 Birth deathprocess 7 4 排队论与生灭过程 生灭过程排队论 1 在无穷小 t内 系统或生长1个 或灭亡1个 或既不生长又不灭亡的概率 1 n t n t 2 系统生长一个的概率 n t 与 t有关 而与t无关 与系统当前状态n有关 而与以前的状态无关 3 系统灭亡一个的概率 n t 与 t有关 而与t无关 与系统当前状态n有关 而与以前的状态无关 马尔可夫性 生灭过程状态变化的性质 7 4 排队论与生灭过程 生灭过程排队论 生灭过程的状态平衡方程 状态 输入率 输出率
14、0 1 2 n 1 n 7 4 排队论与生灭过程 生灭过程排队论 生灭过程的跳跃强度矩阵 7 4 排队论与生灭过程 生灭过程排队论 生灭过程的状态转移图 无限状态的 m个状态的 7 4 排队论与生灭过程 生灭过程排队论 排队系统状态转移图 生灭过程的稳态概率 一般来说 得到N t 的分布Pn t P N t n n 0 1 2 是比较困难的 因此通常是求当系统运行一段时间达到平稳状态后的状态分布 记为Pn 当系统运行长时间达到平稳状态后 对于任一个状态n 单位时间内进入该状态的平均次数和单位时间离开该状态的平均次数应该相等 这就是系统的统计平衡下的 流入 流出 原理 7 4 排队论与生灭过程
15、生灭过程排队论 2 生灭过程稳态方程 输入 出 率 某一稳态概率 平均转换率 2 生灭过程稳态方程 方程为 由此可求得生灭过程的平稳状态分布 由于 即有 即有 即有 7 4 排队论与生灭过程 生灭过程排队论 即当 时 此生灭过程存在平稳状态分布 7 4 排队论与生灭过程 生灭过程排队论 基于生灭过程的排队系统的六个模型 3 M M 1 m FCFS 单服务台无限队列 到达过程 服务时间 系统容量 顾客源 排队规则 M M 1 FCFS 单服务台无限队列 2 M M 1 N FCFS 单服务台无限队列 5 M M s N FCFS 4 M M s FCFS 6 M M s m FCFS 7 4
16、排队论与生灭过程 生灭过程排队论 设单位时间到达系统的顾客数为 单位时间被服务完的顾客数为 由于是单服务台 且顾客源无限 因此 在各种状态的情况下 系统的 出生率 为 系统的 死亡率 为 系统在稳态情况下的状态转移如图9 6所示 图9 6 7 4 排队论与生灭过程 生灭过程排队论 根据以上状态转移图 可以得出如下平衡方程 系统状态概率Pn t 的计算 状态 输入率 输出率 0 1 2 n 1 n 7 4 排队论与生灭过程 生灭过程排队论 根据平衡方程 可递推得到各状态概率为 系统状态概率Pn t 的计算 状态 概率 0 1 2 n 1 n 7 4 排队论与生灭过程 生灭过程排队论 上面两式做差 得 表示平均到达率与平均服务率之比 称为服务强度 系统状态概率Pn t 的计算 7 4 排队论与生灭过程 生灭过程排队论 根据平衡方程 可递推得到各状态概率为 系统状态概率Pn t 的计算 状态 概率 0 1 2 n 1 n 7 4 排队论与生灭过程 生灭过程排队论 高速公路收费处设有一个收费通道 汽车到达服从泊松分布 平均到达速率为150辆 小时 收费时间服从负指数分布 平均收费时间为15秒
