Session10排队与仿真ppt课件

Data ModelandDecisions数据 模型与决策 Session10QueuingTheoryandSimulation排队与仿真 SessionTopics SystemCharacteristics系统特征MeasuresofSystemPerformance系统绩效度量SomeQueuingModels一些排队模型ApplicationofQueuingTheory排队论的应用IntroductiontoSimulation仿真介绍TypesofSimulation仿真类型SimulationSteps仿真步骤ApplicationsofSimulation仿真应用 QueuingTheory排队理论 哪儿有排队现象呢 机器等待修理电话忙音银行排队邮局排队餐厅排队商场排队 SystemCharacteristics系统特征 Arrivalandservicepattern到达和服务规则Charactersofservers服务器 台 特征Queuediscipline队列规则 顾客的总体数或顾客源数 可能是有限也可能是无限 顾客到达的类型 顾客到来到的方式可能是一个一个的 也可能是成批到达 顾客相继到达的时间间隔分布 可以是确定型的 也可以是随机型的 分布参数是什么 是否独立 是否平稳 ArrivalPattern顾客到达模式 描述顾客到达规律可从两方面 现实中有许多服务系统 其顾客的到达具有下述特征 1 无后效性 任一时段的到达数不受前一时段的影响 2 平稳性 顾客到达是均匀的 3 稀有性 瞬时内只可能有1个顾客到达 称具有上述特征的输入为泊松流 其在t时段内到达n个顾客的概率为 即参数为的泊松分布 ArrivalPattern顾客到达模式 通常假定为 泊松分布 Poissondistribution 由概率论知识可知 泊松分布的参数即其均值 因此 的含义是单位时间到达系统的平均顾客数 即到达率 下面考察 当顾客按泊松流到达时 其到达的间隔时间T是服从什么分布呢 因为到达为泊松流 所以 t时段内没有来顾客的概率为 所以 t时段内有顾客到来 即间隔Tt 的概率为 而这正是负指数分布的分布函数 说明T服从负指数分布 且参数同为 可证反之也成立 于是得到关于到达规律的重要性质 由概率论知识可知 负指数分布的表达式 密度函数 为参数即其均值的倒数 因此 的含义是平均间隔时间 这与为单位时间到达系统的平均顾客数的含义一致 到达数为泊松流到达间隔服从负指数分布 同参数 服务台 员 的数量 可以有一个或多个服务员 服务台 通道 窗口等 服务台 员 的排列情况 多个服务台 可以平行排列 并列 可以前后排列 串列 也可以是混合的 服务方式 可以对单个顾客进行 也可以对成批顾客服务 我们将只研究单个单个的服务方式 服务时间是确定型的 还是随机型的 分布参数是什么 是否独立 是否平稳 CharactersofServers服务台特征 单服务台 多服务台 ServiceTime服务时间 通常假定为指数分布 Exponentialdistribution 主要讨论服务时间v服从负指数分布的情形 参数为 即 参数的含义 服务率 即单位时间平均服务完人 由于v的均值为 即平均对每位顾客的服务时间为 可得 QueueDiscipline队列规则 先到先服务 FCFS 多种优先权 1 损失制指顾客到达时若所有服务实施均被占用 则顾客自动离去 2 等待制指顾客到达时若所有服务实施均被占用 则留下来等待 直至被服务完离去 等待的服务规则又可分为 先到先服务 FCFS 后到先服务 LCFS 3 混合制分为 系统容量有限制 等待时间有限制 系统类型顾客服务台理发店人理发师银行出纳服务人出纳ATM机服务人ATM机商店收银台人收银员管道服务阻塞的管道管道工电影院售票窗口人售票员机场检票处人航空公司代理人经纪人服务人股票经纪人 CommercialServiceSystems商业服务系统 系统类型顾客服务台秘书服务雇员秘书复印服务雇员复印机计算机编程服务雇员程序员大型计算机雇员计算机急救中心雇员护士传真服务雇员传真机物料处理系统货物物料处理单元维护系统设备维修工人质检站物件质检员 InternalServiceSystem内部服务系统 系统类型顾客服务台公路收费站汽车收费员卡车装货地卡车装货工人港口卸货区轮船卸货工人等待起飞的飞机飞机跑道航班服务人飞机出租车服务人出租车电梯服务人电梯消防部门火灾消防车停车场汽车停车空间急救车服务人急救车 TransportationServiceSystem运输服务系统 MeasuresofSystemPerformance系统绩效度量 Averagenumberofcustomerswaiting平均顾客等待个数Averagetimecustomerswait平均顾客等待时间Systemutilization系统利用率 SomeModels一些模型 单服务台指数服务时间 M M 1 单服务台一般服务时间 M G 1 多服务台指数服务时间 M M s l 顾客到达率 服务率 1 平均服务时间 Lq 队列中的顾客数L 系统中平均顾客数Wq 队列中平均等待时间W 包括服务的平均等待时间Pn 有n个顾客在系统的概率r 系统利用率 BasicRelationships基本关系 1 队长 把系统中的顾客数称为队长 它的期望值记作Ls 排队长 指在系统中排队等待服务的顾客数 它的期望值记作Lq 显然有队长 排队长 正被服务的顾客数2 逗留时间和等待时间 一个顾客从到达排队系统到服务完毕离去的总停留时间称为逗留时间 它的期望值记作Ws 一个顾客在系统中排队等待的时间称为等待时间 它的期望值记作Wq 显然有逗留时间 等待时间 服务时间 系统利用率系统中平均顾客数队列中平均等待时间包括服务的平均等待时间 BasicRelationships基本关系 Model1 M M 1 模型1 M M 1 系统空闲的概率 系统中有n个顾客的概率 队列中的顾客数 Template M M s M M s 模板 Model2 M G 1 模型2 M G 1 队列中的顾客数 系统空闲的概率 在M D 1队列中的顾客数 Template M D 1 M D 1 模板 系统空闲的概率 系统中有n个顾客的概率 一个新到达的顾客要等待的概率 队列中的顾客数 Model3 M M s 模型3 M M s ApplicationofQueuingTheory排队论的应用 需要多少雇员是要一个服务快的服务台还是多个服务慢的服务台 施乐公司 XeroxCorporation 推出了一种新型复印系统 这个系统被证明对拥有者很有价值 因此 这些顾客要求施乐的技术服务代表降低修理设备的等待时间 然后一个管理科学小组用一个排队模型研究如何以最好的方式满足新服务的要求 结果是用较大的三人技术服务代表负责区域代替先前的单人技术服务代表负责区域 这个变化显著的降低了顾客的平均等待时间并使技术服务代表的利用率的上升超过了50 Interfaces1975年十一月号 ApplicationsofPrize winner获奖应用 ApplicationsofPrize winner获奖应用 L L Bean公司 一个大型的电话销售商和邮购订货目录公司 主要依靠基于对如何分配通讯资源的获奖研究的排队模型 进入呼叫中心的订购电话是一个庞大的排队系统的顾客 电话代理人是服务台 1需要多少条电话干线用来接入打进呼叫中心的电话 2在各个时间段需要多少电话代理人 为等待电话代理人接听电话的顾客提供多少等待位 Interfaces1991 1 1989 11 1993 3 4 IntroductiontoSimulation仿真介绍 分析模型 IntroductiontoSimulation仿真介绍 仿真模型 TypesofSimulation仿真类型 系统仿真 SystemSimulation 仿真不同时间的一系列事件 来决定系统的表现例如 排队系统制造系统库存管理 TypesofSimulation仿真类型 蒙特卡洛仿真 MonteCarloSimulation 根据抽样实验来估计有概率特征的分布例如 一项风险投资退休计划新产品开发 SimulationSteps仿真步骤 典型的仿真步骤 介绍系统的主要组成及如何运行和相互联系仿真时钟设定系统状态的定义随机产生模拟事件的方法当某一事件发生时 改变系统状态的方法推进仿真时钟的过程 GeneratingRandomVariables产生随机变量 产生随机变量的方法 机械工具 Mechanicaldevice 随机数表 Randomnumbertable 随机数产生器 Randomnumbergenerator GeneratingRandomVariablesinExcel用Excel产生随机变量 均匀分布U a b a b a RAND VLOOKUP RAND D3 E6 2 正态分布Normal m s NORMINV m s RAND 指数分布Exponential rate l l LN RAND GeneratingRandomVariablesinExcel用Excel产生随机变量 ApplicationsofSimulation仿真应用 管理库存系统欧洲IBM个人电脑公司 IBMPCCompany 竞争对手敏捷性的不断增强 IBM公司面临的竞争压力增大 为了找出一种便捷的方法来快速处理客户的订单 管理科学小组通过对公司整条供应链 涉及采购 生产和配送 包括每个环节产生的库存 进行仿真分析出解决之道 通过对供应链设计和运作的大幅度调整 每年直接成本节省4000万美元 大大增强了公司的竞争地位 1996年4月OR MSToday ApplicationsofSimulation仿真应用 估计在截止期完成项目的概率在项目管理中 越来越多地运用计算机仿真来获得更为精确的概率估计值 计算机仿真的方法包括了根据项目中不同任务的完成时间的概率分布来产生的随机观察 而后 运用网络化的计划 仿真每一事件开始和结束以及整个任务何时结束 在一个仿真周期内上千次的重复这一过程 就可以非常精确地估计出完成任务的概率值 ApplicationsofSimulation仿真应用 制造系统的设计与运行制造系统可以看作排队系统 然而这种系统有内在复杂性 可用计算机仿真解决这类问题 必须提供多少种类型的机器 每一类原料加工单位的数量 根据完成任务的期限 必须依据怎样的工作流程来开展工作 设计的新生产流程中存在有什么瓶颈问题 ApplicationsofSimulation仿真应用 配送系统的设计和运作雷诺德金属制品公司 ReynoldsMetalsCompany 每年花2 5亿美元运输原料和货物 通过卡车 火车 船舶和飞机等运输工具来进行货运 运输网络包括工厂 仓库和供货商等上千个运输点 综合运用混合0 1整数规划和计算机仿真设计出一个具有中央分配功能的配送系统 这一新系统不仅改善了送货的及时性 还减少了每年的货运成本700多万美元 Interfaces1991年1 2 ApplicationsofSimulation仿真应用 财务风险分析最早运用在计算机仿真的是财务风险分析 考虑对具有不稳定现金流的资本投资的评估问题 通过根据不同时期现金流的概率分布而产生的随机观察数 考虑各个时期关联性 计算机仿真可以产生数千种投资方案的结果 这就提供了投资收益 如净现值 的概率分布 这种分布 称为风险分布 有助于管理层评价投资的风险性 ApplicationsofSimulation仿真应用 保健方面应用未来不确定性的分析对做出决策有至关重要的影响而在保健问题要分析的是人类疾病发展的不确定性模拟医治有冠心病的病人时医院资源使用情况模拟在不同保险计划下的医疗费用模拟早期病症透视的成本和有效性模拟在医疗中心使用组合的外科器械模拟急救服务的呼救时间和定位 ApplicationsofSimulation仿真应用 其他领域的应用包括政府机构 银行 酒店 饭店 教育 灾害处理 国防军事部门以及游乐园等等美国邮政服务公司 TheU S PostalService 经过多年计划想要开发一大型自