运筹学课件（第十三讲）-排队论

运筹学课程第十二章排队论排队现象火车站的售票口理发店客户服务电话乘校车港口食堂吃饭生产流水线这类现象的特点：顾客到来是随机的，服务机构对顾客的服务时间也是随机的。排队论也成为随机服务系统理论，这是对上述随机服务问题进行研究。随机服务系统所面临的问题服务系统要改善自身的服务质量，提高顾客满意度，减少顾客的排队等候时间。VS服务系统要控制内部运营成本，减少人力、物力资源浪费。如何两者之间取得平衡？排队论的研究内容性态问题运用概率统计手段，分析随机服务系统的规律，主要研究排队的队长分布、顾客等待时间分布、服务机构的忙期分布。包括瞬态和稳态两种情形。最优化问题分为静态优化和动态优化。静态优化研究服务系统的设计，动态优化研究服务系统运营。基本概念（1）排队过程的一般表示顾客源排队机构服务机构顾客到来排队规则服务规则离开随机服务系统顾客源服务系统服务对象的总体。顾客源的组成可能是有限的，也可能是无限。顾客到来（输入过程）到来方式：一个一个的、成批到来。到达的时间间隔：确定型、随机型到达事件的相互独立性：以前到达顾客的事件对以后到来顾客的事件没有影响输入过程的平稳性：顾客相继到达的间隔时间分布和所含参数（如期望值、方差等）都与时间无关。否则，输入过程是非平稳的。基本概念（2）排队规则即时制（损失制）与等待制即时制（损失制）：如果服务机构正在被占用，顾客到来后随即离去。等待制：如果服务机构正在被占用，顾客到来后排队等待对列容量：由于服务系统内部的空间限制或其他原因，有的系统要规定排队容量（允许进入排队系统的顾客数）的最大限。有的系统则没有这方面限制。对列数目：可以使单列也可以是多列。基本概念（3）基本概念（4）服务规则先到先服务后到先服务随机服务有优先权的服务服务机构服务台的布置服务方式：单个顾客服务，批量顾客服务服务时间：确定型，随机型如果输入过程中顾客相继到达的时间间隔和服务时间两者都为确定型（如生产流水线），该问题很好处理，不是排队论所讨论的问题。在排队论的研究中，两者至少有一个随机型分布。服务时间的平稳性。服务时间的分布和所含参数（如期望值、方差等）都与时间无关。基本概念（5）排队模型的分类X/Y/Z/A/B/CX表示顾客相继到达的间隔时间分布Y表示服务时间的分布M——负指数分布（Markov）D——确定型（Deterministic）Ek——k阶爱尔朗（Erlang）分布GI——一般相互独立（Generalindependent）的时间间隔分布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)（t1>t2）内有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为随机变量，是一个以λ为参数的负指数分布，则它的概率密度函数为：负指数分布(2)性质（2）当服务时间服从以u为参数的负指数分布则离开服务系统的顾客数概率分布为概率密度为u的泊松流（3）无记忆性（马尔可夫性）即一个顾客到来所需的时间间隔t与过去一个顾客到来所需的时间间隔s无关，所以在随机服务系统中，如果顾客到达的时间间隔为负指数分布，则顾客到达是存随机的。实例爱尔朗分布（Erlang）单服务台负指数分布系统分析模型类型标准模型，M/M/1/∞/∞系统的容量有限制，M/M/1/N/∞顾客源为有限数，M/M/1/∞/mM/M/1/∞/∞（1）条件限制：M/M/1/∞/∞（2）系统稳定下的状态分布求出服务系统在稳定状态下，t时刻顾客数（系统状态）为n的概率分布Pn(t)M/M/1/∞/∞（3）性能指标M/M/1/∞/∞（4）总结实例实例2特点随机服务系统的容量有上限数N；单服务台；若一个顾客到达服务系统时，发现系统中已经有N个顾客，那么这个顾客就被拒绝进入系统；当N=1时，为即时制M/M/1/N/∞（1）M/M/1/N/∞（2）稳态下的状态转移方程M/M/1/N/∞（3）性能指标

比较M/M/1/N/∞的Ls与M/M/1/∞/∞的Ls有效到达率系统损失率PN+1M/M/1/N/∞（4）总结实例M/M/1/∞/m（1）特点随机服务系统的顾客源有上限数m；单服务台；实际上，虽然系统的容量没有限制，但系统中的顾客数永远也不会超过m，因此M/M/1/∞/m与M/M/1/m/m两类模型等同。状态转移过程中的顾客到达率。在无限顾客源情形下，顾客到达率是按顾客的全体来考虑。但在顾客源有限情形下，必须按每个顾客来考虑。

假定每个顾客来到服务系统的时间间隔服从参数为λ的负指数分布，则λ表示单个顾客的平均到达率（其含义是单位时间内该顾客来到服务系统请求服务的次数）。当顾客总数为m，而系统中有n个顾客，则顾客