管理运筹学第十章排队论课件.ppt

运筹学 1 PPT学习交流 第十章排队论 2 PPT学习交流 第十章排队论 10 1概述排队论 QueingTheory 也称随机服务系统 任何一个服务系统均由客体和主体组成 前者是要求服务的对象 我们一律称之为 顾客 后者是提供服务的机构或人员 一律称之为 服务员 顾客可泛指机器 病人 飞机 轮船等 服务员可泛指机修工 医生 码头等 3 PPT学习交流 第十章排队论 服务系统 顾客 机器 飞机 轮船 病人 顾客到达 等待服务 接受服务 顾客离去 服务员 机修工 码头设备 医生 到达时间 服务时间系统空闲 到达时间 服务时间充分利用 无排队 到达时间 服务时间排队越来越长 4 PPT学习交流 第十章排队论 问题是 到达间隔 服务时间均为随机变量 这也是随机服务系统的基本特征 所以难以确定系统状态 只能求期望值 我们希望借助随机服务系统理论来揭示这些规律 5 PPT学习交流 第十章排队论 例 某港口装卸台负责货轮装卸工作 货轮即顾客以某固定周期间隔到达港口 比如每隔a 6小时到达一艘 而装卸台卸货需要一段时间 假定它对每艘货轮的服务时间也是定长的 比如每艘需卸时间为s 4小时 这一服务系统的特征是到达和服务时间均是确定不变的定长 结论 如果sa 则形成等待卸货队伍 且队长不断增加 6 PPT学习交流 第十章排队论 如果货轮到达时间间隔是随机变量 码头卸货时间也为随机变量 则构成一个随机服务系统 即便货轮到达时间间隔的平均时间还为6小时 但每一个间隔时间Xi i 1 2 并不都是6小时 只是指 同理 平均服务时间为4小时 从而会产生排队或服务空闲时间 但事先无法确定 7 PPT学习交流 第十章排队论 对于随机服务系统希望知道 1 在系统中平均队长L 从长远来看 平均等待服务加上正接受服务的货轮期望数 2 在队中平均队长Lq 从长远来看 平均等待服务的货轮期望数 3 系统中平均逗留时间 从长远看 任一进入系统货轮用于等待服务加上接受服务的期望时间 4 在队中平均等待时间 从长远看 任一进入系统货轮用于等待服务的期望时间 8 PPT学习交流 第十章排队论 一 服务系统的结构假如将要求服务的对象统称为 顾客 进行服务的统称为 服务机构 或 服务员 一个排队系统就能抽象地描述为 为了获得某种服务而到达的顾客 若不能立即获得服务 而又允许排队等待 则加入等待队伍 获得服务之后离开系统 作为服务系统基本上由三个部分组成 9 PPT学习交流 第十章排队论 1 输入过程刻划顾客按怎样的规律到达服务系统 主要有以下几方面 1 顾客总体 顾客源 数可能是有限的 例厂内故障设备数 也可能是无限的 到达售票窗口前的顾客总体 2 顾客可能是单个到达 也可能是成批到达 3 顾客相继到达的间隔时间分布可以是确定型 也可以是随机型 4 顾客的到达可以是相互独立的 即以前的到达情况对以后顾客的到来没有影响 10 PPT学习交流 第十章排队论 5 输入过程可以是平稳的 指描述相继到达的间隔时间分布和所含参数 如 都与时间无关 否则称为非平稳的 6 具有不耐烦顾客的输入a 弃长队而去b 排队太久而去c 转队 11 PPT学习交流 第十章排队论 2 排队规则 到达的顾客按什么样的规则接受服务 1 损失制即服务台一旦占用 顾客随即离去 2 等待制顾客到达后须等待服务 服务次序为 a 先到先服务b 后到先服务c 随机服务d 有优先权的服务3 混合制 损失制与等待制的混合 a 队长有限制的情形队长k 离去 12 PPT学习交流 第十章排队论 b 等待 或逗留 时间有限制的情形排队时间 t0 离去 反之排下去4 从队伍的数目看 可以是单列 也可以是多列a 顾客可转移 b 顾客不可转移 13 PPT学习交流 第十章排队论 3 服务机构1 服务员的数目串列 并列 串并混合2 服务方式对单个顾客服务或对成批顾客服务3 服务时间分确定型和随机型服务时间 14 PPT学习交流 第十章排队论 二 表示排队模型的符号D G Kendall于1953年提出排队符号 i j c i 到达过程的分布 j 服务过程分布 c 服务员数到了1971年进一步定为 到达分布 服务分布 服务员数 系统容量 顾客源 排队规则 M M 1 FCFS 常规表示法为 M M 1 15 PPT学习交流 第十章排队论 三 排队模型中常用参数 到达速度 单位时间到达顾客数 服务速度 单位时间服务完成数 1 相继顾客到达的平均间隔时间 1 一个顾客的平均服务时间 1 1 称为服务强度 指相同时间区间内顾客到达的平均数与能被服务完的平均顾客数之比 16 PPT学习交流 第十章排队论 四 系统的稳态性态1 j 稳态概率 j定义为稳态系统中有j个顾客 包括正在服务的 的概率 0 1 称为系统空闲的概率 17 PPT学习交流 第十章排队论 2 3 4 5 18 PPT学习交流 第十章排队论 6 7 进入系统的顾客逗留时间超过t的概率 进入系统的顾客等待时间超过t的概率 19 PPT学习交流 第十章排队论 五 稳态性态中各量值的分析1 的意义1 平均到达速度与平均服务速度之比 2 服务员利用率 1 03 一个平均服务时间 内到达的顾客平均数 20 PPT学习交流 第十章排队论 4 正在接受服务的顾客平均数 0 0 1 1 0 2 L与Lq的关系 表示系统中平均人数等于队中平均人数加上正在接受服务顾客平均人数 21 PPT学习交流 第十章排队论 3 系统逗留时间减排队时间恰为服务时间的期望值 22 PPT学习交流 第十章排队论 4 23 PPT学习交流 第十章排队论 5 24 PPT学习交流 第十章排队论 10 2M M 1模型实例例1 某厂有几千名工人 医务室平均每小时约有4位工人来看病 医生每小时平均诊断约5个病人 若到达时间间隔服从普阿松 Pisson 分布 服务时间服从负指数分布 试分析该系统 解 本例属标准 M M 1 FCFS 问题 已知 4人 小时 5人 小时 4 5 0 8系统队长L 1 0 8 1 0 8 4人 平均4人排队和看病队长Lq 2 1 0 82 1 0 8 3 2人 平均有3 2人在排队或Lq L 4 0 8 3 2人 25 PPT学习交流 第十章排队论 工人在医务室平均逗留时间 病人平均在医务室内排队和看病时间约为1小时 工人在医务室平均排队时间 病人平均在医务室内排队时间约为0 8小时 26 PPT学习交流 第十章排队论 系统空闲概率 0 1 1 0 8 0 2系统忙的概率1 0 0 8以该厂每天工作8小时计 则每天平均来看病的人数为 L总 8 8 4 32人 天 全体病人每天平均等待看病所化时间为 W总 病人逗留时间和排队超过1小时的概率分别为 27 PPT学习交流 第十章排队论 若要计算系统中大于10个病人的概率 则 n 10 11 0 811 0 086即医务室中大于10个病人的概率仅为8 6 医务室中病员大于K的概率 28 PPT学习交流 第十章排队论 例2 某电机修理车间 每天平均有2台电机到达修理 负责修理的是1名修理工 平均每3小时修完1台 若到达为泊松分布 修理时间为负指数分布 求1台电机从到达到修理完毕的平均时间及修理工人每天的平均空闲时间 每天以8小时计 解 本问题属 M M 1 FCFS 模式到达速度 2台 8小时 1 4台 小时服务速度 1台 3小时 1 3台 小时 1 4 1 3 3 4 1 29 PPT学习交流 第十章排队论 一台电机从到达到修理完毕的平均时间为 一台电机排队的平均时间为 30 PPT学习交流 第十章排队论 服务员空闲概率 0 1 1 3 4 1 4每天空闲时间 1 4 8 2小时 天系统中平均人数L 1 3 4 1 4 3人系统中平均队长Lq 2 1 3 42 1 4 9 4人 31 PPT学习交流 第十章排队论 例3 某装卸台装卸设备的设计方案中 有三个方案可供选择 有关费用见下表 32 PPT学习交流 第十章排队论 设货车按Poisson流到达 平均每天 按10小时计算 到达15车 每车平均装货500袋 卸装时间遵从负指数分布 每辆车停留一小时的损失费为10元 问该选择哪个方案 解 本系同属M M 1模型 平均到达率 15 10 1 5车 小时 服务率 1 1000袋 小时 500袋 车 2车 小时 或 1 5 500 750袋 小时 1 1000袋 小时 33 PPT学习交流 第十章排队论 34 PPT学习交流 第十章排队论 一辆车在系统中的平均停留时间为 35 PPT学习交流 第十章排队论 因此 每天货车在系统里逗留时间的平均损失费为 36 PPT学习交流 第十章排队论 服务强度 每天实际可变费用 37 PPT学习交流 第十章排队论 各方案总费用 结论 应选方案2 38 PPT学习交流 第十章排队论 10 3容量有限的M M 1 K FCFS模型 本模型与前相比为系统容量有限 若在某一时刻有一顾客到达时 如系统中已有K个顾客 那个顾客就被拒绝进入系统 当系统已满 N K 则到达率 0 所以有必要找出 有效的到达率 e e 1 Pk 39 PPT学习交流 第十章排队论 系统的状态概率 40 PPT学习交流 第十章排队论 41 PPT学习交流 第十章排队论 例4 某美容院有6个椅子接待顾客等待理发 当6个椅子都坐满时 后到的顾客就被拒绝 顾客到达时间服从负指数分布 平均到达率为3人 小时 每人的理发时间也服从负指数分布 平均需要5分钟 试分析这一系统 解 k 76人排队 1人接受服务 这是M M 1 7 FCFS系统 3人 小时 4人 小时 1 求某顾客一到美容院就理发的概率 即求系统空闲概率 42 PPT学习交流 第十章排队论 2 求系统逗留顾客人数及排队人数 43 PPT学习交流 第十章排队论 3 求有效到达率 4 求每一顾客在美容院内逗留时间的期望值 5 求每一顾客在美容院排队时间的期望值 44 PPT学习交流 第十章排队论 6 求系统客满时顾客流失率 满客等于流失 45 PPT学习交流 第十章排队论 例5 某汽车加油车站只有一台加油泵 且场地最多只能容纳三辆车 一辆加油二辆等待 当站内场地占满时 到达的汽车只能去别处加油 汽车到达间隔时间服从普阿松分布 其中均值为每8分钟一辆 服务时间间隔服从负指数分布 其平均值为4分钟一辆 加油站有机会租赁毗邻的一块空地 以供多停放一辆前来加油的车 无加油泵 租地费用为每周1000元 每周从每个顾客那里期望净收益是50元 这个站每天开放10小时 问租赁空地是否有利 46 PPT学习交流 第十章排队论 解 本系统属M M 1 3 FCFS模型 已知 60 8 7 5辆 小时 60 4 15辆 小时 7 5 15 0 5 1 系统空闲概率 47 PPT学习交流 第十章排队论 2 求系统逗留顾客人数及排队人数 3 求有效到达率 48 PPT学习交流 第十章排队论 4 求每一辆车在加油站内逗留时间的期望值 5 求每一辆车在加油站内排队时间的期望值 49 PPT学习交流 第十章排队论