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

第第8 8章章 排队论排队论本章内容重点本章内容重点排队论基本概念排队论基本概念基本问题与求解思路基本问题与求解思路泊松输入泊松输入指数服务排队模型指数服务排队模型其他模型选介其他模型选介排队系统的优化排队系统的优化 排排队队论论(Queuing(Queuing Theory)Theory)，又又称称随随机机服服务务系系统统理理论论(Random(Random Service Service System System Theory),Theory),是是一一门门研研究究拥拥挤挤现现象象(排排队队、等等待待)的的科科学学。具具体体地地说说，它它是是在在研研究究各各种种排排队队系系统统概概率率规规律律性性的的基基础础上上，解解决决相相应应排排队队系系统统的的最最优优设设计和最优控制问题。计和最优控制问题。前前 言言 排排队队论论是是19091909年年由由丹丹麦麦工工程程师师爱爱尔尔朗朗(A.K(A.KErlang)Erlang)在在研研究究电电活活系系统统时时创创立立的的，几几十十年年来来排排队队论论的的应应用用领领域域越越来来越越广广泛泛，理理论论也也日日渐渐完完善善。特特别别是是自自二二十十世世纪纪6060年年代代以以来来，由由于于计计算算机机的的飞飞速速发发展展，更更为为排排队队论论的的应应用用开开拓了宽阔的前景。拓了宽阔的前景。前前 言言1.1.排队论基本概念排队论基本概念 排队是我们在日常生活和生产中经常排队是我们在日常生活和生产中经常遇到的现象遇到的现象:上、下班搭乘公共汽车；上、下班搭乘公共汽车；顾客到商店购买物品；顾客到商店购买物品；病员到医院看病；病员到医院看病；旅客到售票处购买车票；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等学生去食堂就餐等就常常出现排队和等待现象。待现象。排队的不一定是人，也可以是物：排队的不一定是人，也可以是物：通讯卫星与地面待传递的信息；通讯卫星与地面待传递的信息；生产线上的原料、半成品等待加工；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；码头的船只等待装卸货物；要要降降落落的的飞飞机机因因跑跑道道不不空空而而在在空空中中盘盘旋等等。旋等等。1.1 排队系统特征与基本过程排队系统特征与基本过程1)排队问题的共同特征排队问题的共同特征 有要求某种服务的人或物。排队论里有要求某种服务的人或物。排队论里把要求服务的对象统称为把要求服务的对象统称为“顾客顾客”有提供服务的人或机构。把提供服务有提供服务的人或机构。把提供服务的人或机构称为的人或机构称为“服务台服务台”或或“服务员服务员”顾客的到达、服务的时间至少有一个顾客的到达、服务的时间至少有一个是是随机随机的，服从某种分布。的，服从某种分布。2)基本排队过程基本排队过程 任何一个排队问题的基本排队任何一个排队问题的基本排队过程都可以用图过程都可以用图 8-1 8-1表示：每个顾表示：每个顾客由顾客源按照一定方式到达服务客由顾客源按照一定方式到达服务系统，首先加入队列排队等待接受系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务列中选择顾客进行服务，获得服务后的顾客立即离开。后的顾客立即离开。一般排队系统都可由下图（一般排队系统都可由下图（图图8-1）描述）描述图图8-1 8-1 随机服务系统随机服务系统排队系统示意图排队系统示意图 面面对对拥拥挤挤现现象象，顾顾客客排排队队时时间间的的长长短短与与服服务务设设施施规规模模的的大大小小，就就构构成成了了设设计计随机服务系统中的一对矛盾。随机服务系统中的一对矛盾。如如何何做做到到既既保保证证一一定定的的服服务务质质量量指指标标，又又使使服服务务设设施施费费用用经经济济合合理理，恰恰当当地地解解决决顾顾客客排排队队时时间间与与服服务务设设施施费费用用大大小小这这对对矛矛盾盾，这这就就是是排排队队论论所所要要研研究究解解决决的的问题之一。问题之一。通通常常，排排队队系系统统都都有有输输入入过过程程、服务规则服务规则和和服务台服务台等等3 3个组成部分：个组成部分：1)1)输输入入过过程程这这是是指指要要求求服服务务的的顾顾客客是是按按怎怎样样的的规规律律到到达达排排队队系系统统的的过过程程，有有时时也也把把它它称称为为顾顾客客流流一一般般可可以以从从3 3个方面来描述一个输入过程。个方面来描述一个输入过程。1.2 1.2 排队系统的基本组成部分排队系统的基本组成部分1)1)输入过程输入过程 顾顾客客总总体体数数(又又称称顾顾客客源源、输输入入源源)。这这是是指指顾顾客客的的来来源源。顾顾客客源源可可以以是是有有限限的的，也也可可以以是是无无限限的的。例例如如，到到售售票票处处购购票票的的顾顾客客总总数数可可以以认认为为是是无无限限的的，而而某某个个工工厂厂因因故故障障待待修修的的机机床床则则是是有有限的。限的。顾顾客客到到达达方方式式。描描述述顾顾客客是是怎怎样样来来到到系系统统的的，他他们们是是单单个个到到达达，还还是是成成批批到到达达。病病人人到到医医院院看看病病是是顾顾客客单单个个到到达达的的例例子子。在在库库存存问问题题中中如如将将生生产产器器材材进进货货或或产产品品入入库库看看作作是是顾顾客客，那么这种顾客则是成批到达的。那么这种顾客则是成批到达的。1)1)输入过程输入过程1)输入过程输入过程 顾顾客客流流的的概概率率分分布布，或或称称相相继继顾顾客客到到达达的的时时间间间间隔隔的的分分布布。这这是是求求解解排排队队系系统统有有关关运运行行指指标标问问题题时时，首首先先需需要要确确定定的的指指标标。流流可可以以理理解解为为在在一一定定的的时时间间间间隔隔内内到到达达k个个顾顾客客(k=1、2、)的的概概率率是是多多大大。顾顾客客流流的的概概率率分分布布一一般般有有定定长长分分布布、二二项项分分布布、泊泊松松流流(最最简简单流单流)、爱尔朗分布等若干种。、爱尔朗分布等若干种。指指服服务务台台从从队队列列中中选选取取顾顾客客进进行行服服务务的的顺顺序序。一一般般可可以以分分为为损损失失制制、等待制等待制和和混合制混合制等等3 3大类。大类。损损失失制制。如如果果顾顾客客到到达达排排队队系系统统时时，所所有有服服务务台台都都已已被被占占用用，那那么么他他们就自动离开系统永不再来。们就自动离开系统永不再来。2)服务规则服务规则 等等待待制制。当当顾顾客客来来到到系系统统时时，所所有有服服务务台台都都不不空空，顾顾客客加加入入排排队队行行列列等等待待服服务务。等等待待制制中中，服服务务台台在在选选择择顾顾客客进进行行服服务务时时，常常有如下四种规则：有如下四种规则：先先到到先先服服务务。按按顾顾客客到到达达的的先先后后顺顺序序对对顾顾客进行服务，这是最普遍的情形。客进行服务，这是最普遍的情形。后后到到先先服服务务。仓仓库库中中迭迭放放的的钢钢材材，后后迭迭放放上去的都先被领走，就属于这种情况。上去的都先被领走，就属于这种情况。2)服务规则服务规则随随机机服服务务。即即当当服服务务台台空空闲闲时时，不不按按照照排排队队序序列列而而随随意意指指定定某某个个顾顾客客去去接接受受服服务，如电话交换台接通呼叫电话就是一例。务，如电话交换台接通呼叫电话就是一例。优优先先权权服服务务。如如老老人人、儿儿童童先先进进车车站站；危危重重病病员员先先就就诊诊；遇遇到到重重要要数数据据需需要要处处理理计计算算机机立立即即中中断断其其他他数数据据的的处处理理等等，均均属属于此种服务规则。于此种服务规则。2)服务规则服务规则(等待制等待制-续续)混混合合制制等等待待制制与与损损失失制制相相结结合合的的一一种种服服务务规规则则，一一般般是是指指允允许许排排队队，但但又又不不允允许许队队列列无无限限长长下下去去。具具体体说说来来，大致有三种：大致有三种：队队长长有有限限。当当排排队队系系统统中中的的顾顾客客人人数数K超超过过规规定定数数量量时时，后后来来的的顾顾客客就就自自动动离离去去，另另求求服服务务，即即系系统统的的容容量量是是有有限限的。的。2)服务规则服务规则等等待待时时间间有有限限。顾顾客客在在系系统统中中的的等等待待时时间间不不超超过过某某一一给给定定的的长长度度T，当当等等待待时时间间超超过过T 时时，顾顾客客将将自自动动离离去去，并并不不再再回回来来。如如易易损损坏坏的的电电子子元元器器件件的的库库存存问问题题，超超过过一一定定存存储储时时间间的的元元器器件件被被自自动动认认为为失失效效。又又如如顾顾客客到到饭饭馆馆就就餐餐，等等了了一一定定时时间间后不愿再等而自动离去另找饭店用餐。后不愿再等而自动离去另找饭店用餐。2)服务规则服务规则（混合制（混合制-续）续）逗逗留留时时间间有有限限。例例如如用用高高射射炮炮射射击击敌敌机机，当当敌敌机机飞飞越越高高射射炮炮射射击击有有效效区区域域的的时时间间为为 t 时时，若若在在这这个个时时间间内内未未被被击击落落，就就不不可可能能再再被击落了。被击落了。注意注意：损失制和等待制可看成是混合制损失制和等待制可看成是混合制的特殊情形，如记的特殊情形，如记 s 为系统中服务台的个数，为系统中服务台的个数，则当则当 N=s 时，混合制即成为损失制；当时，混合制即成为损失制；当N=时，混合制即成为等待制。时，混合制即成为等待制。2)服务规则服务规则（混合制（混合制-续）续）服务台可从以下三方面来描述：服务台可从以下三方面来描述：1.1.服务台数量及构成形式；服务台数量及构成形式；2.2.服务方式；服务方式；3.3.服务时间分布服务时间分布3)服务台情况服务台情况 服务台数量及构成形式（图服务台数量及构成形式（图8-28-6）单队单队单服务台式；单服务台式；单队单队多服务台并联式；多服务台并联式；多队多队多服务台并联式；多服务台并联式；单队单队多服务台串联式；多服务台串联式；单队单队多服务台并串联混合式及多队多服务台并串联混合式及多队多服务多服务台并串联混合式等等。台并串联混合式等等。图图8-2 8-2 单服务台排队系统单服务台排队系统图图8-3 8-3 单队列单队列-S-S个服务台并联的排队系统个服务台并联的排队系统图图8-4 S8-4 S个队列个队列-S-S个服务台的并联排队系统个服务台的并联排队系统图图8-5 8-5 单队单队-多个服务台的串联排队系统多个服务台的串联排队系统图图8-6 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个个位位子子，则则 s N00为为一一常常数数，表表示示单单位位时时间间内内到到达达顾顾客客的的平平均均数数，又又称称为为顾顾客客的的平平均均到达率。到达率。负负指指数数分分布布。对对于于泊泊松松流流，可可以以证证明明其其相相继继顾顾客客到到达达时时间间间间隔隔 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 表示表示 n t 和和 n t，生灭过程可利用状态转移速度图来描，生灭过程可利用状态转移速度图来描述述“生生”、“灭灭”导致状态转移的过程。注意，导致状态转移的过程。注意，在实际上，在实际上，n和和 n的取值不需要考虑的取值不需要考虑t的大的大小，只要保证二者的基础时段一致即可（计小，只要保证二者的基础时段一致即可（计算中考虑的是二者的比率）。算中考虑的是二者的比率）。2)生灭过程与状态转移速度图生灭过程与状态转移速度图无限状态生灭过程的状态转移速度无限状态生灭过程的状态转移速度图如图图如图：状态转移速度图状态转移速度图0n123021n-1n1n32n+1状态转移速度图状态转移速度图 根根据据泊泊松松流流的的普普通通性性，当当t充充分分小小时时，在在(t,t+t)时时间间段段内内有有一一个个顾顾客客到到达达的的概概率率为为 nt+o(t)，而而无无顾顾客客到到达达的的概概率率为为1-nt+o(t)，故故泊泊松松输输入入指指数数服服务务排排队队系系统统的的状状态态转转移移过过程程是是生生灭灭过过程程。因因此此，可可以以通通过过状状态态转转移移速速度度图图研研究究状状态态概概率率之之间间的的关系。关系。1)状态概率之间的关系状态概率之间的关系:可以通过两种方式推导这种关系：可以通过两种方式推导这种关系：直直接接通通过过概概率率发发生生情情况况讨讨论论系系统统状态概率之间的关系。状态概率之间的关系。利利用用状状态态转转移移速速度度图图导导出出各各状状态态概率之间的关系。概率之间的关系。直直接接通通过过概概率率发发生生情情况况讨讨论论系系统统状状态态概概率之间的关系：率之间的关系：n：系统状态为系统状态为n时，顾客进入系统的平均速度时，顾客进入系统的平均速度 n：系统状态为系统状态为n时，顾客离开系统的平均速度时，顾客离开系统的平均速度 Pn(t)：t 时刻，系统内有时刻，系统内有n个顾客的概率。个顾客的概率。那那么么，在在(t,t+t)有有一一个个顾顾客客到到达达概概率率为为 n t，无无顾顾客客到到达达的的概概率率为为 1-n t（根根据据普普通性）。通性）。各种方式发生概率表各种方式发生概率表 Pn(t+t)=Pn(t)(1-n t)(1-n t)+Pn-1(t)n-1 t(1-n-1 t)+Pn+1(t)(1-n+1 t)n+1 t +Pn(t)n t n tdPn(t)/dt=lim t-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)Pn0n123021n-1n1n32n+1公式推导如下：公式推导如下：根根据据此此各各事事件件两两两两不不相相容容，且且完完备，有备，有 pn=1，于是于是 可求出可求出 pn,n=0,1,2,对对排排队队系系统统运运行行情情况况的的分分析析，通通常常是是在在给给定定输输入入与与服服务务条条件件下下，通通过过求求解解系系统统状状态态为为n的的概概率率Pn(t)，再计算其主要的运行指标，再计算其主要的运行指标:根据已知条件绘制状态转移速根据已知条件绘制状态转移速度图。度图。依据状态转移速度图写出各稳依据状态转移速度图写出各稳态概率之间的关系。态概率之间的关系。求出求出 P0 及及 Pn。2)泊松输入泊松输入负指数分布服务的排队负指数分布服务的排队系统的一般决策过程：系统的一般决策过程：2)泊松输入泊松输入负指数分布服务的负指数分布服务的排队系统的一般决策过程（续）排队系统的一般决策过程（续）计算各项数量运行指标。计算各项数量运行指标。用系统运行指标构造目标函数，用系统运行指标构造目标函数，对系统进行优化。对系统进行优化。泊松输入泊松输入-指数服务指数服务稳态稳态排队系统排队系统的运行指标的运行指标 系统中顾客数系统中顾客数(队长队长)的期望值的期望值 排队等待的顾客数排队等待的顾客数(排队长排队长)的期望值的期望值 求出平均有效到达率求出平均有效到达率 e，再再利用利用Little公式计算：公式计算：顾客在系统中全部时间顾客在系统中全部时间(逗留逗留时间时间)的期望值的期望值W；顾客在系统中排队等待时间顾客在系统中排队等待时间的期望值的期望值Wq。例例某某汽汽车车加加油油站站有有两两台台加加油油泵泵为为汽汽车车加加油油，加加油油站站内内最最多多能能容容纳纳6辆辆汽汽车车。已已知知顾顾客客到到达达的的时时间间间间隔隔服服从从负负指指数数分分布布，平平均均每每小小时时到到达达18辆辆汽汽车车。若若加加油油站站中中已已有有K辆辆车车，当当K 2时时，有有K/6的的顾顾客客将将自自动动离离去去。加加油油时时间间服服从从负负指指数数分分布布，平平均均每每辆辆车车需需要要5分分钟钟。试试求：求：非标准的非标准的M/M/2/NM/M/2/N模型模型1）系统空闲的概率为多少？）系统空闲的概率为多少？P02）求系统满的概率是多少？）求系统满的概率是多少？P63）求系统服务台不空的概率）求系统服务台不空的概率 P2+P3+P4+P5+P6=1-P0-P1 4）若服务一个顾客）若服务一个顾客,加油站可以获得加油站可以获得利润利润10元元,问平均每小时可获得利润问平均每小时可获得利润为多少元？为多少元？10 e5）求每小时损失掉的顾客数？）求每小时损失掉的顾客数？损损=-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=1222 2205124632(1-2/6)(1-3/6)(1-4/6)(1-5/6)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.22433P1=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）10 e=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)7)W Wq q=L Lq q/e e=0.018h=1.08=0.018h=1.08分钟分钟 W W=W Wq q+1/+1/=0.101h=6.08=0.101h=6.08分钟分钟 在在排排队队系系统统中中，由由于于顾顾客客到到达达分分布布和和服服务务时时间间分分布布不不同同、服服务务台台数数不不同同、队队长长有有限限无无限限、顾顾客客源源有有限限无无限限等等的的不不同同组组合合，就就会会有有不不胜胜枚枚举举的的不不同同排排队队模模型型。下下面面分分析析泊泊松输入松输入-指数服务排队系统模型。指数服务排队系统模型。3 3 泊松输入泊松输入-指数服务排队模型指数服务排队模型 1)M/M/1/:参数参数 ，稳态概率方程：稳态概率方程：Pn=(/)Pn-1=(/)nP0 令令=/当当 1时时,n不收敛，故应不收敛，故应1,n=0即即 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 N0N-112N-2N 由由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=Wq e 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 P2181)M/M/s/系统系统 参数参数 ，稳态概率应满足的关系：稳态概率应满足的关系：当当ns时，时，pn=/(n)pn-1当当ns时，时，Pn=/(s)pn-1 令令=/(s)系统负荷强度系数系统负荷强度系数3.2 多服务台无限源系统多服务台无限源系统012ns2cc-1ssc+13(s-1)ss 此此系系统统中中，当当=/(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）队长和队列长。）队长和队列长。例例 5 5 排队系统的优化目标排队系统的优化目标与最优化问题与最优化问题 从从经经济济角角度度考考虑虑，排排队队系系统统的的费费用用应应该该包包含含以以下下两两个个方方面面：一一个个是是服服务务费费用用，它它是是服服务务水水平平的的递递增增函函数数；另另一一个个是是顾顾客客等等待待的的机机会会损损失失(费费用用)，它它是是服服务务水水平平的的递递减减函函数。两者的总和呈一条数。两者的总和呈一条U U形曲线。形曲线。排队系统优化问题排队系统优化问题 系系统统最最优优化化的的目目标标就就是是寻寻求求上上述述合成费用曲线的最小点。合成费用曲线的最小点。排排队队系系统统的的最最优优化化问问题题通通常常分分为为两两类类：系系统统的的静静态态最最优优设设计计，目目的的在在于于使使设设备备达达到到最最大大效效益益；系系统统动动态态最最优优运运营营，是是指指一一个个给给定定排排队队系系统统，如如何运营可使某个目标函数得到最优。何运营可使某个目标函数得到最优。排队系统常见的优化问题排队系统常见的优化问题1)1)确定最优服务率确定最优服务率*；2)2)确定最佳服务台数量确定最佳服务台数量s s*；3)3)选择最为合适的服务规则；选择最为合适的服务规则；4)4)或是确定上述几个量的最优组合。或是确定上述几个量的最优组合。研研究究排排队队系系统统的的根根本本目目的的在在于于以以最少的设备得到最大的效益。最少的设备得到最大的效益。本节讨论的排队系统优化问题本节讨论的排队系统优化问题 本本章章只只讨讨论论系系统统静静态态的的最最优优设设计计问问题题。这这类类问问题题一一般般可可以以借借助助于于前前面面所所得得到到的的一一些表达式来解决。些表达式来解决。本本节节就就 ，s s 这这两两个个决决策策变变量量的的分分别别单单独独优优化化，介介绍绍两两个个较较简简单单的的模型。模型。5.1 M/M/1/系统的最优平均服务系统的最优平均服务率率*设设：c1 当当 =1时时服服务务系系统统单单位位时时间间的的平均费平均费 cw 平平均均每每个个顾顾客客在在系系统统逗逗留留单单位位时间的损失；时间的损失；y 系统单位时间的平均总费用。系统单位时间的平均总费用。其中其中 c1，cw 均为可知。则目标函数为均为可知。则目标函数为求解过程求解过程将将L=(-)，代入上式，得，代入上式，得 y 是是关关于于决决策策变变量量 的的一一元元非非线线性性函函数数,由一阶条件由一阶条件解得驻点解得驻点求解过程（续）求解过程（续）根号前取正号是为了保证根号前取正号是为了保证 1 ，这这样样，系系统统才才能能达达到到稳稳态态。又又由由二阶条件二阶条件 ()可可知知求求出出的的*为为(,),)上上的的全全局局唯唯一一最最小小点。将点。将*代入代入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)，如如下下表所示。表所示。求解过程求解过程 续续S1234524.492.642.061.9521.850.580.11 由表所示，可知：由表所示，可知：S*4(人人)据此可得最小总平均费用：据此可得最小总平均费用：故故该该室室应应设设置置4名名接接待待员员可可使使每每天天总总平平均均费费用用达达到到最最小小，为为7326元。元。求解过程求解过程 续续作业 P235 2,3,4