《排队论运筹学》PPT课件.ppt

第8章 排队论,本章内容重点,排队论基本概念基本问题与求解思路泊松输入指数服务排队模型其他模型选介排队系统的优化,排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。,前 言,排队论是1909年由丹麦工程师爱尔朗(A.KErlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。,前 言,1.排队论基本概念,排队是我们在日常生活和生产中经常遇到的现象:上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。,排队的不一定是人，也可以是物：通讯卫星与地面待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。,1.1 排队系统特征与基本过程,1)排队问题的共同特征 有要求某种服务的人或物。排队论里把要求服务的对象统称为“顾客”有提供服务的人或机构。把提供服务的人或机构称为“服务台”或“服务员”顾客的到达、服务的时间至少有一个是随机的，服从某种分布。,2)基本排队过程,任何一个排队问题的基本排队过程都可以用图 8-1表示：每个顾客由顾客源按照一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务后的顾客立即离开。,一般排队系统都可由下图（图8-1）描述,图8-1 随机服务系统,排队系统示意图,面对拥挤现象，顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是排队论所要研究解决的问题之一。,通常，排队系统都有输入过程、服务规则和服务台等3个组成部分：1)输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流一般可以从3个方面来描述一个输入过程。,1.2 排队系统的基本组成部分,1)输入过程,顾客总体数(又称顾客源、输入源)。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。,顾客到达方式。描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。,1)输入过程,1)输入过程,顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。流可以理解为在一定的时间间隔内到达k个顾客(k=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。,指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。损失制。如果顾客到达排队系统时，所有服务台都已被占用，那么他们就自动离开系统永不再来。,2)服务规则,等待制。当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。,2)服务规则,随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。优先权服务。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。,2)服务规则(等待制-续),混合制等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：队长有限。当排队系统中的顾客人数K超过规定数量时，后来的顾客就自动离去，另求服务，即系统的容量是有限的。,2)服务规则,等待时间有限。顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T 时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。,2)服务规则（混合制-续）,逗留时间有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为 t 时，若在这个时间内未被击落，就不可能再被击落了。注意：损失制和等待制可看成是混合制的特殊情形，如记 s 为系统中服务台的个数，则当 N=s 时，混合制即成为损失制；当N=时，混合制即成为等待制。,2)服务规则（混合制-续）,服务台可从以下三方面来描述：服务台数量及构成形式；服务方式；服务时间分布,3)服务台情况,服务台数量及构成形式（图8-28-6）单队单服务台式；单队多服务台并联式；多队多服务台并联式；单队多服务台串联式；单队多服务台并串联混合式及多队多服务台并串联混合式等等。,图8-2 单服务台排队系统,图8-3 单队列-S个服务台并联的排队系统,图8-4 S个队列-S个服务台的并联排队系统,图8-5 单队-多个服务台的串联排队系统,图8-6 多队-多服务台混联、网络系统,服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。服务时间的分布。在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。,3)服务台情况,为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，肯道尔（DGKendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：A/B/C/D/E/F 各符号的意义为：,1.3 排队系统的描述符号与分类,A表示顾客相继到达间隔时间分布，常用下列符号：M 表示到达过程为泊松过程或负指数分布；D 表示定长输入；Ek 表示k阶爱尔朗分布；G 表示一般相互独立的随机分布。,Kendall记号含义,Kendall记号含义,B 表示服务时间分布。所用符号与表示顾客到达间隔时间分布相同。M 表示服务过程为泊松过程或负指数分布；D 表示定长分布；Ek 表示k阶爱尔朗分布；G 表示一般相互独立的随机分布。,C表示服务台(员)个数：“1”则表示单个服务台，“s”(s1)表示多个服务台。D表示系统中顾客容量限额：如系统有N个位子，则 sN，当 N=s 时，说明系统不允许等待，即为损失制。N=时为等待制系统，此时一般省略不写。N为有限整数时，表示为混合制系统。,Kendall记号含义,Kendall记号含义,E表示顾客源（潜在顾客）数量。分有限与无限两种，表示顾客源无限，此时一般也可省略不写。F表示服务规则：常用下列符号 FCFS：表示先到先服务；LCFS：表示后到先服务；PR（priority）：表示优先权服务。,例如：某排队问题为 M/M/s/FCFS 则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。可简记为：M/M/s,Kendall记号含义,Kendall记号的默认含义,某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。省略应从后先前考虑：分别当第6、5、4个符号为FCFS、时，可依次考虑省略。,作业：,习题-1,研究排队系统的目的是通过了解系统运行的状况，对系统进行调整和控制，使系统处于最优运行状态。因此，首先需要弄清系统的运行状况。描述一个排队系统运行状况的主要数量指标有：,1.4 排队系统的主要数量指标,1)队长和排队长（队列长）队长是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和)排队长是指系统中正在排队等待服务的顾客数。队长和排队长一般都是随机变量。我们希望能确定它们的分布，或至少能确定它们的平均值(即平均队长和平均排队长)及有关的矩(如方差等)。,1.4 排队系统的主要数量指标,2)等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，是随机变量。从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量。对这两个指标的研究是希望能确定其分布，或至少能知道顾客的平均等待时间和平均逗留时间。,1.4 排队系统的主要数量指标,3)忙期和闲期忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个随机变量，它关系到服务员的服务强度。与忙期相对的是闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。,1.4 排队系统的主要数量指标,1.4 排队系统的主要数量指标,除了上述指标外，还会用到：损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的顾客损失率及服务强度等，也都是十分重要的数量指标。,4)一些数量指标的常用记号 N(t)：时刻t系统中的顾客数(又称为系统的状态)，即队长；Nq(t)：时刻t系统中排队的顾客数，即排队长；T(t)：时刻t到达系统的顾客在系统中的逗留时间；Tq(t)：时刻t到达系统的顾客在系统中的等待时间。,1.4 排队系统的主要数量指标,上面数量指标一般都是和系统运行的时间有关的随机变量，求它们的瞬时分布一般很困难。我们讨论平稳状态的情况。在平稳状态下，这些量与系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。,1.4 排队系统的主要数量指标,L或Ls 平均队长，稳态系统任一时刻的顾客数的期望值；Lq 平均等待队长或队列长，稳态系统任一时刻等待服务的顾客数期望值；W或Ws 平均逗留时间，在任意时刻进入稳态系统的顾客逗留时间期望值；Wq 平均等待时间，在任意时刻进入稳态系统的顾客等待时间期望值。,稳态下系统的统计性态指标,稳态下系统的统计性态指标,这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而对顾客而言系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。,s 系统中并联服务台的数目；平均到达率；1/平均到达间隔。平均服务率；1/平均服务时间。服务强度，即每个服务台单位时间内的平均服务时间；一般有 s；,稳态排队系统的参数,Pn=PN=n：稳态系统任一时刻状态为n的概率；特别当 n=0 时，Pn即P0，为稳态系统所有服务台全部空闲的概率。,稳态下系统的基本数量指标,对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已满，则自行消失。这就是说，到达的顾客不一定全部进入系统，设系统中有n个顾客时，每单位时间进入系统的顾客平均数为n，每单位时间离开系统的顾客平均数为n。我们引入：e 有效平均到达率，即每单位时间实际进入系统的平均顾客数（期望值），e=npn 对等待制的排队系统，有 e,平均有效离去率:e=n pn 同有效到达率一样，由于系统的容量有限，实际到达顾客是有损失的，既然顾客没有进入系统，其离去情况也必然受到影响。从平稳系统中均值的意义看，容易理解应有平均有效离去率等于平均有效到达率，即 e=e,L,Lq,e,W,Wq 之间的关系：L=e W Lq=e Wq 几何解释：稳态时，一个顾客，进入系统后，每单位时间平均到达e顾客。,队长L由时间段内W个e组成的,L=eW,5)Little公式,同理：Lq=eWq又 W=Wq+（1/）-W与Wq只相差一段平均服务时间1/L=Lq+(e/),5)Little公式,2.1 排队论研究的基本问题 排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。,2 基本问题与求解过程,2.1 排队论研究的基本问题,2)统计推断问题：建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。,2.1 排队论研究的基本问题,3)系统优化问题：基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。,1)重要的概率分布 排队系统中，常考虑的概率分布有如下几种，下面进行简单介绍，用表示时间随机变量、用N表示顾客数。定长输入。这是指顾客有规则地等距到达，每隔时间到达一个顾客。这时相继顾客到达间隔的分布函数F(t)为：,2.2 重要的概率分布与生灭过程,泊松(poisson)流(最简单流)。满足下面3个条件的输入称之为最简单流。平稳性。指在长度为t的时段内恰好到达k个顾客的概率仅与时段长度有关，而与时段起点无关。即对任意(0,)，在(,+t 或(0,t)内恰好到达k个顾客的概率相等；,1)重要的概率分布,无后效性。指在任意几个不相交的时间区间内，各自到达的顾客数是相互独立的。通俗地说就是以前到达的顾客情况，对以后顾客的到来没有影响。否则就是关联的；,1)重要的概率分布 poisson流,1)重要的概率分布 poisson流,单个性又称普通性。指在充分小的时段内最多到达一个顾客。因为泊松流实际应用最广，也最容易处理，因而研究得也较多可以证明，对于泊松流，在长度为t的时间内到达K个顾客的概率vk(t)服从泊松分布，即,其中参数0为一常数，表示单位时间内到达顾客的平均数，又称为顾客的平均到达率。负指数分布。对于泊松流，可以证明其相继顾客到达时间间隔i，i=1,2,是相互独立同分布的，其分布函数为负指数分布：,1)重要的概率分布 poisson流,k阶爱尔朗分布.这是指相继顾客到达时间间隔相互独立，具有相同的分布，其分布密度为其中k为非负整数。可以证明，在参数为的泊松输人中，对任意的j与k,设第j与第j+k个顾客之间的到达间隔为则随机变量Tk的分布必遵从参数为的爱尔朗分布。,例：某排队系统有并联的k个服务台，顾客流为泊松流，规定第i,k+i,2k+i 个顾客排入第i号台(i=1,2,k)，则第k台所获得的顾客流，即为k阶爱尔朗输入流，其他各台，从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流。此外，爱尔朗分布中，当k1时将化为负指数分布。,1)重要的概率分布 爱尔朗分布,2)生灭过程与状态转移速度图,生灭过程。假定一个系统具有状态集 S=0,1,2,N,并存在常数 n0 和 n0，n=1,2,N 当 t(t 0)时刻，记状态随机变量为K(t)，系统内有n个顾客的概率为Pn(t)，经过t 时间，如果满足,则称这个随机过程 K(t)：t 0 为有限状态S上的生灭过程。当系统具有可列无限状态集S=0,1,2,时,则称为无限状态的生灭过程。,2)生灭过程与状态转移速度图,状态转移速度图。我们把充分小的t 固定，直接用参数 n 和 n 表示 nt 和nt，生灭过程可利用状态转移速度图来描述“生”、“灭”导致状态转移的过程。注意，在实际上，n和n的取值不需要考虑t的大小，只要保证二者的基础时段一致即可（计算中考虑的是二者的比率）。,2)生灭过程与状态转移速度图,无限状态生灭过程的状态转移速度图如图：,状态转移速度图,状态转移速度图,根据泊松流的普通性，当t充分小时，在(t,t+t)时间段内有一个顾客到达的概率为 nt+o(t)，而无顾客到达的概率为1-nt+o(t)，故泊松输入指数服务排队系统的状态转移过程是生灭过程。因此，可以通过状态转移速度图研究状态概率之间的关系。,1)状态概率之间的关系:可以通过两种方式推导这种关系：直接通过概率发生情况讨论系统状态概率之间的关系。利用状态转移速度图导出各状态概率之间的关系。,直接通过概率发生情况讨论系统状态概率之间的关系：n：系统状态为n时，顾客进入系统的平均速度 n：系统状态为n时，顾客离开系统的平均速度 Pn(t)：t 时刻，系统内有n个顾客的概率。那么，在(t,t+t)有一个顾客到达概率为nt，无顾客到达的概率为 1-nt（根据普通性）。,各种方式发生概率表,Pn(t+t)=Pn(t)(1-nt)(1-nt)+Pn-1(t)n-1t(1-n-1t)+Pn+1(t)(1-n+1t)n+1t+Pn(t)ntntdPn(t)/dt=limt-0(Pn(t+t)-Pn(t)/t)=Pn-1(t)n-1-Pn(t)(n+n)+Pn+1(t)n+1(其中t2项都变为零),方式1,2,3,4互不相容且完备,于是,当n=0时，只有方式1和3，4发生，且方式1中无离去的概率为1，则 dP0(t)/dt=-P0(t)0+P1(t)1 我们假设系统是稳态的，即与时刻无关，于是可得：d Pn(t)/d t=0；,公式推导如下：,根据此各事件两两不相容，且完备，有 pn=1，于是 可求出 pn,n=0,1,2,利用状态转移速度图得到概率公式,由此图易得：转入率=转出率n=0，0P0=1P1n0，n-1Pn-1+n+1Pn+1=(n+n)Pn,公式推导如下：,根据此各事件两两不相容，且完备，有 pn=1，于是 可求出 pn,n=0,1,2,对排队系统运行情况的分析，通常是在给定输入与服务条件下，通过求解系统状态为n的概率Pn(t)，再计算其主要的运行指标:,根据已知条件绘制状态转移速度图。依据状态转移速度图写出各稳态概率之间的关系。求出 P0 及 Pn。,2)泊松输入负指数分布服务的排队系统的一般决策过程：,2)泊松输入负指数分布服务的排队系统的一般决策过程（续）,计算各项数量运行指标。用系统运行指标构造目标函数，对系统进行优化。,泊松输入-指数服务稳态排队系统的运行指标,系统中顾客数(队长)的期望值 排队等待的顾客数(排队长)的期望值,求出平均有效到达率e，再利用Little公式计算：顾客在系统中全部时间(逗留时间)的期望值W；顾客在系统中排队等待时间的期望值Wq。,例,某汽车加油站有两台加油泵为汽车加油，加油站内最多能容纳6辆汽车。已知顾客到达的时间间隔服从负指数分布，平均每小时到达18辆汽车。若加油站中已有K辆车，当K2时，有K/6的顾客将自动离去。加油时间服从负指数分布，平均每辆车需要5分钟。试求：,非标准的M/M/2/N模型,1）系统空闲的概率为多少？P02）求系统满的概率是多少？P63）求系统服务台不空的概率 P2+P3+P4+P5+P6=1-P0-P1 4）若服务一个顾客,加油站可以获得利润10元,问平均每小时可获得利润为多少元？10e5）求每小时损失掉的顾客数？损=-e,6）加油站平均有多少辆车在等待加油？Lq 平均有多少个车位被占？L7）进入加油站的顾客需要等多长的时间才能开始加油？Wq 进入加油站的顾客需要多长时间才能离去？W,稳态概率关系：P1=/P0=1.5P0=(3/2)P0P2=/(2)P1=0.75*1.5P0=(9/8)P0,解：状态转移速度图 以小时为单位=18=60/5=12,P3=(4/6)/(2)P2=(1/2)(9/8)P0=(9/16)P0 P4=(3/6)/(2)P3=(3/8)(9/16)P0=(27/128)P0P5=(2/6)/(2)P4=(1/4)(27/128)P0=(27/512)P0P6=(1/6)/(2)P5=(1/8)(27/512)P0=(27/4096)P0,由 P0+P1+P2+P3+P4+P5+P6=1解得：P0=0.22433,P1=0.33649，P2=0.25237，P3=0.12618，P4=0.04732，P5=0.01183，P6=0.00148。,1)P0=0.224332)P6=0.001483)P忙=1-P0-P1=0.439184)e=0P0+P1+2(P2+P3+P4+P5+P6)=14.578（辆/h）10e=145.78(元/小时）,运行指标：,5)损=-e=18-14.5782=3.4218（辆/h）6)Lq=(3-2)P3+(4-2)P4+(5-2)P5+(6-2)P6=0.26223 L=Lq+e/=0.26223+1.21485=1.47708,运行指标（续）,运行指标（续）,7)Wq=Lq/e=0.018h=1.08分钟 W=Wq+1/=0.101h=6.08分钟,车站候车室在某段时间旅客到达服从泊松分布，平均速度为50人/h，每位旅客在候车室内停留的时间服从负指数分布，平均停留时间为0.5h，问候车室内平均人数为多少？解：把旅客停留在候车室看做服务，于是系统为M/M/=50=1/0.5=2,例,稳态概率关系：Pn=/(n)Pn-1=1/n!(/)nP0 记=/=50/2=25,状态转移速度图:,因此，候车室平均人数为25人。,在排队系统中，由于顾客到达分布和服务时间分布不同、服务台数不同、队长有限无限、顾客源有限无限等的不同组合，就会有不胜枚举的不同排队模型。下面分析泊松输入-指数服务排队系统模型。,3 泊松输入-指数服务排队模型,1)M/M/1/:参数，稳态概率方程：Pn=(/)Pn-1=(/)nP0 令=/当 1时,n不收敛，故应1,n=0即,3.1 单服务台无限源系统,P0=1/(n)=1-或 P0=1-/n=0Pn=n(1-)或 Pn=(/)n(1-/),M/M/1/系统,M/M/1/系统,L=n(n-n+1)n=1=nn-nn+1 n=1 n=1=+nn-nn+1 n=2 n=1=+n+1 n=1=+2/(1-)=/(1-)=/(-)(=/),取出第一项,写成(n+1)n+1 n=1 与后一项合并,M/M/1/系统,这里:e=（容量无限，顾客无损失）Little公式:W=L/e=1/(-)Wq=W-1/=/(-)=W Lq=Wq=2/(-)=L系统内顾客数多于k个的概率 P(N k)=k+1顾客逗留时间超过t的概率 P(U t)=e-()t,设忙期、闲期和忙的概率、闲的概率分别为 T忙、T闲、p忙、p闲，那么可以计算忙期和闲期。注意，,M/M/1/系统 其他指标,例82 P216,某医院急诊室同时只能诊治1个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。,3.1 单服务台无限源系统,2)M/M/1/N/参数,系统状态转移速度：稳态概率方程：Pn=(/)Pn-1=(/)nP0,1n N,由,M/M/1/N/系统,e=npn=(1-pN)+0pN=(1-pN)(只有pN不再进人，故N=0，其余均为)e=npn=0p0+(1-p0)（同理）W=L/e,Wq=W-(1/),Lq=Wqe,M/M/1/N/系统,3)损失制M/M/1/1:顾客到达若服务台被占用立即离开。直接可得：P1=P0;P0+P1=1 P0=1/(1+)=/(+)P闲=P0=/(+)P损=P忙=P1=/(+),3.1 单服务台无限源系统,例83 P218,1)M/M/s/系统 参数，稳态概率应满足的关系：当ns时，pn=/(n)pn-1当ns时，Pn=/(s)pn-1 令=/(s)系统负荷强度系数,3.2 多服务台无限源系统,此系统中，当=/(s)1时，不收敛，设1,M/M/s/系统,根据，可得到 Lq=sss+1p0/s!(1-)2利用 Little 公式得到 Wq=Lq/,W=Wq+1/,L=W=Lq+/,M/M/s/系统,某火车站售票处有三个窗口，同时售各车次的车票。顾客到达服从泊松分布，平均每分钟到达=0.9(人)，服务时间服从负指数分布，平均服务率每小时=24(人)，分两种情况讨论：1.顾客排成一队，依次购票；2.顾客在每个窗口排一队，不准串队。求:1）售票处空闲的概率。2）平均等待时间和逗留时间。3）队长和队列长。,例,单位一致：=0.4(人/分钟)=/(3)=0.75稳态概率：,解：情况1.M/M/3/,解：情况1.M/M/3/续,由得,解：情况1.M/M/3/续,记 先求积分，再求微分,解：情况1.M/M/3/续,售票处的空闲的概率为0.0748平均等待时间 Wq=1.893分钟，平均逗留时间 W=4.393分钟队长 L=3.954(人)Lq=1.704(人),有1个窗口空闲 0.18934有2个窗口空闲 0.1683,参数=0.3=0.4=/=0.75利用公式，1个服务台有空 p0=1-=0.25 2个、3个服务台有空:p02=0.0625 和 p03=0.0156L=/(1-)=3 e=0.3用Little公式：Lq=L-/=2.25,W=L/=10,Wq=W-1/=7.5,情况2 M/M/1/3个系统并联,故售票处空闲的概率为 0.0156平均等待时间 Wq=7.5分钟 平均逗留时间 W=10分钟队长 L=3 三个队 共3+3+3=9队列长 Lq=2.25 共6.75（人）显然，排一队共享3个服务台效率高。,解：情况2.M/M/1/续,有1个窗口空闲 0.25有2个窗口空闲 0.0625,2)M/M/c/N/稳态概率应满足的关系：当nc时，当nc时，,3.2 多服务台无限源系统,令=/(c)，根据 pn=1，可得,M/M/c/N/系统,运行指标：,M/M/c/N/系统,同单服务台情况的分析，e=(1-pN)利用 Little 公式，可求得 Wq=Lq/e W=Wq+1/L=We=Lq+e/,M/M/c/N/系统,此即M/M/c/N中 N=c 的情形 损=-e=pc，损失率=损/=pc,3)M/M/c/c/损失制系统,3.3 有限源排队系统,1)M/M/1/m/m系统顾客源是m个，那么系统容量实质上最多有m个足够。,1)M/M/1/m/m系统,稳态概率方程：由概率性质，得,1)M/M/1/m/m系统,根据e=(m-L)=e=(1-p0),得 L=m-/(1-p0)再利用Little公式，可求得 W=L/e Wq=W-1/Lq=Wqe,2)M/M/c/m/m系统,稳态概率方程,代入 pn=1 得,同前，,M/M/c/m/m系统,进一步可得：可求出L和e，再利用Little公式，得,M/M/c/m/m系统,4 其他模型选介,1)M/G/1排队系统 设顾客平均到达率为，服务时间为随机变量V，且E(V)=1/，D(V)=2 那么，服务强度，当 1时 p0=1-根据波拉切克-欣钦（Pollaczek-Khinchine）公式可导出 Lq=(2+)/2(1-)其它量的计算同前。,4 其他模型选介,2)M/D/1排队系统 设顾客平均到达率为，服务时间为常数v，则 E(v)=v=1/,D(v)=0那么，服务强度，当 1时 p0=1-根据上一模型的公式可直接得到 Lq=2/2(1-)其它量的计算同前。,5 排队系统的优化目标与最优化问题,从经济角度考虑，排队系统的费用应该包含以下两个方面：一个是服务费用，它是服务水平的递增函数；另一个是顾客等待的机会损失(费用)，它是服务水平的递减函数。两者的总和呈一条U形曲线。,排队系统优化问题,系统最优化的目标就是寻求上述合成费用曲线的最小点。排队系统的最优化问题通常分为两类：系统的静态最优设计，目的在于使设备达到最大效益；系统动态最优运营，是指一个给定排队系统，如何运营可使某个目标函数得到最优。,排队系统常见的优化问题,1)确定最优服务率*；2)确定最佳服务台数量s*；3)选择最为合适的服务规则；4)或是确定上述几个量的最优组合。研究排队系统的根本目的在于以最少的设备得到最大的效益。,本节讨论的排队系统优化问题,本章只讨论系统静态的最优设计问题。这类问题一般可以借助于前面所得到的一些表达式来解决。本节就，s 这两个决策变量的分别单独优化，介绍两个较简单的模型。,5.1 M/M/1/系统的最优平均服务率*,设：c1 当=1时服务系统单位时间的平均费 cw 平均每个顾客在系统逗留单位时间的损失；y 系统单位时间的平均总费用。其中 c1，cw 均为可知。则目标函数为,求解过程,将L=(-)，代入上式，得 y 是关于决策变量 的一元非线性函数,由一阶条件解得驻点,求解过程（续）,根号前取正号是为了保证，这样，系统才能达到稳态。又由二阶条件()可知求出的*为(,)上的全局唯一最小点。将*代入y中，可得最小总平均费用,求解过程（续）,另外，若设cw为平均每个顾客在队列中等待单位时间的损失，则需用 取代前式中的L，这时类似可得一阶条件：这一般采用数值法(如牛顿法)确定其根*。,兴建一座港口码头，只有一个装卸船只的泊位。要求设计装卸能力，单位为（只/日）船数。已知：单位装卸能力的平均生产费用a=2千元，船只逗留每日损失b=1.5千元。船只到达服从泊松分布，平均速率=3只/日。船只装卸时间服从负指数分布。目标是每日总支出最少。,例,=3 待定 模型 M/M/1/队长 Ls=/(-)总费用 c=a+bL=a+b/(-)求导 dc/d=a+(-b)/(-)2=0得:-=(b/a)1/2（根据题意舍负）所以=+(b/a)1/2=3+(2.25)1/2=4.5(只/日),解：,5.2 M/M/s/系统的最优服务台数s*,设目标函数为其中：s 并联服务台的个数(待定)；f(s)整个系统单位时间的平均总费用，它是关于服务台数s的函数；c2单位时间内平均每个服务台的费用；,求解过程,cw 平均每个顾客在系统中逗留(或等待)单位时间的损失；L(s)平均队长(或平均等待队长)，它是关于服务台数s的函数；要确定最优服务台数s*1，2，使 由于s取值离散，不能采用微分法或非线性规划的方法，因此我们采用差分法。显然有,求解过程（续）,得由此得令 依次计算s=1，2，时的L(s)值及每一差值L(s)-L(s+1)，根据 落在哪两个差值之间就可确定 s*。,建造一口码头，要求设计装卸船只的泊位数。已知:预计到达=3只/天，泊松流；装卸=2只/天，负指数分布。装卸费每泊位每天a=2千元，停留损失费b=1.5千元/日。目标是总费用最少。解:模型 M/M/s/s待定 总费用：F=as+bL(s)离散，无法用求导来解。,例,求解过程（续）,考虑:M/M/s/要求:=/(c)/=1.5只需讨论 s=2,3,4,利用公式计算，可得下表,计算结果,结论：s=3 即设计3个装卸泊位可使每天的总费用最少为8.60526千元。,例,某市政府的上访接待室每天平均接待来访48次，来访者为泊松流，每天上访所造成的损失为平均每次20元。该室每设置一名接待员的服务成本为平均每天8元，接待时间为指数分布，平均每天可接待25次。问应设置几名接待员能使平均总费用为最小?解:这是一个 M/M/s/系统,求解过程 续,注意，c28(元人天)，cw20(元天次)，48(次天)，(25次天)，则 0.4，另有,求解过程 续,把 代入前式，得又由根据 Little 公式，可得,求解过程 续,注意，系统应满足稳态条件，即只需依次计算当s2，3，时的L(s)值及其差值L(s)-L(s+1)，如下表所示。,求解过程 续,由表所示，可知：S*4(人),据此可得最小总平均费用：故该室应设置4名接待员可使每天总平均费用达到最小，为7326元。,求解过程 续,作业 P235 2,3,4,