Ch排队论课件.ppt

Queuingtheory 第九章排队论 运筹学OperationsResearch 9 1排队论的基本概念9 2排队系统常用分布9 3单服务台模型 M M 1 9 4多服务台模型 M M s 9 5其它服务时间分布模型9 6排队系统的优化 9 1排队论的基本概念 2020年1月30日星期四 9 1 1排队系统的描述 排队系统的例子 9 1排队论的基本概念BasicConceptsofQueuingtheory 2020年1月30日星期四 排队的过程可表示为 9 1排队论的基本概念BasicConceptsofQueuingtheory 2020年1月30日星期四 根据服务台的数量及排队方式 排队系统可以分为 1 单服务台单队 2 多服务台单队 图9 2单服务台单队系统 顾客到达 服务台 顾客离去 服务台 服务台 图9 3多服务台单队系统 9 1排队论的基本概念BasicConceptsofQueuingtheory 2020年1月30日星期四 3 多队多服务台 4 多服务台串联服务 图9 4多服务台多队系统 图9 5多服务台串联系统 9 1排队论的基本概念BasicConceptsofQueuingtheory 顾客到达 服务台 顾客离去 服务台 服务台 顾客到达 顾客离去 2020年1月30日星期四 9 1 2排队系统的基本组成 排队系统由输入过程 服务规则和服务台三个部分组成 这是指要求服务的顾客按怎样的规律到达排队系统的过程 有时也称之为顾客流 1 顾客总体数 又称顾客源 输入源 顾客源可以是有限的 也可以是无限的 2 顾客到达的形式 这是描述顾客是怎样来到系统的 是单个到达 还是成批到达 3 顾客流的概率分布 或称顾客相继到达的时间间隔分布 这是首先需要确定的指标 9 1排队论的基本概念BasicConceptsofQueuingtheory 1 输入过程 2020年1月30日星期四 1 先到先服务 FCFS FirstComeFirstServe 2 后到先服务 LCFS LastComeFirstServe 3 有优先权的服务 PR Priority 4 随机服务 SIRO ServiceinRandomOrder 9 1排队论的基本概念BasicConceptsofQueuingtheory 2 排队规则 1 等待制指顾客到达系统后 所有服务台都不空 顾客加入排队行列等待服务 一直等到服务完毕以后才离去 2 损失制指当顾客到达系统时 所有服务台都已被占用 顾客不愿等待而离开系统 2020年1月30日星期四 3 混合制这是等待制与损失制相结合的一种服务规则 一般是指允许排队 但又不允许队列无限长下去 大体有以下三种 队长有限 当等待服务的顾客人数超过规定数量时 后来的顾客就自动离去 另求服务 即系统的等待空间是有限的 等待时间有限 即顾客在系统中的等待时间不超过某一给定的长度T 当等待时间超过时间T时 顾客将自动离去 并不再回来 逗留时间 等待时间与服务时间之和 有限 9 1排队论的基本概念BasicConceptsofQueuingtheory 2020年1月30日星期四 1 服务台数量及构成形式从数量上说 服务台有单台和多台之分 从构成形式上看 有单队单服务台式 单队多服务台并联式 多队多服务台并联式 单队多服务台串联式等等 如图9 2到9 5所示 2 服务方式指在某一时刻接受服务的顾客数 有单个服务和成批服务两种 3 服务时间的分布在多数情况下 对某一个顾客的服务时间是一随机变量 与顾客到达的时间间隔分布一样 服务时间的分布有定长分布 负指数分布 爱尔朗分布等等 3 服务台 9 1排队论的基本概念BasicConceptsofQueuingtheory 服务台可以从以下三个方面来描述 2020年1月30日星期四 9 1 3排队系统的主要数量指标 记号和符号 9 1排队论的基本概念BasicConceptsofQueuingtheory 1 队长和队列长 排队长 队长是指系统中的顾客数 排队等待的顾客数与正在接受服务的顾客数之和 队列长是指系统中正在排队等待服务的顾客数 队长和队列长一般都是随机变量 2 等待时间和逗留时间从顾客到达时刻起到他开始接受服务止这段时间称为等待时间 从顾客到达时刻起到他接受服务完止这段时间称为逗留时间 两种时间都是随机变量 3 忙期和闲期忙期是指从顾客到达空闲着的服务机构起 到服务再次成为空闲止的这段时间 服务机构连续忙的时间 这是个随机变量 与忙期相对的是闲期 即服务机构连续保持空闲的时间 1 主要数量指标 2020年1月30日星期四 9 1排队论的基本概念BasicConceptsofQueuingtheory 2 记号 时刻t系统中的顾客数 又称为系统的状态 即队长 时刻t系统中排队的顾客数 即列队长 时刻t到达系统的顾客在系统中的逗留时间 时刻t到达系统的顾客在系统中的等待时间 L 平均队长 即稳态系统任一时刻顾客数的期望值 Lq 平均等待队长 即稳态系统任一时刻等待服务的顾客数的期望值 W 平均逗留时间 即在任一时刻进入稳态系统的顾客逗留时间的期望值 Wq 平均等待时间 即在任一时刻进入稳态系统的顾客等待时间的期望值 在平稳状态下 2020年1月30日星期四 9 1排队论的基本概念BasicConceptsofQueuingtheory 顾客到达的平均速率 即单位时间内平均到达的顾客数 1 平均到达时间间隔 平均服务速率 即单位时间内服务完毕离去的顾客数 1 平均服务时间 s 系统中服务台的个数 服务强度 即每个服务台单位时间内的平均服务时间 一般有 s N 稳态系统任一时刻的状态 即系统中所有顾客数 U 任一顾客在稳态系统中的逗留时间 Q 任一顾客在稳态系统中的等待时间 Pn P N n 稳态系统任一时刻状态为n的概率 特别当n 0时 Pn P0 即稳态系统所有服务台全部空闲的概率 e 有效平均到达率 即期望每单位时间内来到系统 包括未进入系统 的概率 2020年1月30日星期四 3 排队系统的符号 一个排队系统的特征可以用六个参数表示 形式为 X Y Z A B C 或X Y Z A B C其中X 顾客到达的概率分布 可取M D Ek G等 Y 服务时间的概率分布 可取M D Ek G等 Z 服务台个数 取正整数 A 排队系统的最大容量 可取正整数或 B 顾客源的最大容量 可取正整数或 C 排队规则 可取FCFS LCFS等 例如 M M 1 FCFS 表示顾客到达的时间间隔是负指数分布 服务时间是负指数分布 一个服务台 排队系统和顾客源的容量都是无限 实行先到先服务的一个服务系统 9 1排队论的基本概念BasicConceptsofQueuingtheory 2020年1月30日星期四 下一节 排队系统常用分布 9 1排队论的基本概念BasicConceptsofQueuingtheory 9 2排队系统常用分布 2020年1月30日星期四 9 2 1负指数分布 随机变量T服从负指数分布 其分布函数为 密度函数为 T的期望值为 T的方差为 9 2排队系统常用分布 2020年1月30日星期四 负指数分布具有性质 1 密度函数 对时间t严格递减 2 无记忆性或马尔柯夫性 即 3 当顾客到达过程是泊松流时 顾客相继到达的间隔时间T必服从负指数分布 这个性质将在定理9 1中予以证明 若随机变量X的概率密度为 9 2 2泊松分布 则称X服从参数为 的泊松 Poisson 分布 记为X P 其均值和方差分别为 9 2排队系统常用分布 2020年1月30日星期四 定义9 1 对于随机过程 若满足 1 Poisson流的定义 9 2顾客到达和服务的时间分布 1 独立增量性 无后效性 即对任意n个参数增量相互独立或者说不相交的时间区间内到达的顾客数互相独立 2 增量平稳性即在长度为t的时间区间内恰好到达k个顾客的概率仅与区间长度t有关 而与区间起始点无关 3 普遍性即当t充分小时 有 称为Poisson过程 N t 服从泊松分布 2020年1月30日星期四 2排队系统与泊松过程 9 2顾客到达和服务的时间分布 若N t 为时间区间 0 t t 0 内到达系统的顾客数 则N t 是一个随机变量 且 N t t 0 T 为一个随机过程 若该随机过程满足 1 在不相重叠的区间内 顾客的到达数是相互独立的 2 在时间区间 t t t 内有顾客的到达数只与区间长度 t有关 而与区间起始点t无关 3 对于充分小的 t 在时间区间 t t t 内有2个或2个以上的顾客到达的概率极小 以致于可以忽略 则认为顾客到达系统的过程是泊松过程 且 2020年1月30日星期四 9 2顾客到达和服务的时间分布 如果一个随机变量 概率分布与时间t有关 则称这个随机变量为一随机过程 排队系统中顾客到达的个数就是一个随机过程 定理9 1 在排队系统中 如果到达的顾客数服从以 t为参数的泊松分布 则顾客相继到达的时间间隔服从以 为参数的负指数分布 证明参看教材 由定理9 1可以看出 到达的顾客数是一个以 为参数的泊松流 与 顾客相继到达的时间间隔服从以为参数的负指数分布 两个事实是等价的 2020年1月30日星期四 定理9 2 设X1 X2 Xk 是k个互相独立的 具有相同参数 的负指数分布随机变量 则随机变量 服从k阶爱尔朗 Erlang 分布 X的密度函数为 记为 或简记为 随机变量X的均值和方差分别为 9 2排队系统常用分布 2020年1月30日星期四 为单位时间平均到达顾客数目 亦称平均到达率 顾客到达服从泊松分布 亦称顾客到达形成泊松流 最简单流 例1 一台仪表由1000个元件组成 每个元件在一年工作时间内发生故障的概率为0 001 并且与其它元件的状况无关 求在一年内不少于2个元件发生故障的概率 解 设X 元件发生故障个数 由于n 1000P 0 001很小 可视发生故障服从泊松分布 其中 nP 1因此 9 2顾客到达和服务的时间分布 2020年1月30日星期四 下一节 单服务台模型 9 2顾客到达和服务的时间分布 9 3单服务台模型 M M 1 2020年1月30日星期四 9 3单服务台模型 9 3 1基本模型 设单位时间到达系统的顾客数为 单位时间被服务完的顾客数为 由于是单服务台 且顾客源无限 因此 在各种状态的情况下 系统的 出生率 为 系统的 死亡率 为 系统在稳态情况下的状态转移如图9 6所示 图9 6 根据以上状态转移图 可以得出如下平衡方程 9 1 9 2 1系统状态概率Pn t 的计算 2020年1月30日星期四 9 3单服务台模型 由 9 1 和 9 2 可以递推求解P1 P2 Pn 得到 9 3 9 4 表示平均到达率与平均服务率之比 称为服务强度 2020年1月30日星期四 9 3单服务台模型 例9 1 高速公路收费处设有一个收费通道 汽车到达服从泊松分布 平均到达速率为150辆 小时 收费时间服从负指数分布 平均收费时间为15秒 辆 求 1 收费处空闲的概率 2 收费处忙的概率 3 系统中分别有1 2 3辆车的概率 解 根据题意 150辆 小时 1 15秒 1 240 小时 辆 即 240 辆 小时 150 240 5 8 则有 1 系统空闲的概率为 P0 1 1 5 8 3 8 0 375 2 系统忙的概率为 1 P0 5 8 0 625 3 系统中有1辆车的概率为 P1 1 0 625 0 375 0 234系统中有2辆车的概率为 P2 2 1 0 234 0 625 0 146系统中有3辆车的概率为 P3 3 1 0 146 0 625 0 091 2020年1月30日星期四 2 系统的运行指标 1 系统中的平均顾客数 系统中顾客数的期望值 L 即队长为系统中顾客数的期望值 系统中各种状态的加权平均值 2 队列中的平均顾客数 9 3单服务台模型 2020年1月30日星期四 9 3单服务台模型 3 顾客在系统中的平均逗留时间W 9 8 4 顾客在队列中的平均逗留时间Wq 9 9 9 10 Little公式 2020年1月30日星期四 9 3单服务台模型 例9 2 轻轨进站口售票处设有一个售票窗口 乘客到达服从泊松分布 平均到达速率为200人 小时 售票时间服从负指数分布 平均售票时间为15秒 人 求L Lq W和Wq 解 根据题意 200人 小时 240人 小时 5 6 2020年1月30日星期四 9 3单服务台模型 9 3 2有限队列模型 如果系统的最大容量为N 对于单服务台的情形 排队等待的顾客最多为N 1 在某一时刻一顾客到达时 如系统中已有N个顾客 那么这个顾客就被拒绝进入系统 系统状态转移如图9 7 图9 7 1 系统状态概率的计算 2020年1月30日星期四 9 3单服务台模型 由状态转移图9 7 建立系统概率平衡方程如下 9 11 9 12 9 13 2020年1月30日星期四 9 3单服务台模型 9 14 9 15 2020年1月30日星期四 9 3单服务台模型 根据式9 12和9 13可以导出系统的各个指标 对于 1 有 9 16 1 系统中的平均顾客数L 2020年1月30日星期四 9 3单服务台模型 9 17 2 队列中的平均顾客数Lq 9 18 e称为有效到达率 即单位时间内到达并能进入队列的平均顾客数 e称为有效服务强度 2020年1月30日星期四 9 3单服务台模型 3 顾客在系统中的平均逗留时间W 9 19 4 顾客在队列中的平均逗留时间 9 20 2020年1月30日星期四 9 3单服务台模型 例9 3 咨询中心有一位咨询工作人员 每次只能咨询一人 另外有4个座位供前来咨询的人等候 某人到来发现没有座位 就不再等待而离去 前来咨询者到达服从泊松流 到达的平均速率为4人 小时 咨询人员的平均咨询时间为10分钟 人 咨询时间服从负指数分布 求 1 咨询者到达不用等待就可咨询的概率 2 咨询中心的平均人数以及等待咨询的平均人数 3 咨询者来咨询中心一次平均花费的时间以及平均等待的时间 4 咨询者到达后因客满而离去的概率 5 增加一个咨询工作人员可以减少的顾客损失率 解 N 4 1 5 4人 小时 6人 小时 2 3 1 2020年1月30日星期四 9 3单服务台模型 2 3 4 因客满而离去的概率为0 048 5 当N 6时 2020年1月30日星期四 9 3单服务台模型 即增加一个咨询工作人员可以减少顾客损失率1 6 9 3 3有限顾客源模型 设顾客总数为m 当顾客需要服务时 就进入队列等待 服务完毕后 重新回到顾客源中 如此循环往复 由于顾客源的数量有限 因此队列的长度也是有限的 并且队列的长度必定小于顾客源总数 有限源系统顾客的平均到达速率 2020年1月30日星期四 9 3单服务台模型 0 1 2 n 1 n n 1 m 1 m 图9 8有限顾客源模型状态转移图 状态转移图如图9 8 由图9 8得到系统稳态概率平衡方程组 1 系统状态概率的计算 9 21 2020年1月30日星期四 9 3单服务台模型 用递推方法解该方程组 得到 9 22 9 23 2有限源系统的运行指标 在求得系统中出现顾客数的概率后 即可求得系统的运行指标 推导过程略 2020年1月30日星期四 9 3单服务台模型 9 24 9 25 9 26 9 27 在机器维修问题中 L是待检修及正在检修的平均机器数 而 表示正常运行的平均机器数 2020年1月30日星期四 9 3单服务台模型 例9 4 某车间有5台机器 每台机器的连续运转时间服从负指数分布 一天 8小时 平均连续运行时间120分钟 有一个修理工 每次修理时间服从负指数分布 平均每次96分钟 求 1 修理工忙的概率 记为Pb 2 五台机器都出故障的概率 3 出故障的平均台数 4 平均停工时间 5 平均等待修理时间 6 评价这个系统的运行情况 解 一天为一个单位时间 认为一天内来修理的机器数平均为4台 修理工一天平均修理机器数为5台 m 5 4 5 0 8 2020 1 30 45 可编辑 2020年1月30日星期四 9 3单服务台模型 由计算结果看出 系统的修理工几乎没有空闲时间 机器的停工时间是平均运行时间的三倍 系统的服务效率很低 2020年1月30日星期四 9 3单服务台模型 作业 教材P216T1 2 3 4 5 6 下一节 9 4多服务台模型 9 4多服务台模型 M M s 2020年1月30日星期四 9 4多服务台模型 9 4 1基本模型 规定各服务台工作相互独立且服务速率相同 系统的平均服务速率为s 令 0 1 2 s 1 s s 1 n 1 n 图9 9基本模型状态转移图 系统的状态转移图9 9 2020年1月30日星期四 9 4多服务台模型 稳态概率方程 9 28 9 29 9 30 9 31 9 32 9 33 2020年1月30日星期四 9 4多服务台模型 顾客需要等待 系统已有s个顾客 的概率 与单服务台系统的方法类似 有 2020年1月30日星期四 9 4多服务台模型 例9 5 银行办理个人储蓄业务有三个窗口 顾客到达服从泊松流 到达速率为0 9人 分 办理业务时间服从负指数分布 每个窗口的平均服务速率为0 4人 分 顾客到达后取得一个排队号 依次由空闲窗口按号码顺序办理储蓄业务 求 1 所有窗口都空闲的概率 2 平均队长 3 平均等待时间及逗留时间 4 顾客到达后必须等待的概率 1 所有窗口都空闲的概率 即求P0 2020年1月30日星期四 2 平均队长 先求Lq 再求L 3 平均等待时间和平均逗留时间 即求Wq和W的值 4 顾客到达后必须等待 即n 3 9 4多服务台模型 2020年1月30日星期四 9 4多服务台模型 9 4 2有限队列模型 0 1 2 s 1 s s 1 N 1 N 图9 10有限队列模型状态转移图 设系统容量为N N s 当系统中的顾客数n N时 到达的顾客进入系统 当n N时 到达的顾客就被拒绝 设顾客到达的速率为 每个服务台服务的速率为 系统的状态转移图见图9 10 2020年1月30日星期四 9 4多服务台模型 稳定状态的状态概率转移方程为 9 38 9 39 9 40 9 41 9 42 9 43 9 44 2020年1月30日星期四 9 4多服务台模型 9 45 系统的运行指标 9 46 9 47 9 48 9 49 2020年1月30日星期四 9 4多服务台模型 例9 6 某旅馆有10个床位 旅客到达服从泊松流 平均速率为6人 天 旅客平均逗留时间为2天 求 1 旅馆客满的概率 2 每天客房平均占用数 旅馆10个床位全满的概率为0 3019 平均占用8 377个床位 客房占用率为83 77 2020年1月30日星期四 9 4多服务台模型 9 4 3有限顾客源模型 设顾客源为有限数m 服务台个数为s 且m s 这个模型的典型例子是机器维修问题 机器数量为m台 修理工数量为s人 状态概率 式中 9 51 9 50 2020年1月30日星期四 9 4多服务台模型 运行指标 2020年1月30日星期四 9 4多服务台模型 例9 7 车间有5台机器 每台机器的故障率为1次 小时 有2个修理工负责修理这5台机器 工作效率相同 为4台 小时 求 1 等待修理的平均机器数 2 等待修理及正在修理的平均机器数 3 每小时发生故障的平均机器数 4 平均等待修理的时间 5 平均停工时间 解 这是一个模型 2020年1月30日星期四 9 4多服务台模型 P1 0 394 P2 0 197 P3 0 074 P4 0 018 P5 0 002 由式 9 51 可以计算得到 2020年1月30日星期四 作业 教材P216T7 8 下一节 其它服务时间分布模型 9 4多服务台模型 9 5其它服务时间分布模型 2020年1月30日星期四 9 5其它服务时间分布模型 9 5 1一般分布模型 G表示服务时间T的分布为任意的概率分布 但已知期望值E T 和方差Var T 该模型被称为 单服务台泊松到达 任意服务时间的排队模型 在稳态情况下 当时 可以证明下列P K Pollaczek Khintchine 公式成立 其他指标为 推导过程略 9 57 9 58 2020年1月30日星期四 9 5其它服务时间分布模型 例9 8 某维修站有一技工修理出故障机器 现已知机器按泊松流发生故障 平均故障率为每小时5台 机器排队有两种类型 一种修理时间为9分钟 另一种是12分钟 资料统计知 1 3故障需要修理12分钟 试求此维修站的运行指标 解 服务时间可以看成是二项分布 利用P K公式求得 2020年1月30日星期四 9 5其它服务时间分布模型 9 5 2定长分布模型 模型符号中的D表示服务时间为固定长度 即为常数 该模型被称为单服务台泊松到达 定长服务时间的排队模型 因此 只需将模型中的方差改为0 即可得到定长排队模型的各个指标 2020年1月30日星期四 9 5其它服务时间分布模型 解 服务时间定长 该服务系统是一个 排队系统 其中 代入式 9 58 计算得 例9 9 某汽车冲洗站有一套自动冲洗设备 冲洗每辆汽车所需时间为6分钟 到此冲洗站来冲洗汽车的到达过程服从泊松分布 每小时平均到达6辆 求该排队系统的有关运行指标 2020年1月30日星期四 9 5其它服务时间分布模型 9 5 3爱尔朗分布模型 在此模型中 每一个顾客必须依次经过k个服务站 接受k次服务后才构成一个完整的服务过程 该模型假设每个服务站的服务时间Ti服务相同的负指数分布 参数为k 则总的服务时间 服从k阶爱尔朗 Erlang 分布 其他条件与标准的 M M 1 模型相同 此模型的如下数量指标 9 59 9 60 9 61 2020年1月30日星期四 9 5其它服务时间分布模型 9 62 9 63 在M EK 1 FCFS排队系统中 而当K 时 m EK 1 排队系统可认为为m D 1排队系统 在m D 1排队系统中 2020年1月30日星期四 9 8 2 M D 1 FCFS 在m D 1排队系统中 2020年1月30日星期四 9 5其它服务时间分布模型 例9 10 一个质量检查员平均每小时收到2件送来检验的样品 每件样品要依次完成5项检验才能判定是否合格 据统计 每项检验所需时间的期望值都是4分钟 每项检验的时间和送检产品的到达时间间隔都为负指数分布 求检验过程的各项指标 解 该检验系统是一个排队系统 且 2020年1月30日星期四 作业 教材P216T9 10 11 下一节 排队系统的优化 9 5其它服务时间分布模型 9 6排队系统的优化 2020年1月30日星期四 9 6排队系统的优化 排队系统的费用包含以下两个方面 一个是服务费用 它是服务水平的递增函数 另一个是顾客等待的机会损失 费用 它是服务水平的递减函数 两者的总和呈一条U形曲线 如图9 11 服务水平 费用 等待费用 服务费用 总费用 如图9 11 9 6 1排队系统经济分析 2020年1月30日星期四 9 6排队系统的优化 排队系统的优化问题常常分为两类 一类称之为系统的静态最优设计 目的在于使设备达到最大效益 或者说 在保证一定服务质量指标的前提下 要求机构最为经济 另一类叫做系统动态最优运营 是指一个给定排队系统 如何运营可使某个目标函数得到最优 归纳起来 排队系统常见的优化问题有 1 确定最优服务率 2 确定最佳服务台数量 3 选择最为合适的服务规则 4 或是确定上述几个量的最佳组合 2020年1月30日星期四 式中 Cs为 1时单位时间内的服务费用 Cw为每个顾客在系统中逗留单位时间的费用 稳态下取目标函数z为单位时间服务成本与顾客在系统逗留费用之和的期望值最小 M M 1 FCFS 9 6排队系统的优化 9 6 2最优服务水平 的确定 1 基本模型 9 65 9 66 2020年1月30日星期四 9 6排队系统的优化 例9 11 某地欲兴建一座港口码头 但只有一个装卸船只的位置 现要求设计装卸能力 装卸能力用每天装卸的船只数表示 已知单位装卸能力每天平均生产成本为2000元 船只到港后若不能及时装卸 停留一天损失运输费1500元 预计船只的平均到达率为3只 天 设船只到达的时间间隔和装卸时间都服从负指数分布 问港口装卸能力为多大时 每天的总支出最少 解 Cs 2000元 天 Cw 1500元 天 3只 天 由式 9 66 有 即最优装卸能力为4 5只 天 2020年1月30日星期四 2 有限队列模型的最优服务率 M M 1 N FCFS 单位时间内达到系统的平均顾客数 设服务一个顾客服务机构的收入为G 单位时间收入的期望值是 给定N及Cs G求出 或给定Cs G及 求N PN为被拒绝的概率 1 PN为能接受服务的概率 取纯利润最大 9 6排队系统的优化 9 68 2020年1月30日星期四