运筹学排队论课件推荐.pptVIP

运筹学课程 上海交通大学管理学院 第十二章 排队论 排队现象 火车站的售票口 理发店 客户服务电话 乘校车 港口 食堂吃饭 生产流水线 这类现象的特点：顾客到来是随机的，服务机构对顾客的服务时间也是随机的。排队论也成为随机服务系统理论，这是对上述随机服务问题进行研究。 随机服务系统所面临的问题 服务系统要改善自身的服务质量，提高顾客满意度，减少顾客的排队等候时间。 VS 服务系统要控制内部运营成本，减少人力、物力资源浪费。 如何两者之间取得平衡？ 排队论的研究内容 性态问题 运用概率统计手段，分析随机服务系统的规律，主要研究排队的 队长分布、顾客等待时间分布、服务机构的忙期分布。 包括瞬态和稳态两种情形。 最优化问题 分为静态优化和动态优化。静态优化研究服务系统的设计，动态优化研究服务系统运营。 基本概念（1） 排队过程的一般表示 基本概念（2） 顾客源 服务系统服务对象的总体。顾客源的组成可能是有限的，也可能是无限。 顾客到来（输入过程） 到来方式：一个一个的、成批到来。 到达的时间间隔：确定型、随机型 到达事件的相互独立性：以前到达顾客的事件对以后到来顾客的事件没有影响 输入过程的平稳性：顾客相继到达的间隔时间分布和所含参数（如期望值、方差等）都与时间无关。 否则，输入过程是非平稳的。 基本概念（3） 排队规则 即时制（损失制）与等待制 即时制（损失制）：如果服务机构正在被占用，顾客到来后随即离去。 等待制：如果服务机构正在被占用，顾客到来后排队等待 对列容量：由于服务系统内部的空间限制或其他原因，有的系统要规定排队容量（允许进入排队系统的顾客数）的最大限。有的系统则没有这方面限制。 对列数目：可以使单列也可以是多列。 基本概念（4） 服务规则 先到先服务 后到先服务 随机服务 有优先权的服务 服务机构 服务台的布置 基本概念（5） 服务方式：单个顾客服务，批量顾客服务 服务时间：确定型，随机型 如果输入过程中顾客相继到达的时间间隔和服务时间两者都为确定型（如生产流水线），该问题很好处理，不是排队论所讨论的问题。在排队论的研究中，两者至少有一个随机型分布。 服务时间的平稳性。服务时间的分布和所含参数（如期望值、方差等）都与时间无关。 排队模型的分类 X/Y/Z/A/B/C X表示顾客相继到达的间隔时间分布 Y表示服务时间的分布 M——负指数分布（Markov） D——确定型（Deterministic） Ek——k阶爱尔朗（Erlang）分布 GI——一般相互独立（General independent）的时间间隔分布 G——一般服务时间分布 Z表示并列服务台的数目 A表示服务系统容量（服务中和排队等待的顾客总和）的限制 B表示服务系统的顾客源数目 C表示服务系统的服务规则，如先到先服务（FCFS），后到先服务（LCFS），随机服务（SIRO），优先权服务（PR） 服务系统中的几个重要参数 服务系统中的性能指标 参数与性能指标之间的关系 1/λ相邻两个顾客到达的平均时间间隔 1/u对每个顾客的平均服务时间 Ls=Lq+S 对于单服务台来讲系统忙期=1-P0 排队论问题的求解思路 根据顾客到达的时间间隔和顾客服务时间的实际数据资料进行分析，确定其理论上是属于何种概率分布类型； 确定系统处于各种状态（系统中顾客数）的概率； 计算反应系统特征的一系列性能指标（队长、忙期、逗留时间、等待时间等） 顾客到达的时间间隔分布与服务时间的分布 解决了顾客到达的时间间隔分布与服务时间的分布排队论问题迎刃而解； 顾客到达的时间间隔分布与服务时间的分布是随机的，情况较为复杂，需拿出来单独研究； 介绍几种常用的随机模型。 泊松流（poisson）（1） 设N(t)表示在时刻t服务系统内的顾客数 Pn(t1,t2)表示在时间区间[t1,t2)（ t1t2 ）内有n个顾客到达的概率，即 如果满足以下三个条件，可以说顾客到达的形成泊松流： （1）无后效性：在不相重叠的时间区间内顾客到达数是相互独立； （2）平稳性：对充分小的⊿t，在时间区间[t,t+⊿t)内有一个顾客到达的概率与t无关，而几乎与区间长⊿t成正比 其中o(⊿t),当⊿t→0时，是关于⊿t的高阶无穷小； λ0是常数，表示单位时间有一个顾客到达的概率。 （3）普通性：对于充分小的⊿t，在时间区间[t,t+⊿t)内有2个或2个以上顾客到达的概率极小，可以忽略 泊松流（poisson）（2） 目前在排队论的研究中，顾客到达的时间分布还仅限于对泊松流分布的研究，其他分布用数学解析方法还得不到满意解。 实例 负指数分布(1) 设顾客到达的时间间隔T为随机变量，是一个以λ为参数的负指数分