排队论详解及案例.pdf

Operations Research cmLiushufe 第九章第九章 排队论排队论 Operations Research cmLiushufe 第九章 排队论 在生产和日常生活中，人们会遇到很多排队现象，比如去火车站购票、到医院就诊、上银行办理业务以及要求起降的飞机、进港待泊的船只、工厂待修的机器等等。在这些问题中，售票员与买票人、医生与患者、银行工作人员与顾客、机场跑道与起降的飞机、港口的泊位与进港的船只、维修工与待修的机器等等，均构成一个排队系统或服务系统。在排队系统中，如果服务员（服务台）过少，会引起顾客的不满，影响排队系统的服务效率；如果服务员（服务台）过多，会增加服务机构的运营、维护成本。如何协调二者之间的关系，就需要用排队论的知识加以解决。排队论就是研究排队系统（又称随机服务系统）的一门数学理论和方法。它是在对各种排队系统概率规律性进行研究的基础上，解决排队系统的最优设计和最优控制问题。Operations Research cmLiushufe 第九章 排队论 9.1 基本概念 9.2 几个常用的概率分布 9.3 单服务台负指数分布的排队系统 9.4 多服务台负指数分布排队系统模型 9.5 一般服务时间M/G/1模型 9.6 排队系统的建模与优化 9.7 电子表格建模和求解 9.8 案例分析 办公室设施公司（OEI）服务能力分析 Operations Research cmLiushufe 9.1.1 排队系统的描述和组成 一般的排队过程可以这样描述：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。Operations Research cmLiushufe 9.1.1 排队系统的描述和组成 尽管排队系统是多种多样的，但所有的排队系统都是由输入过程、排队规则、服务机构及服务规则三个基本部分组成的。（1）输入过程输入过程 描述顾客来源以及顾客到达排队系统的规律。一般从以下几个方面对输入过程进行描述：顾客源中顾客的数量是有限还是无限；顾客到达的方式是单个到达还是成批到达；顾客的到达是否相互独立（以前到达的顾客对以后达到的顾客没有影响，则称顾客的达到是相互独立的，否则就是有关联的）；顾客相继到达的间隔时间分布是确定型的还是随机型的（如果是随机分布，需要知道单位时间内的顾客到达数或者顾客相继到达时间间隔的概率分布）；输入的过程是平稳的还是非平稳的（若相继到达的间隔时间分布参数（如期望值、方差等）都是与时间无关的，则称输入过程是平稳的，否则称为非平稳）。本章主要讨论顾客的到达是相互独立的、输入过程是平稳的情形。Operations Research cmLiushufe 9.1.1 排队系统的描述和组成（2）排队及排队规则排队及排队规则 描述顾客排队等待的队列和接受服务的次序，一般包括损失制、等待制和混合制三种。损失制：指排队空间为零的系统，即当顾客到达排队系统时，若所有的服务台均被占用（正在进行服务），则顾客离开系统，永不再来。等待制：当顾客到达排队系统时，若所有的服务台均被占用（正在进行服务），则顾客就加入排队行列等待服务，服务台按照下面的规则对顾客进行服务：先到先服务（FCFS）、后到先服务（FCLS）、随机服务（SIRO）、有优先权的服务（PR）混合制：是等待制和损失制系统的结合，一般是指允许排队，但又不允许队列无限长下去。具体来讲，分为以下三种：队长有限，即系统的等待空间是有限的；等待时间有限，即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来；逗留时间有限（等待时间和服务时间之和）。Operations Research cmLiushufe 9.1.1 排队系统的描述和组成（3）服务机构及服务规则服务机构及服务规则 指服务机构服务设施的个数、排列方式及服务方式，一般从以下几个方面进行描述：服务台（员）的数目：服务机构可以没有服务员，也可以有一个或者多个服务员；服务台的排列情况：有单队单服务台、单队多服务台、多对多服务台、串联多服务台及混合多服务台等多种形式；服务台（员）的服务方式：对顾客是单个服务还是成批进行服务，本章只研究对顾客进行单个服务的方式；服务时间：同输入过程一样，对顾客的服务时间也分确定型的还是随机型的，如果是随机分布，需要知道单位时间内服务的顾客数或者是对顾客相继服务的时间间隔的概率分布。服务时间的分布是平稳的，是指服务时间的分布参数（如期望值、方差等）都是与时间无关的。本章主要讨论服务时间的分布是平稳的情形。在排队论中，一般假设顾客相继到达的间隔时间和服务时间至少有一个是随机的。Operations Research cmLiushufe 9.1.2 排队模型的分类 Kendall符号X/Y/Z/A/B/C X表示顾客相继到达的间隔时间分布 Y表示服务时间的分布 Z表示并列的服务台个数 A表示系统容量限制 B表示顾客源中的顾客数目 C表示服务规则（如先到先服务FCFS，后到先服务LCFS）如略去后三项，即指X/Y/Z/FCFS的情形。Operations Research cmLiushufe 9.1.3 排队论研究的基本问题（1）排队系统工作状况的衡量 一个排队系统运行状况的好坏不仅会影响顾客的利益，也会影响服务机构的利益，甚至会影响到社会效果的好坏。通过研究运行系统在平衡状态下的概率分布及其数字特征，了解排队系统运行的效率、服务质量等等，进而可以判断系统运行状况的优劣。1）队长（队长（Ls）：排队系统中顾客的平均数（期望值），它是正在服务的 顾客和等待接受服务的顾客总数的期望值。其常用的主要衡量指标如下：2）队列长（队列长（Lq）：排队系统中平均等待服务顾客数的期望值。显然有 队长排队长正被服务的顾客数 3）逗留时间（逗留时间（Ws）：一个顾客从到达排队系统到服务完毕离去的总停留 时间的期望值。Operations Research cmLiushufe 9.1.3 排队论研究的基本问题 其常用的主要衡量指标如下：4）等待时间等待时间（Wq）：一个顾客在系统中排队等待的平均时间。显然有 逗留时间等待时间服务时间 5）忙期忙期：是指从顾客到达空闲着的服务机构，到服务机构再次成为空闲的 这段时间，即服务机构连续忙碌的时间，它代表了服务员的工作强度。6）闲期闲期：即服务机构连续保持空闲的时间。7）服务设备利用率服务设备利用率：服务设备工作时间占总时间的比例，这也是衡量服务 机构利用效率的指标。1=用于服务顾客的时间服务设备总的空闲时间服务机构工作强度服务设备总的服务时间服务设备总的服务时间8）顾客损失率顾客损失率：由于服务能力不足而造成的顾客流失的概率。该指标过高 会造成服务系统利润的减少。Operations Research cmLiushufe 9.1.3 排队论研究的基本问题（2）统计推断问题的研究 在建立实际问题的排队系统模型时，首先要对现实数据进行收集、处理，然后分析顾客相继到达的间隔时间是否相互独立，确定其分布的类型和相关参数，研究服务时间的独立性以及服务时间的分布等，在此基础上，选择适合该系统的排队模型，再用排队模型进行分析和研究。Operations Research cmLiushufe 9.1.3 排队论研究的基本问题（3）系统优化问题的研究 研究排队系统的目的就是通过对该系统概率规律的研究，实现系统的优化。系统的优化包括最优设计和最优运营问题。前者属于静态问题，它是在输入和服务参数给定的情况下，确定系统的设计参数，以使服务设施达到最大效益或者服务机构实现最为经济。后者属于动态问题，它是指对于一个给定的系统，在系统运行的参数可以随着时间或状态变化的情况下，考虑如何运营使某个目标函数达到最优。Operations Research cmLiushufe 9.1.3 排队论研究的基本问题 在一般情况下，随着服务水平的提高，服务费用会增加而等待费用会减少，系统的优化就是协调二者之间的矛盾，使服务系统既能适当地满足顾客的需求，又能使总费用最低（服务费用与等待费用之和）。其常用的优化的目标有二：一是确定最优的服务水平（最优服务率或最优的服务员（台）数）使总费用最小；二是使纯收入或利润（服务收入与服务成本之差）最大。Operations Research cmLiushufe 9.1.3 排队论研究的基本问题 这里的服务水平是指服务机构提供服务方面的能力，如服务台的个数、服务率等，服务费用是指达到相应服务水平所付出的费用，包括增加服务内容、提高服务率、组织动态服务台服务及管理支出的总费用，它一般随着服务水平的提高而上升；等待费用是指在相应的服务水平下，由于等待服务而产生的顾客及系统费用，包括顾客由于等待服务造成的损失费用、系统损失的顾客对系统造成的机会损失费用等，一般来讲它随着服务水平的提高而减少。Operations Research cmLiushufe 9.2 几个常用的概率分布 9.2.1 经验分布 9.2.2 泊松分布 9.2.3 负指数分布 9.2.4 爱尔朗分布 Operations Research cmLiushufe 9.2.1 经验分布 主要指标 =总时间平均间隔时间到达顾客总数=服务时间总和平均服务时间服务顾客总数=到达顾客总数平均到达率总时间=服务顾客总数平均服务率服务时间总和Operations Research cmLiushufe 9.2.2 泊松分布 泊松分布也称为泊松流，在排队论中称为最简单流。()N t00,)t tt+设 表示在时间区间 内到达的顾客数，是随机变量。()N t满足下列三个条件时，我们说顾客的到达符合泊松分布 当 00,)t tt+()N t0t（1）平稳性平稳性：在时间区间 内到达的顾客数，只与区间长度 无关。有关而与时间起点 00,)t tt+()N t0t （2）无后效性无后效性：在时间区间 内到达的顾客数，与 以前 到达的顾客数独立。t()()2nnPtot=（3）普通性普通性：在充分短的时间区间 内，到达两个或两个以上顾客的概率 极小，可以忽略不计，即 Operations Research cmLiushufe 9.2.2 泊松分布 在满足上述三个条件下，可以推出在t时间段内有n个顾客到达服务系统的 概率为 ()()!ntntP ten=0,1,2,n=0t 0其中，为一常数，表示单位时间到达的顾客数，即为到达率。Operations Research cmLiushufe 9.2.2 泊松分布 最简单流具有如下一些性质：性质1 参数 代表单位时间内平均到达的顾客数，即达到率。,t tt+()01vtt=性质2 在 时间内没有顾客到达的概率为,t tt+()1vtt=性质3 在 时间内恰好有一个顾客到达的概率为 由于最简单流与实际顾客到达流的相似性，更由于最简单流容易处理，因 此到目前为止排队论中大量的研究都是基于最简单流的情况。Operations Research cmLiushufe 9.2.3 负指数分布(),00,0tetf tt=因而泊松分布和负指数分布是对同一顾客流(无论到达或服务完毕离去)按 不同方式进行统计时得到的两种不同分布。Operations Research cmLiushufe 9.2.4 爱尔朗分布 Operations Research cmLiushufe 9.2.4 爱尔朗分布 爱尔朗分布图 Operations Research cmLiushufe 9.3 单服务台负指数分布的排队系统 9.3.1 标准M/M/1模型(M/M/1/)9.3.2 系统容量有限的排队模型(M/M/1/N/)9.3.3 顾客源为有限的排队模型(M/M/1/m)Operations Research cmLiushufe 9.3.1 标准M/M/1模型(M/M/1/)Operations Research cmLiushufe 9.3.1 标准M/M/1模型(M/M/1/)系统的状态()N t随时间变化的过程称为生灭过程生灭过程。排队系统的生灭过程可以用系统的状态转移图加以表示。M/M/1/排队系统的状态转移图 状态平衡方程()01111nnnnPPPPPP n+=+=+Operations Research cmLiushufe 9.3.1 标准M/M/1模型(M/M/1/)01=P(1),1nn=nPt时刻系统状态为n的概率为()01111nnnnPPPPPP n+=+=+01nnP=在该系统中=，是单位时间顾客平均达到率与平均服务率的比值，反映了服务机构的忙碌或利用的程度。Operations Research cmLiushufe 9.3.1 标准M/M/1模型(M/M/1/)其他指标：01(1)nsnnnLnPn=23234(23)(23)=+23=+1=01（1）平均队长平均队长 ，Operations Research cmLiushufe 9.3.1 标准M/M/1模型(M/M/1/)其他指标：（2）平均排队长平均排队长 11122(1)(1)()qnnnsnnnLnPnPPL=（3）正在接受服务的预期顾客数正在接受服务的预期顾客数 012001(.)11(1)nLPPPPP=+=sqLLL=+Operations Research cmLiushufe 9.3.1 标准M/M/1模型(M/M/1/)其他指标：ssLW=qqLW=1sqWW=+（4）平均逗留时间平均逗留时间 （5）平均等待时间平均等待时间 1每个顾客的平均服务时间为 Operations Research cmLiushufe 9.3.1 标准M/M/1模型(M/M/1/)例9.1 顾客到达只有一个服务员的快餐店的时间平均每6分钟一个，服务员对顾客的平均服务时间是4分钟，达到时间和服务时间都服从负指数分布。回答以下问题：（1）服务员空闲的概率；（2）排队等待服务员服务的平均顾客数；（3）顾客在快餐店平均的逗留时间；（4）服务员平均每小时将为多少顾客提供服务？Operations Research cmLiushufe 9.3.1 标准M/M/1模型(M/M/1/)Operations Research cmLiushufe 9.3.2 系统容量有限的排队模型(M/M/1/N/)基于输入率等于输出率原则，建立该系统的状态平衡方程()011111nnnnNNPPPPPPnNPP+=+=+=1=01NnnP=0111NP+=0,nnPPnN=Operations Research cmLiushufe 9.3.2 系统容量有限的排队模型(M/M/1/N/)其他指标：()11111NsNNL+=()01qsLLP=（1）平均队长平均队长（2）平均排队长平均排队长 Operations Research cmLiushufe 9.3.2 系统容量有限的排队模型(M/M/1/N/)其他指标：（3）有效到达率有效到达率 Operations Research cmLiushufe 9.3.2 系统容量有限的排队模型(M/M/1/N/)其他指标：sseLW=1qqseLWW=（4）平均逗留时间平均逗留时间 （5）平均等待时间平均等待时间 Operations Research cmLiushufe 9.3.2 系统容量有限的排队模型(M/M/1/N/)例9.2 某车间的工具仓库只有一个管理员，平均每小时有10个工人来领工具，到达过程为泊松分布，领工具的时间服从负指数分布，平均每7.5分钟服务一个工人。由于场地的限制，仓库内领工具的工人最多不超过4人。回答下列问题：（1）仓库内没有人领工具的概率；（2）有效达到率；（3）仓库内领工具的工人的平均数；（4）排队等待领工具的工人的平均数；（5）工人在系统中的平均花费时间；（6）工人在系统中的平均等待时间。Operations Research cmLiushufe 9.3.2 系统容量有限的排队模型(M/M/1/N/)Operations Research cmLiushufe 9.3.3 顾客源为有限的排队模型(M/M/1/m)状态平衡方程 ()()()011111nnnnmmm PPmnPPmnPP nmPP+=+=+=Operations Research cmLiushufe 9.3.3 顾客源为有限的排队模型(M/M/1/m)()()()011111nnnnmmm PPmnPPmnPP nmPP+=+=+=100!()()!miimPmi=0!(),()!1nmPnnPmnm =011mPPP+=Operations Research cmLiushufe 9.3.3 顾客源为有限的排队模型(M/M/1/m)其他指标：()01sLmP=()01qsLLP=()()01esmLP=（1）平均队长平均队长（2）平均排队长平均排队长（3）有效到达率有效到达率 sseLW=1qqseLWW=（4）平均逗留时间平均逗留时间 （5）平均等待时间平均等待时间 Operations Research cmLiushufe 9.3.3 顾客源为有限的排队模型(M/M/1/m)例9.3 设有一名技术工人照看5台机器，每台机器正常运转的时间服从负指数分布，平均为60分钟，每次修理时间服从负指数分布，平均为15分钟。回答下列问题：（1）工人空闲的概率；（2）发生故障机器的平均台数；（3）排队等待维修机器的平均台数；（4）机器平均停工时间；（5）机器排队等待的平均时间。Operations Research cmLiushufe 9.3.3 顾客源为有限的排队模型(M/M/1/m)Operations Research cmLiushufe 9.4 多服务台负指数分布排队系统模型 9.4.1 标准的M/M/c/模型（M/M/c/）9.4.2 系统容量有限的排队模型 9.4.3 顾客源为有限的排队模型(M/M/c/m)Operations Research cmLiushufe 9.4.1 标准的M/M/c/模型（M/M/c/）Operations Research cmLiushufe 9.4.1 标准的M/M/c/模型（M/M/c/）Operations Research cmLiushufe 9.4.1 标准的M/M/c/模型（M/M/c/）1100111()()!1ckckPkc=+001()()!1()()!nnnn cP ncnPP ncc c=状态平衡方程()()()()()01111111nnnnnnPPPnPnPncc PPcP nc+=+=+=+1c=01iiP=Operations Research cmLiushufe 9.4.1 标准的M/M/c/模型（M/M/c/）其他指标：()021()!(1)cqnn ccLnc PPc=+=（1）平均排队长平均排队长 sqLL=+（2）平均队长平均队长 ssLW=（3）平均逗留时间平均逗留时间 qqLW=（4）平均等待时间平均等待时间 Operations Research cmLiushufe 9.4.1 标准的M/M/c/模型（M/M/c/）例9.4 某银行有3个出纳员，顾客的达到服从泊松分布，平均每小时达到30人，所有的顾客排成一队。出纳员对顾客的服务时间服从负指数分布，平均每小时可服务12人。试求：（1）三名出纳员都忙的概率及该银行的主要运行指标；（2）若所有的顾客排成三队，顾客平均每小时达到10人，计算该银行的主要运行指标。（3）将（1）、（2）进行比较，会得出什么结论？Operations Research cmLiushufe 9.4.1 标准的M/M/c/模型（M/M/c/）Operations Research cmLiushufe 9.4.1 标准的M/M/c/模型（M/M/c/）Operations Research cmLiushufe 9.4.1 标准的M/M/c/模型（M/M/c/）（3）比较（1）和（2）不难发现，单队列的排队系统比多队列的排队系统的系统空闲的概率低，而且单队列队长比多队列长，逗留时间和等待时间也都比多队列长很多。可见，排队的方式对排队系统运行指标的影响还是比较大，因此在排队系统中应注重排队方式。Operations Research cmLiushufe 9.4.2 系统容量有限的排队模型()()()()()011111111nnnnnnNNPPPnPnPncc PPcP cnNc PP+=+=+=+=状态平衡方程 Operations Research cmLiushufe 9.4.2 系统容量有限的排队模型()()()()()011111111nnnnnnNNPPPnPnPncc PPcP cnNc PP+=+=+=+=001,1()().!1kccNckPcckc=+00()(0)!()!nncncPncnPcP cnNc=c=其中 Operations Research cmLiushufe 9.4.2 系统容量有限的排队模型 其他指标：02()1()(1)!(1)cN cN cqPcLNcc=(1)sqNLLcP=+(1)qqNLWP=1sqWW=+（1）平均排队长平均排队长（2）平均队长平均队长（3）平均等待时间平均等待时间（4）平均逗留时间平均逗留时间 Operations Research cmLiushufe 9.4.2 系统容量有限的排队模型 当 Nc=时，系统的最大容量与服务台个数相等时，系统将不存在可供等 待的空位，混合制变成即时制的情形，例如在街头的停车场就不允许排队 等待空位，这时系统的状态概率为：001()!kckPck=0(),0!nncPPncn=该系统的主要运行指标如下 0qL=0qW=1sW=11010()!(1)()!nccnsncncnnccnLnPcPcn=Operations Research cmLiushufe 9.4.2 系统容量有限的排队模型 Operations Research cmLiushufe 9.4.2 系统容量有限的排队模型 441=42c2 1=解：（1）根据题意，该模型是M/M/2/5/模型，则有 0225200110.008()()(4)22(22).!1!2!1 2kccNkckkPcckck=+2550220.0080.512!2!cncPPc=Operations Research cmLiushufe 9.4.2 系统容量有限的排队模型 5(1)0.976eP=02()1()(1)2.176!(1)cN cN cqPcLNcc=（辆）(1)4.128sqNLLcP=+=（辆）2.230(1)qqNLWP=（小时）13.230sqWW=+=（小时）有效达到率 等待维修的车辆的平均数 维修站中车辆的平均数 车辆在维修站的平均等待时间 车辆在维修站的平均逗留时间 Operations Research cmLiushufe 9.4.2 系统容量有限的排队模型（2）设维修站共有n个维修工人，这样就形成了一个M/M/n/5/模型，故 维修站损失顾客的概率为 5001()()()()!.!1ccnnkccNckccp nP ncccckc=+3n=41.33333 1=500.3340.35!cncPPc=当 时，上述结果表明，增加一名维修工人才能使维修站的损失顾客概率低于0.35。Operations Research cmLiushufe 9.4.3 顾客源为有限的排队模型(M/M/c/m)就整个服务机构而言，平均服务率也随着系统状态的变化而变化，即,nccnmnnc=Operations Research cmLiushufe 9.4.3 顾客源为有限的排队模型(M/M/c/m)该系统生灭过程的状态转移图如下 00111.11!()!()!()!ccmkkkk cPccmk mkmcmkm=+=+（）！00!()(0)()!()(1)()!nnnn cmPncmn nPmP cnmmn c c=+mc=Operations Research cmLiushufe 9.4.3 顾客源为有限的排队模型(M/M/c/m)各项指标如下：1msnnLnP=1()mqnn cLnc P=+=()esqqsLLLmL=+=+sseLW=qqeLW=()esmL=（1）平均队长（2）平均排队长 （3）平均逗留时间 （4）平均等待时间 （5）有效到达率 Operations Research cmLiushufe 9.4.3 顾客源为有限的排队模型(M/M/c/m)例9.6 某工厂有6台同类设备，按参数 为台/天的泊松流发生故障；现安排两名工人同时负责修理这6台设备，修理时间服从负指数分布，每个工人每天可修理3台设备。试求：（1）修理工空闲的概率、发生故障的机器台数、等待修理的机器台数、有效到达率、平均逗留时间及设备完好率；（2）若安排每个修理工人负责修理3台设备，试与（1）的指标进行比较。1=Operations Research cmLiushufe 9.4.3 顾客源为有限的排队模型(M/M/c/m)Operations Research cmLiushufe 9.4.3 顾客源为有限的排队模型(M/M/c/m)（2）若安排每个修理工人负责修理3台设备，则是两个 M/M/1/3模型，与原模型相比如下表所示 Operations Research cmLiushufe 9.5 一般服务时间M/G/1模型 9.5.1 Pollaczek-Khintchine(PK)公式 9.5.2 输入为泊分布服务时间为定长分布的排队系统 9.5.3 输入为泊分布服务时间为爱尔朗分布的排队系统 Operations Research cmLiushufe 9.5.1 Pollaczek-Khintchine(PK)公式 9.3和9.4讨论的模型都具有马尔可夫性，即由系统当前的状态可以推断未来的状态。但是，当输入的过程不是泊松分布或者服务时间不服从负指数分布时，仅知道系统内当前的顾客数，对于推断系统未来的状态是不够的，因为正在接受服务的顾客已经被服务了多长时间，将影响其离开系统的时间。对于这类系统可以通过“嵌入马尔可夫链”的方法，设法找出从状态 到状态 的概率转移方程，这样就可以将一个非马尔可夫问题转化为一个离散的马尔可夫链，从而求得分析问题的解。()0,1,2,n n=1n+Operations Research cmLiushufe 9.5.1 Pollaczek-Khintchine(PK)公式 对于一般的服务系统，假定（1）顾客的到达为参数为的泊松分布；（2）服务机构对每个顾客的服务时间t是相互独立的并且具有相同概率分()F t，其期望值和方差分别为 布的随机变量，其概率分布函数为 201()(),()E ttdF tVar t=（3）()1E t=（4）有一个服务站 Operations Research cmLiushufe 9.5.1 Pollaczek-Khintchine(PK)公式 将该问题转化为一个离散的马尔可夫链，可求得该系统的平均排队长为 2222(1)sL+=+上式被称为Pollaczek-Khintchine公式，其他的指标如下：2222(1)qsLL+=2222(1)qqLW+=222112(1)sqWW+=+=+Operations Research cmLiushufe 9.5.2 输入为泊分布服务时间为定长分布的排队系统（M/D/1）在生产和生活实践中，当一个服务机构提供固定的服务项目，服务时间偏 差很小时，可以近似地看作服务时间是定长分布。此时 ,01VaErtt=，于是有 22(1)sL=+22q2(1)2()L=22(1)2()qW=212(1)sW=+Operations Research cmLiushufe 9.5.2 输入为泊分布服务时间为定长分布的排队系统（M/D/1）Operations Research cmLiushufe 9.5.3输入为泊分布服务时间为爱尔朗分布的排队系统（M/Ek/1）如果服务机构对顾客进行的服务不是一项，而是按序进行的k项任务，若每一项服务的持续时间都是具有相同分布的负指数分布，则总的服务时间服从爱尔朗分布。如一种产品的生产需要4道加工工序，在每一道工序上加工的时间都服从相同分布的负指数分布，那么整个产品的加工时间就服从爱尔朗分布。Operations Research cmLiushufe 9.5.3输入为泊分布服务时间为爱尔朗分布的排队系统（M/Ek/1）Operations Research cmLiushufe 9.5.3输入为泊分布服务时间为爱尔朗分布的排队系统（M/Ek/1）运行指标 2222(1)2(1)2(1)skkLk+=+=+2(1)2(1)qkLk+=(1)2()qqLkWk+=1sqWW=+Operations Research cmLiushufe 例9.8 设有一电话亭，其顾客的达到服从泊松分布，平均每小时到达8人，通话时间服从爱尔朗分布，其平均通话时间为6分钟，方差为12分钟2。求该系统的平均排队长和顾客平均等待时间。9.5.3输入为泊分布服务时间为爱尔朗分布的排队系统（M/Ek/1）Operations Research cmLiushufe 9.6 排队系统的建模与优化 9.6.1 排队系统的建模 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.6.1 排队系统的建模 构建实际问题的排队系统模型时，首先要对实际问题的背景资料进行仔细的分析和认真的研究，根据问题的特征，如果能将该系统完全地归结为某一类排队模型（前面介绍的模型），则根据相应公式求出系统的运行指标；如果不能完全归结为前面介绍的排队模型，则需要画出系统的状态转移图，依据输入率等于输出率原则，建立系统的稳态方程，在此基础上求出系统的各项运行指标。Operations Research cmLiushufe 9.6.1 排队系统的建模 例9.9 某汽车修理部有4个停车位，当所有车位被占满时，新到达待修车辆则离去另求服务。前来寻求修理的汽车按泊松流到达，平均每天到达2辆。该修理部现有4个修理工，当待修车辆不足4辆时，空闲的修理工会协助修理。修理一辆汽车所需时间服从负指数分布，若1个修理工修理1辆汽车，则平均需3天；若4个修理工修理3辆汽车，则平均需2.5天；若4个修理工修理2辆汽车，则平均需2天；若4个修理工修理1辆汽车，则平均需0.75天。根据以上资料，回答下列问题：（1）画出系统的状态转移图；（2）求系统的状态概率；（3）求系统的损失率；（4）求系统中平均的汽车数量；（5）求每辆汽车在系统中逗留的时间。Operations Research cmLiushufe 9.6.1 排队系统的建模 M/M/4/4/=2解：（1）根据题意，该系统可归结为 系统，辆/天，41362531,3,44kkkkk=则该系统的状态转移图如下 Operations Research cmLiushufe 9.6.1 排队系统的建模 （2）根据输入率与输出率相等，该系统的状态转移方程为 04101324112233223142331400000PPPPPPPPPPPPu Pu PPP+=+=+=+=即 01012112322343343204322046220546220354203PPPPPPPPPPPPPPPP+=+=+=+=00.0320P=20.1708P=30.2847P=40.4270P=计算得，10.0854P=Operations Research cmLiushufe 9.6.1 排队系统的建模 40.4270P=系统损失率12342342.9891sLPPPP=+=()411.1459eP=2.6085sseWL=（3）（4）（辆/天）（天）（5）Operations Research cmLiushufe 9.6.2 排队系统的优化 排队系统的总费用包括服务费用和等待费用，一般来讲，随着服务水平的提高，服务费用会增加而等待费用会减少，系统的优化就是通过确定最优的服务水平，即最优服务率或最优的服务员（台）数，从而协调二者之间的矛盾，使服务系统既能适当地满足顾客的需求，又能使总费用最低。针对变量为离散变量和连续变量的不同，可分别采用边际分析法和微分法进行求解。Operations Research cmLiushufe 9.6.2 排队系统的优化（1）确定最优服务率 s()swTCcc L=+Operations Research cmLiushufe 9.6.2 排队系统的优化()swTCcc=+*wscc=+对于标准的M/M/1模型()0dTCd=，于是有()TC要使 最小，必须满足 Operations Research cmLiushufe 9.6.2 排队系统的优化（2）确定最优服务员（台）数c Operations Research cmLiushufe 9.6.2 排队系统的优化()TC c()TC c对于标准的M/M/c模型，由于c只能取整数值，不是 最小，必须满足 连续变量的函数，所以采用边际分析法进行分析，要使(*)(*1)(*)(*1)TC cTC cTC cTC c+s()swTC cc cc L=+将 代入上式，有 *(*)(*1)(*1)*(*)(*1)(*1)swsswsswsswsc cc L cccc L cc cc L cccc L c+化简后得最优服务台数应满足下式(*)(*1)(*1)(*)swcL cL cL cL cc+Operations Research cmLiushufe 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.6.2 排队系统的优化 例9.11 某公司有三台复印机供其雇员使用，但由于等待时间过长，经理正在考虑添加一台或多台打印机。该公司每年的工作时间为2000小时，来复印的雇员按平均每小时30人的泊松分布到达，对每名顾客的服务时间为平均5分钟的负指数分布。由于雇员在复印时造成效率的损失估计为每小时25元，每台复印机的租用费用为每年3000元。试决定该公司应配备多少台复印机，使其每小时总的期望费用为最小？Operations Research cmLiushufe 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.6.2 排队系统的优化 Operations Research cmLiushufe 9.7 电子表格建模和求解 例9.12 某乡镇月末水电费的收缴工作由甲乙两名职员完成。收电费的甲窗口的单据平均到达率服从每小时16的泊松分布，收水费的乙窗口的单据平均到达率服从每小时14的泊松分布。无论缴纳电费或水费，每次操作都服从平均3分钟的负指数分布。为了减少顾客的等待时间，有关部门提出了下列建议：（a）培训甲乙两名职员使其均熟悉缴纳电费和水费的操作流程；（b）将交纳电费和水费的群众排成一队，由两名职员来处理。试求：（1）按现有工作情况分别计算交纳电费和缴纳水费的顾客在系统中的停留时间，然后计算他们结合在一起的期望等待时间；（2）假定上述建