排队论详解及案例

OperationsResearchcmLiu@shufe第九章排队论OperationsResearchcmLiu@shufe第九章排队论在生产和日常生活中，人们会遇到很多排队现象，比如去火车站购票、到医院就诊、上银行办理业务以及要求起降的飞机、进港待泊的船只、工厂待修的机器等等。在这些问题中，售票员与买票人、医生与患者、银行工作人员与顾客、机场跑道与起降的飞机、港口的泊位与进港的船只、维修工与待修的机器等等，均构成一个排队系统或服务系统。在排队系统中，如果服务员（服务台）过少，会引起顾客的不满，影响排队系统的服务效率；如果服务员（服务台）过多，会增加服务机构的运营、维护成本。如何协调二者之间的关系，就需要用排队论的知识加以解决。排队论就是研究排队系统（又称随机服务系统）的一门数学理论和方法。它是在对各种排队系统概率规律性进行研究的基础上，解决排队系统的最优设计和最优控制问题。OperationsResearchcmLiu@shufe第九章排队论9.1基本概念9.2几个常用的概率分布9.3单服务台负指数分布的排队系统9.4多服务台负指数分布排队系统模型9.5一般服务时间M/G/1模型9.6排队系统的建模与优化9.7电子表格建模和求解9.8案例分析办公室设施公司（OEI）服务能力分析OperationsResearchcmLiu@shufe9.1.1排队系统的描述和组成一般的排队过程可以这样描述：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。OperationsResearchcmLiu@shufe9.1.1排队系统的描述和组成尽管排队系统是多种多样的，但所有的排队系统都是由输入过程、排队规则、服务机构及服务规则三个基本部分组成的。（1）输入过程描述顾客来源以及顾客到达排队系统的规律。一般从以下几个方面对输入过程进行描述：顾客源中顾客的数量是有限还是无限；顾客到达的方式是单个到达还是成批到达；顾客的到达是否相互独立（以前到达的顾客对以后达到的顾客没有影响，则称顾客的达到是相互独立的，否则就是有关联的）；顾客相继到达的间隔时间分布是确定型的还是随机型的（如果是随机分布，需要知道单位时间内的顾客到达数或者顾客相继到达时间间隔的概率分布）；输入的过程是平稳的还是非平稳的（若相继到达的间隔时间分布参数（如期望值、方差等）都是与时间无关的，则称输入过程是平稳的，否则称为非平稳）。本章主要讨论顾客的到达是相互独立的、输入过程是平稳的情形。OperationsResearchcmLiu@shufe9.1.1排队系统的描述和组成（2）排队及排队规则描述顾客排队等待的队列和接受服务的次序，一般包括损失制、等待制和混合制三种。①损失制：指排队空间为零的系统，即当顾客到达排队系统时，若所有的服务台均被占用（正在进行服务），则顾客离开系统，永不再来。②等待制：当顾客到达排队系统时，若所有的服务台均被占用（正在进行服务），则顾客就加入排队行列等待服务，服务台按照下面的规则对顾客进行服务：先到先服务（FCFS）、后到先服务（FCLS）、随机服务（SIRO）、有优先权的服务（PR）③混合制：是等待制和损失制系统的结合，一般是指允许排队，但又不允许队列无限长下去。具体来讲，分为以下三种：•队长有限，即系统的等待空间是有限的；•等待时间有限，即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来；•逗留时间有限（等待时间和服务时间之和）。OperationsResearchcmLiu@shufe9.1.1排队系统的描述和组成（3）服务机构及服务规则指服务机构服务设施的个数、排列方式及服务方式，一般从以下几个方面进行描述：•服务台（员）的数目：服务机构可以没有服务员，也可以有一个或者多个服务员；•服务台的排列情况：有单队—单服务台、单队—多服务台、多对—多服务台、串联多服务台及混合多服务台等多种形式；•服务台（员）的服务方式：对顾客是单个服务还是成批进行服务，本章只研究对顾客进行单个服务的方式；•服务时间：同输入过程一样，对顾客的服务时间也分确定型的还是随机型的，如果是随机分布，需要知道单位时间内服务的顾客数或者是对顾客相继服务的时间间隔的概率分布。服务时间的分布是平稳的，是指服务时间的分布参数（如期望值、方差等）都是与时间无关的。本章主要讨论服务时间的分布是平稳的情形。•在排队论中，一般假设顾客相继到达的间隔时间和服务时间至少有一个是随机的。OperationsResearchcmLiu@shufe9.1.2排队模型的分类Kendall符号——X/Y/Z/A/B/CX表示顾客相继到达的间隔时间分布Y表示服务时间的分布Z表示并列的服务台个数A表示系统容量限制B表示顾客源中的顾客数目C表示服务规则（如先到先服务FCFS，后到先服务LCFS）•如略去后三项，即指X/Y/Z/∞/∞/FCFS的情形。OperationsResearchcmLiu@shufe9.1.3排队论研究的基本问题（1）排队系统工作状况的衡量一个排队系统运行状况的好坏不仅会影响顾客的利益，也会影响服务机构的利益，甚至会影响到社会效果的好坏。通过研究运行系统在平衡状态下的概率分布及其数字特征，了解排队系统运行的效率、服务质量等等，进而可以判断系统运行状况的优劣。1）队长（Ls）：排队系统中顾客的平均数（期望值），它是正在服务的顾客和等待接受服务的顾客总数的期望值。其常用的主要衡量指标如下：2）队列长（Lq）：排队系统中平均等待服务顾客数的期望值。显然有队长＝排队长＋正被服务的顾客数3）逗留时间（Ws）：一个顾客从到达排队系统到服务完毕离去的总停留时间的期望值。OperationsResearchcmLiu@shufe9.1.3排队论研究的基本问题其常用的主要衡量指标如下：4）等待时间（Wq）：一个顾客在系统中排队等待的平均时间。显然有逗留时间＝等待时间＋服务时间5）忙期：是指从顾客到达空闲着的服务机构，到服务机构再次成为空闲的这段时间，即服务机构连续忙碌的时间，它代表了服务员的工作强度。6）闲期：即服务机构连续保持空闲的时间。7）服务设备利用率：服务设备工作时间占总时间的比例，这也是衡量服务机构利用效率的指标。1==−用于服务顾客的时间服务设备总的空闲时间服务机构工作强度服务设备总的服务时间服务设备总的服务时间8）顾客损失率：由于服务能力不足而造成的顾客流失的概率。该指标过高会造成服务系统利润的减少。OperationsResearchcmLiu@shufe9.1.3排队论研究的基本问题（2）统计推断问题的研究在建立实际问题的排队系统模型时，首先要对现实数据进行收集、处理，然后分析顾客相继到达的间隔时间是否相互独立，确定其分布的类型和相关参数，研究服务时间的独立性以及服务时间的分布等，在此基础上，选择适合该系统的排队模型，再用排队模型进行分析和研究。OperationsResearchcmLiu@shufe9.1.3排队论研究的基本问题（3）系统优化问题的研究研究排队系统的目的就是通过对该系统概率规律的研究，实现系统的优化。系统的优化包括最优设计和最优运营问题。前者属于静态问题，它是在输入和服务参数给定的情况下，确定系统的设计参数，以使服务设施达到最大效益或者服务机构实现最为经济。后者属于动态问题，它是指对于一个给定的系统，在系统运行的参数可以随着时间或状态变化的情况下，考虑如何运营使某个目标函数达到最优。OperationsResearchcmLiu@shufe9.1.3排队论研究的基本问题在一般情况下，随着服务水平的提高，服务费用会增加而等待费用会减少，系统的优化就是协调二者之间的矛盾，使服务系统既能适当地满足顾客的需求，又能使总费用最低（服务费用与等待费用之和）。其常用的优化的目标有二：一是确定最优的服务水平（最优服务率或最优的服务员（台）数）使总费用最小；二是使纯收入或利润（服务收入与服务成本之差）最大。OperationsResearchcmLiu@shufe9.1.3排队论研究的基本问题这里的服务水平是指服务机构提供服务方面的能力，如服务台的个数、服务率等，服务费用是指达到相应服务水平所付出的费用，包括增加服务内容、提高服务率、组织动态服务台服务及管理支出的总费用，它一般随着服务水平的提高而上升；等待费用是指在相应的服务水平下，由于等待服务而产生的顾客及系统费用，包括顾客由于等待服务造成的损失费用、系统损失的顾客对系统造成的机会损失费用等，一般来讲它随着服务水平的提高而减少。OperationsResearchcmLiu@shufe9.2几个常用的概率分布9.2.1经验分布9.2.2泊松分布9.2.3负指数分布9.2.4爱尔朗分布OperationsResearchcmLiu@shufe9.2.1经验分布主要指标=总时间平均间隔时间到达顾客总数=服务时间总和平均服务时间服务顾客总数=到达顾客总数平均到达率总时间=服务顾客总数平均服务率服务时间总和OperationsResearchcmLiu@shufe9.2.2泊松分布泊松分布也称为泊松流，在排队论中称为最简单流。()Nt00[,)ttt+∆设表示在时间区间内到达的顾客数，是随机变量。()Nt满足下列三个条件时，我们说顾客的到达符合泊松分布当00[,)ttt+∆()Nt0t（1）平稳性：在时间区间内到达的顾客数，只与区间长度无关。有关而与时间起点00[,)ttt+∆()Nt0t（2）无后效性：在时间区间内到达的顾客数，与以前到达的顾客数独立。。t∆()()2nnPtot∞=∆=∆∑（3）普通性：在充分短的时间区间内，到达两个或两个以上顾客的概率极小，可以忽略不计，即OperationsResearchcmLiu@shufe9.2.2泊松分布在满足上述三个条件下，可以推出在t时间段内有n个顾客到达服务系统的概率为()()!ntntPtenλλ−=0,1,2,n=0t≥0λ其中，为一常数，表示单位时间到达的顾客数，即为到达率。OperationsResearchcmLiu@shufe9.2.2泊松分布最简单流具有如下一些性质：性质1参数λ代表单位时间内平均到达的顾客数，即达到率。[],ttt+∆()01vttλ∆=−∆性质2在时间内没有顾客到达的概率为[],ttt+∆()1vttλ∆=∆性质3在时间内恰好有一个顾客到达的概率为由于最简单流与实际顾客到达流的相似性，更由于最简单流容易处理，因此到目前为止排队论中大量的研究都是基于最简单流的情况。OperationsResearchcmLiu@shufe9.2.3负指数分布(),00,0tetfttµµ−≥=若随机变量T的概率密度函数为则称T服从负指数分布。()Ftt(){}001tttttFtPTtedtdeeµµµµ−−−=≤==−=−∫∫表示的概率分布函数，则有用OperationsResearchcmLiu@shufe9.2.3负指数分布负指数分布具有下列性质：OperationsResearchcmLiu@shufe9.2.3负指数分布负指数分布具有下列性质：OperationsResearchcmLiu@shufe9.2.3负指数分布负指数分布具有下列性质：OperationsResearchcmLiu@shufe9.2.3负指数分布负指数分布具有下列性质：5.当顾客的到达服从泊松分布时，顾客到达的间隔时间必服从负指数分布，即顾客的达到时间服从泊松分布和顾客到达的间隔时间服从负指数分布是等价的。当依次到达排队系统的顾客服从负指数分布时，t时间区间内无顾客到达的概率为()()()()011tPTtPTtFtevtλ−=−≤=−==因而泊松分布和负指数分布是对同一顾客流(无论到达或服务完毕离去)按不同方式进行统计时得到的两种不同分布。OperationsResearchcmLiu@shufe9.2.4爱尔朗分布Ope