第运筹学06章课件.ppt

1、1第六章第六章 排队论排队论本章内容重点本章内容重点 排队论的基本概念排队论的基本概念 研究的基本问题与排队问题求解研究的基本问题与排队问题求解思路思路 泊松输入泊松输入指数服务排队模型指数服务排队模型 其他模型选介其他模型选介 排队系统的优化目标与最优化问排队系统的优化目标与最优化问题题3 排队论排队论(Queuing Theory)(Queuing Theory)又称又称随机服务系统理论随机服务系统理论(Random Service(Random Service System Theory),System Theory),是一门研究拥挤现是一门研究拥挤现象象(排队、等待排队、等待)的科学。

2、具体地说，的科学。具体地说，它是在研究各种排队系统概率规律性它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优的基础上，解决相应排队系统的最优设计和最优控制问题。设计和最优控制问题。前前 言言4 排队论是排队论是19091909年由丹麦工程师爱年由丹麦工程师爱尔朗尔朗(A.K(A.KErlang)Erlang)在研究电话系统时在研究电话系统时创立的，几十年来排队论的应用领域创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别越来越广泛，理论也日渐完善。特别是自是自2020世纪世纪6060年代以来，由于计算机年代以来，由于计算机的飞速发展，更为排队论的应用开拓的飞速发展

3、，更为排队论的应用开拓了广阔的前景。了广阔的前景。前前 言言5第一节第一节 排队论的基本概念排队论的基本概念 排队是我们在日常生活和生产中经常排队是我们在日常生活和生产中经常遇到的现象遇到的现象:人多时排队乘车；人多时排队乘车；顾客到商店购买物品交款；顾客到商店购买物品交款；病人到医院看病；病人到医院看病；旅客到车站售票处购买车票；旅客到车站售票处购买车票；食堂就餐等。食堂就餐等。常常出现人们排队和等待现象。常常出现人们排队和等待现象。排队的不一定是人，也可以是物：排队的不一定是人，也可以是物：通信卫星与地面待传递的信息；通信卫星与地面待传递的信息；生产线上的原料、半成品等待加工；生产线上的原

4、料、半成品等待加工；因故障停止运转的机器等待工人修理；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘要降落的飞机因跑道不空而在空中盘旋等。旋等。7一、一、排队系统特征与基本过程排队系统特征与基本过程 1.排队问题的共同特征排队问题的共同特征 有要求某种服务的人或物。排队有要求某种服务的人或物。排队论里把要求服务的对象统称为论里把要求服务的对象统称为“顾客顾客”。有提供服务的人或机构。把提供有提供服务的人或机构。把提供服务。的人或机构称为服务。的人或机构称为“服务台服务台”或或“服务员服务员”。顾客的到达、服务的时间至少有顾客的

5、到达、服务的时间至少有一个是一个是随机随机的，服从某种分布。的，服从某种分布。8 2.基本排队过程基本排队过程 任何一个排队问题的基本排队任何一个排队问题的基本排队过程都可以用图过程都可以用图 6-16-1表示：每个顾表示：每个顾客由顾客源按照一定方式到达服务客由顾客源按照一定方式到达服务系统，首先加入队列排队等待接受系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务列中选择顾客进行服务，获得服务后的顾客立即离开。后的顾客立即离开。一般排队系统都可由一般排队系统都可由图图6-1描述描述图图6-1 6-1 随机服务系统随机服务

6、系统排队系统示意图排队系统示意图10 面对拥挤现象，顾客排队时间的长短面对拥挤现象，顾客排队时间的长短与服务设施规模的大小，就构成了设计与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这决顾客排队时间与服务设施费用大小这对矛盾，这就是排队论所要研究解决的对矛盾，这就是排队论所要研究解决的问题之一。问题之一。11 通常，排队系统都有通常，排队系统都有输入过程输入过程、服务规则服务规则和和服务台

7、服务台等等3 3个组成部分：个组成部分：1)1)输入过程。输入过程。这是指要求服务的这是指要求服务的顾客是按怎样的规律到达排队系统的过顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流。一般可以程，有时也把它称为顾客流。一般可以从从3 3个方面来描述一个输入过程。个方面来描述一个输入过程。二、二、排队系统的基本组成部分排队系统的基本组成部分121)1)输入过程输入过程 顾客总体数顾客总体数(又称又称顾客源顾客源、输入源输入源)。这是指顾客的来源。这是指顾客的来源。顾客源可以是有限的，也可以是顾客源可以是有限的，也可以是无限的。例如，到售票处购票的无限的。例如，到售票处购票的顾客总数可以

8、认为是无限的，而顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是某个工厂因故障待修的机床则是有限的。有限的。13 顾客到达方式顾客到达方式。描述顾客描述顾客是怎样来到系统的，他们是单个到达，是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如客单个到达的例子。在库存问题中如将生产器材进货或产品入库看做是顾将生产器材进货或产品入库看做是顾客，那么这种顾客则是成批到达的客，那么这种顾客则是成批到达的（下面只讨论单个情况）（下面只讨论单个情况）。1)1)输入过程输入过程141)1)输入过程输入过程 顾客流的概率分布

9、顾客流的概率分布，或称，或称相相继顾客到达的时间间隔的分布继顾客到达的时间间隔的分布。这这是求解排队系统有关运行指标问题时，是求解排队系统有关运行指标问题时，首先需要确定的指标。流可以理解为在首先需要确定的指标。流可以理解为在一定的时间间隔内到达一定的时间间隔内到达k个顾客个顾客(k=1，2，)的概率是多大。的概率是多大。顾客流的概率分布顾客流的概率分布一般有定长分布、二项分布、泊松流一般有定长分布、二项分布、泊松流(最简单流最简单流)、爱尔朗分布等若干种。、爱尔朗分布等若干种。15 这指服务台从队列中选取顾客这指服务台从队列中选取顾客进行服务的顺序。一般可以分为进行服务的顺序。一般可以分为损

10、损失制失制、等待制等待制和和混合制混合制等等3 3大类。大类。损失制损失制。如果顾客到达排队如果顾客到达排队系统时，所有服务台都已被占用，那系统时，所有服务台都已被占用，那么他们就自动离开系统永不再来。么他们就自动离开系统永不再来。2)服务规则服务规则 等待制等待制。当顾客来到系统时，所当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服有服务台都不空，顾客加入排队行列等待服务。等待制中，服务台在选择顾客进行服务务。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：时，常有如下四种规则：先到先服务。先到先服务。按顾客到达的先后顺序对顾按顾客到达的先后顺序对顾客进行服务，这是最普遍的

11、情形。客进行服务，这是最普遍的情形。后到先服务。后到先服务。仓库中叠放的钢材，后叠放仓库中叠放的钢材，后叠放上去的都先被领走，就属于这种情况。上去的都先被领走，就属于这种情况。2)服务规则服务规则17 随机服务随机服务。即当服务台空闲时，不按即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。务，如电话交换台接通呼叫电话就是一例。优先权服务优先权服务。如老人、儿童先进车站；如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理，危重病员先就诊；遇到重要数据需要处理，计算机立即中断其他数据的处理等，均属计算机立即

12、中断其他数据的处理等，均属于此种服务规则。于此种服务规则。2)服务规则服务规则(等待制等待制-续续)18 混合制。混合制。等待制与损失制相等待制与损失制相结合的一种服务规则，一般是指允许排结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体队，但又不允许队列无限长下去。具体说来，大致有三种：说来，大致有三种：队长有限队长有限。当排队系统中的顾客人数当排队系统中的顾客人数K超过规定数量时，后来的顾客就自动超过规定数量时，后来的顾客就自动离去，另求服务，即系统的容量是有限离去，另求服务，即系统的容量是有限的。的。2)服务规则服务规则19 等待时间有限等待时间有限。顾客在系统中的等待

13、顾客在系统中的等待时间不超过某一给定的长度时间不超过某一给定的长度T，当等待时，当等待时间超过间超过T 时，顾客将自动离去，并不再回时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。后不愿再等而自动离去另找饭店用餐。2)服务规则服务规则（混合制（混合制-续）续）逗留时间有限逗留时间有限。例如用高射炮射击敌机，例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为当敌

14、机飞越高射炮射击有效区域的时间为 t 时，若飞机在这个时间内未被击落，就不可时，若飞机在这个时间内未被击落，就不可能再被击落了。能再被击落了。注意注意：损失制和等待制可看成是混合损失制和等待制可看成是混合制的特殊情形，如记制的特殊情形，如记 s 为系统中服务台的个为系统中服务台的个数，则当数，则当 K=s 时，混合制即成为损失制；时，混合制即成为损失制；当当K=时，混合制即成为等待制。时，混合制即成为等待制。2)服务规则服务规则（混合制（混合制-续）续）服务台可从以下三方面来描述服务台可从以下三方面来描述：服务台数量及构成形式（图服务台数量及构成形式（图6-6-26-626-6）单队单队单服务

15、台式；单服务台式；单队单队多服务台并联式；多服务台并联式；多队多队多服务台并联式；多服务台并联式；单队单队多服务台串联式；多服务台串联式；单队单队多服务台并串联混合式；多多服务台并串联混合式；多队队多服务台并串联混合式，等等。多服务台并串联混合式，等等。3.服务台情况服务台情况 不同的顾客与服务台组成了各式各不同的顾客与服务台组成了各式各样的服务系统。顾客为了得到某种服务样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获允许排队等待，则加入等待队伍，待获得服务后离开系统，见图得服务后离开系统，见图6-26-2

16、至图至图6-66-6。图图6-2 6-2 单服务台排队系统单服务台排队系统图图6-3 6-3 单队列单队列-S-S个服务台并联的排队系统个服务台并联的排队系统图图6-4 S6-4 S个队列个队列-S-S个服务台的并联排队系统个服务台的并联排队系统图图6-5 6-5 单队单队-多个服务台的串联排队系统多个服务台的串联排队系统图图6-6 6-6 多队多队-多服务台混联、网络系统多服务台混联、网络系统25 服务方式服务方式。这是指在某一时这是指在某一时刻接受服务的顾客数，它有单个服务和成刻接受服务的顾客数，它有单个服务和成批服务两种（下面只讨论单个情况）。批服务两种（下面只讨论单个情况）。服务时间的

17、分布服务时间的分布。在多数情在多数情况下，对每一个顾客的服务时间是一随机况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分变量，其概率分布有定长分布、负指数分布、布、K级爱尔朗分布、一般分布级爱尔朗分布、一般分布(所有顾客所有顾客的服务时间都是独立同分布的的服务时间都是独立同分布的)等等。等等。3.服务台情况服务台情况26 为了区别各种排队系统，根据输为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化入过程、排队规则和服务机制的变化对 排 队 模 型 进 行 描 述 或 分 类，对 排 队 模 型 进 行 描 述 或 分 类，DGKendall提出了一种目前在排

18、提出了一种目前在排队论中被广泛采用的队论中被广泛采用的“Kendall记号记号”，完整的表达方式通常用到完整的表达方式通常用到6个符号并个符号并取如下固定格式：取如下固定格式：A/B/C/D/E/F 各符号的位置含义如下：各符号的位置含义如下：三、三、排队系统的描述符号与分类排队系统的描述符号与分类A 表示顾客相继到达间隔时间表示顾客相继到达间隔时间 分布，常用下列符号：分布，常用下列符号：M 表示到达过程为泊松过程或负指表示到达过程为泊松过程或负指 数分布；数分布；D 表示定长输入；表示定长输入；Ek 表示表示k阶爱尔朗分布；阶爱尔朗分布；G 表示一般相互独立的随机分布。表示一般相互独立的随

19、机分布。Kendall记号含义记号含义Kendall记号含义记号含义B 表示服务时间分布表示服务时间分布。所用符号所用符号 与表示顾客到达间隔时间分布相同。与表示顾客到达间隔时间分布相同。M 表示服务过程为泊松过程或负表示服务过程为泊松过程或负 指数分布；指数分布；D 表示定长分布；表示定长分布；Ek 表示表示k阶爱尔朗分布；阶爱尔朗分布；G 表示一般相互独立的随机分布。表示一般相互独立的随机分布。C 表示服务台表示服务台(员员)个数个数：“1”则表示单个服务台，则表示单个服务台，“s”(s1)表示多表示多个服务台。个服务台。D 表示系统中顾客容量限额表示系统中顾客容量限额：如系统有如系统有K

20、个位子，则个位子，则 s K0 和和 n0，n=1,2,N 当当 t(t 0)时刻，记状态随机变量时刻，记状态随机变量为为K(t)，系统内有，系统内有n个顾客的概率为个顾客的概率为Pn(t)，经过，经过t 时间，如果满足时间，如果满足59 则称这个随机过程则称这个随机过程 K(t)：t 0 为为有限状态有限状态S上的上的生灭过程生灭过程。当系统具有。当系统具有可列无限状态集可列无限状态集S=0,1,2,时时,则则称为无限状态的生灭过程。称为无限状态的生灭过程。生灭过程与状态转移速度图生灭过程与状态转移速度图1,1,),()()()()()(11nnnkSktottPtotttPtotttPkn

21、nnn 状态转移速度图。状态转移速度图。我们把充分我们把充分小的小的t 固定，直接用参数固定，直接用参数 n 和和 n 表示表示 n t 和和 n t，生灭过程可利用状态转移速度图来，生灭过程可利用状态转移速度图来描述描述“生生”、“灭灭”导致状态转移的过程。导致状态转移的过程。注意，实际上，注意，实际上，n和和 n的取值不需要考虑的取值不需要考虑t的大小，只要保证二者的基础时段一致即可的大小，只要保证二者的基础时段一致即可（计算中考虑的是二者的比率）。（计算中考虑的是二者的比率）。生灭过程与状态转移速度图生灭过程与状态转移速度图无限状态生灭过程的状态转移速度无限状态生灭过程的状态转移速度图如

22、下图图如下图：状态转移速度图状态转移速度图0n123021n-1n1n32n+1状态转移速度图状态转移速度图 根据泊松流的普通性，当根据泊松流的普通性，当t充分小充分小时，在时，在(t,t+t)时间段内有一个顾客到时间段内有一个顾客到达的概率为达的概率为 nt+o(t)，而无顾客，而无顾客到达的概率为到达的概率为1-nt+o(t)，故泊松，故泊松输入输入指数服务排队系统的状态转指数服务排队系统的状态转移过程是生灭过程。因此，可以通过移过程是生灭过程。因此，可以通过状态转移速度图研究状态概率之间的状态转移速度图研究状态概率之间的关系。关系。三、三、泊松输入泊松输入-指数服务排队系统的求指数服务排

23、队系统的求解解 1)状态概率之间的关系状态概率之间的关系:可以通过两种方式推导这种关系：可以通过两种方式推导这种关系：直接通过概率发生情况讨论系统直接通过概率发生情况讨论系统状态概率之间的关系。状态概率之间的关系。利用状态转移速度图导出各状态利用状态转移速度图导出各状态概率之间的关系。概率之间的关系。直接通过概率发生情况讨论系统状态直接通过概率发生情况讨论系统状态概率之间的关系：概率之间的关系：n：系统状态为系统状态为n时，顾客进入系统的平均速度时，顾客进入系统的平均速度 n：系统状态为系统状态为n时，顾客离开系统的平均速度时，顾客离开系统的平均速度 Pn(t)：t 时刻，系统内有时刻，系统内

24、有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互

25、不相容且完备互不相容且完备,于是于是67 当当n=0时，只有方式时，只有方式1和和3，4发生，且方式发生，且方式1中无离去的概率为中无离去的概率为1，则，则 dP0(t)/dt=-P0(t)0+P1(t)1 我们假设系统是稳态的，即我们假设系统是稳态的，即与时刻无关，于是可得与时刻无关，于是可得 d Pn(t)/d t =0；公式推导如下：公式推导如下：2323332221112122211100010111000)(0)(0pppppppppppppp 根据此根据此各事件两两不相容，且完各事件两两不相容，且完备，有备，有 pn=1，于是于是 可求出可求出 pn,n=0,1,2,0110111

26、1110)(ppppppinijnjnnnnnnnnnnn 利用状态转移速度图得到概率公式利用状态转移速度图得到概率公式由此图易得转入率由此图易得转入率=转出率转出率n=0，0P0=1P1n0，n-1Pn-1+n+1Pn+1=(n+n)Pn0n123021n-1n1n32n+171公式推导如下：公式推导如下：2323332221112122211100010111000)(0)(0pppppppppppppp 72 根据此根据此各事件两两不相容，且完各事件两两不相容，且完备，有备，有 pn=1，于是于是 可求出可求出 pn,n=0,1,2,01101111110)(ppppppinijnjnn

27、nnnnnnnnn 对排队系统运行情况的分析，对排队系统运行情况的分析，通常是在给定输入与服务条件下，通常是在给定输入与服务条件下，通过求解系统状态为通过求解系统状态为n的概率的概率Pn(t)，再计算其主要的运行指标，再计算其主要的运行指标:74泊松输入泊松输入-指数服务指数服务稳态稳态排队系排队系统统系统的运行指标系统的运行指标 系统中顾客数系统中顾客数(队长队长)的期望值的期望值 排队等待的顾客数排队等待的顾客数(排队长排队长)的期的期望值为望值为0nnnpL1)(snnqpsnL75 求出平均有效到达率求出平均有效到达率 e，再再利用利用Little公式计算：公式计算：顾客在系统中全部时

28、间顾客在系统中全部时间(逗留时间逗留时间)的期望值的期望值W；顾客在系统中排队等待顾客在系统中排队等待时间的期望值时间的期望值Wq。76 根据已知条件绘制状态转根据已知条件绘制状态转移速度图；移速度图；依据状态转移速度图写出依据状态转移速度图写出各稳态概率之间的关系；各稳态概率之间的关系；求出求出 P0 及及 Pn；2)泊松输入泊松输入负指数分布服务的排负指数分布服务的排队系统的一般决策过程：队系统的一般决策过程：772)泊松输入泊松输入负指数分布服务负指数分布服务的排队系统的一般决策过程（续）的排队系统的一般决策过程（续）计算各项数量运行指标；计算各项数量运行指标；用系统运行指标构造目标用系

29、统运行指标构造目标函数，对系统进行优化。函数，对系统进行优化。78 例例6-2 6-2 某汽车加油站有两台加油某汽车加油站有两台加油泵为汽车加油，加油站内最多能容纳泵为汽车加油，加油站内最多能容纳6辆汽车。已知顾客到达的时间间隔服辆汽车。已知顾客到达的时间间隔服从负指数分布，平均每小时到达从负指数分布，平均每小时到达18辆辆汽车。若汽车。若加油站中已有加油站中已有K辆车，当辆车，当K 2时，有时，有K/6的顾客将自动离去的顾客将自动离去。加油时。加油时间服从负指数分布，平均每辆车需要间服从负指数分布，平均每辆车需要5min。试求：。试求：非标准的非标准的M M/M M/2/2/N N模型模型7

30、9 1）系统空闲的概率）系统空闲的概率P0为多少？为多少？2）求系统满的概率）求系统满的概率P6是多少？是多少？3）求系统服务台不空的概率）求系统服务台不空的概率 P2+P3+P4+P5+P6=1-P0-P1 4）若服务一个顾客）若服务一个顾客,加油站可以加油站可以获得利润获得利润10元元,问平均每小时可获得问平均每小时可获得利润为多少元？利润为多少元？10 e 5）求每小时损失掉的顾客数？）求每小时损失掉的顾客数？损损=-e 80 6）加油站平均有多少辆车在）加油站平均有多少辆车在等待加油等待加油Lq？平均有多少个车位平均有多少个车位被占被占L？7）进入加油站的顾客需要等）进入加油站的顾客需

31、要等多长的时间才能开始加油多长的时间才能开始加油Wq？进进入加油站的顾客需要多长时间才能入加油站的顾客需要多长时间才能离去离去W？81稳态概率关系：稳态概率关系：P1=/P0=1.5P0=(3/2)P0P2=/(2 )P1=0.751.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)

32、/(2)P4=(1/4)(27/128)P0 =(27/512)P0P6=(1/6)/(2)P5=(1/8)(27/512)P0 =(27/4096)P083由由 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。841)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元元/h运行指标：运行指标：85

33、5)损损=-e=(18-14.5782)辆辆/h=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.477087)Wq=Lq/e=0.018h=1.08min W=Wq+1/=0.101h=6.08min运行指标（续）运行指标（续）86 例例6-3 车站候车室在某段时间车站候车室在某段时间旅客到达服从泊松分布，平均速度为旅客到达服从泊松分布，平均速度为50人人/h，每位旅客在候车室内停留的，每位旅客在候车室内停留的时间服从负指数分布，平均停留时间时间服从负指数分布，平均停留时间

34、为为0.5h，问候车室内平均人数为多少？，问候车室内平均人数为多少？解：把旅客停留在候车室看做服解：把旅客停留在候车室看做服务，于是系统为务，于是系统为M/M/=50 =1/0.5=287稳态概率关系：稳态概率关系：Pn=/(n )Pn-1=1/n!(/)nP0 记记=/=50/2=25 状态转移速度图状态转移速度图:0n12n-1n2(n+1)n+13(n-1)(n+2)88010100025!1e)!1(1ee!1,1nnnnnnnnnnnnnpLnpprrrrrrrr代入因此，候车室平均人数为因此，候车室平均人数为25人。人。在排队系统中，由于顾客到达在排队系统中，由于顾客到达分布和服务

35、时间分布不同、服务台分布和服务时间分布不同、服务台数不同、队长有限无限、顾客源有数不同、队长有限无限、顾客源有限无限等的不同组合，就会有不胜限无限等的不同组合，就会有不胜枚举的不同排队模型。枚举的不同排队模型。下面分析泊下面分析泊松输入松输入-指数服务排队系统模型。指数服务排队系统模型。第三节第三节 泊松输入泊松输入指数服务指数服务排队模型排队模型 90 1)M/M/1/:参数参数 ，稳态概率方程：稳态概率方程：Pn=(/)Pn-1=(/)nP0 令令=/当当 1时时,n不收敛，故应不收敛，故应1,n=0即即 k)=r r k+1顾客逗留时间超过顾客逗留时间超过t的概率的概率 P(U t)=e

36、-()t M/M/1/系统系统94 损损=-e=pN ,损失率损失率 损损/。设忙期、闲期和忙的概率、闲的概率分设忙期、闲期和忙的概率、闲的概率分别为别为 T忙忙、T闲闲、p忙忙、p闲闲，那么，那么可以证明可以证明 ，于是，于是 M/M/1/系统系统 其他指标其他指标r rr r11,1,0000ppppTTpppp忙忙闲闲忙忙闲闲忙忙闲闲又又 1忙忙Trr111忙闲TT95单服务台无限源系统单服务台无限源系统 2)M/M/1/N/参数参数、系统状态转移速度：系统状态转移速度：稳态概率方程：稳态概率方程：Pn=(/)Pn-1=(/)nP0 ,1n N0N-112N-2N96 由由M/M/1/N

37、/系统系统10 NnnpNnnp001 10011111NNnnNp97 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/系统系统1,21,1)1(1110r rr rr rr rr rr rNNnpLNNNnn98 3)损失制损失制M/M/1/1:顾客到达顾客到达若服务台被占用立即离开。直接可得：若服务台被占用立即离开。直接可得：P0=(1-)/(1-)2 =1/(1+)=/(+)P0+P1=1 P闲闲=P0=/(+

38、)P损损=P忙忙=P1=/(+)单服务台无限源系统单服务台无限源系统 1)M/M/c/系统系统 参数参数 、稳态概率应满足的关系：稳态概率应满足的关系：当当nc时，时，pn=/(n)pn-1 当当nc时，时，Pn=/(c)pn-1 令令=/(c)系统负荷强度系数系统负荷强度系数二、二、多服务台无限源系统多服务台无限源系统012nc2cc-1ccc+13(c-1)cc100 此系统中，当此系统中，当=/(c)1时，不时，不收敛，设收敛，设1,M/M/c/系统系统cnpccpcnpncpncpcnnnn,!1,!0101r rr r101 根据根据 ，可得到，可得到 Lq=ccc+1p0/c!(1

39、-)2利用利用 Little 公式得到公式得到 Wq=Lq/,W=Wq+1/,L=W=Lq+/M/M/c/系统系统10nnprrressnsnnssnsp,1!1100102 例例6-4 某火车站售票处有三个窗口，同某火车站售票处有三个窗口，同时售各车次的车票。顾客到达服从泊松分时售各车次的车票。顾客到达服从泊松分布，平均每分钟到达布，平均每分钟到达 =0.9人，服务时间服人，服务时间服从负指数分布，平均服务率每小时从负指数分布，平均服务率每小时 =24人，人，分两种情况讨论：分两种情况讨论：1.顾客排成一队，依次购票；顾客排成一队，依次购票；2.顾客在每个窗口排一队，不准串队。顾客在每个窗口

40、排一队，不准串队。求求:1）售票处空闲的概率。）售票处空闲的概率。2）平均等待时间和逗留时间。）平均等待时间和逗留时间。3）队长和队列长。）队长和队列长。单位一致单位一致：=0.4人人/min，=/(3)=0.75稳态概率：稳态概率：031232343 解：情况解：情况1.M/M/3/)3(5.4!33,53125.22,25.2003012001npppppppppnnnr rr r 104解：情况解：情况1.M/M/3/续续由由得得15.453125.225.2,130000nnnnppppr r1893.0,1683.0,0748.015.453125.225.21 21130pppr

41、rr r,)3(5.4)3(44044nnnnqnppnLr rr r105解：情况解：情况1.M/M/3/续续44)3(nnnSr rr rr rr rr rr rr r1)3(4434nnnndndSF,704.1)1(5.4,)1(12042r rr rr rr rpLddFSq记记 ,先求积分，再求微先求积分，再求微分分954.3,393.41,893.1WLWWLWqqq 106解：情况解：情况1.M/M/3/续续售票处的空闲的概率为售票处的空闲的概率为0.0748平均等待时间平均等待时间 Wq=1.893min，平均逗留时间平均逗留时间 W=4.393min队长队长 L=3.954

42、人人)Lq=1.704人人107参数参数 =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个系统并联个系统并联108故售票处空闲的概率为故售票处空闲的概率为 0.0156平均等待时间平均等待时间 Wq=7.5min 平均逗留时间平均逗留时间 W=10min队长队长 L=3 三个队三个队 共共3+3+3=9队列长

43、队列长 Lq=2.25 共共6.75人人 显然，排一队共享显然，排一队共享3个服务台效率高。个服务台效率高。解：情况解：情况2.M/M/1/续续1092)M/M/c/N/稳态概率应满足的关系：稳态概率应满足的关系：当当nc时，时，当当nc时，时，多服务台无限源系统多服务台无限源系统0N-112N-2c2cNcc-1ccc+1(c-1)cc111 nnnnnpnpp 111nnnnnpcpp 110令令=/(c)，根据，根据 pn=1，可得，可得M/M/c/N/系统系统Nncpccpcnpncpncpcnnnn,!1,!0101r rr r1,!)1(!1,1!11011100r rr rr r

44、r rr rr rsssNnsssnsPsnsnNssnnsn111运行指标：运行指标：M/M/c/N/系统系统1,!2)1)(1,)1)(1(1)1(!0021r rr rr rr rr rr rr rpcccNcNpcNccLccNccq112同单服务台情况的分析，同单服务台情况的分析，e=(1-pN)利用利用 Little 公式，可求得公式，可求得 Wq=Lq/e W=Wq+1/L=We=Lq+e/M/M/c/N/系统系统113此即此即M/M/c/N中中 N=c 的情形的情形 损损=-e=pc ，损失率，损失率=损损/=pc 3)M/M/c/c/损失制系统损失制系统 r rr r cpn

45、cppnnnnnn,!0110,0,)1(,!100qqcecnnnWLpncp r r)1(,1cpLW 114三、三、有限源排队系统有限源排队系统 1)M/M/1/m/m系统系统 顾客源是顾客源是m个，那么系统容量实质上最多有个，那么系统容量实质上最多有m个个足够。足够。0m-112m-2m(m-1)2m(m-2)3顾客源中剩余的顾客数顾客源中剩余的顾客数乘以每个顾客到达的概率乘以每个顾客到达的概率115M/M/1/m/m系统系统稳态概率方程：稳态概率方程：由概率性质，得由概率性质，得),2,1()()!(!)1(01mnpnmmpnmpnnnmnnnmmp010)!(!(r r)()()

46、(0000Lmnppmpnmpmnnmnnmnmnnnne M/M/1/m/m系统系统根据根据 e=(m-L)=e=(1-p0),得得 L=m-/(1-p0)再利用再利用Little公式，可求得公式，可求得 W=L/e Wq=W-1/Lq=Wq e1172)M/M/c/m/m系统系统0m-112m-2m(m-1)2c2cmcc-1(m(c-1)c稳态概率方程稳态概率方程)1,2,1(!)!(!)1(01cnpnnmmpnnmpnnnr),1,(!)!(!)1(01mccnpccnmmpcnmpncnnnr118代入代入 pn=1 得得同前，同前，M/M/c/m/m系统系统mcnncncnncc

47、nmmnnmmp1100!)!(!)!(!r rr r)()()(0000Lmnppmpnmpmnnmnnmnmnnnne 119进一步可得进一步可得 可求出可求出L和和 e，再利用，再利用Little公式，得公式，得 M/M/c/m/m系统系统msnnsnneepspn11 qeqqeWLWWLW ,1,120第四节第四节 其他模型选介其他模型选介一、一、M/G/1排队系统排队系统 设顾客平均到达率为设顾客平均到达率为，服务时间为随机变量，服务时间为随机变量V，且且E(V)=1/，D(V)=2 。那么，服务强那么，服务强度度 r r ，当，当 r r 1时，时，p0=1-r r 根据波拉切克

48、根据波拉切克-欣钦欣钦（Pollaczek-Khinchine）公式公式可导出可导出 其他量的计算同前。其他量的计算同前。)1(2222r r r r qL121其他模型选介其他模型选介二、二、M/D/1排队系统排队系统 设顾客平均到达率为设顾客平均到达率为，服务时间为常数，服务时间为常数v，则，则 E(v)=v=1/,D(v)=0那么，服务强度那么，服务强度 r r ，当，当 r r 1时时 p0=1-r r 根据上一模型的公式可直接根据上一模型的公式可直接得到得到 其他量的计算同前。其他量的计算同前。)1(22r rr r qL122第五节第五节 排队系统的优化目标排队系统的优化目标与最优

49、化问题与最优化问题 从经济角度考虑，排队系统的费从经济角度考虑，排队系统的费用应该包含以下两个方面：一个是服用应该包含以下两个方面：一个是服务费用，它是服务水平的递增函数；务费用，它是服务水平的递增函数；另一个是顾客等待的机会损失另一个是顾客等待的机会损失(费用费用)，它是服务水平的递减函数。两者的总它是服务水平的递减函数。两者的总和呈一条和呈一条U U形曲线。形曲线。123排队系统优化问题排队系统优化问题 系统最优化的目标就是寻求上述系统最优化的目标就是寻求上述合成费用曲线的最小点。合成费用曲线的最小点。排队系统的最优化问题通常分为排队系统的最优化问题通常分为两类：系统的静态最优设计，目的在

50、两类：系统的静态最优设计，目的在于使设备达到最大效益；系统动态最于使设备达到最大效益；系统动态最优运营，是指一个给定排队系统，如优运营，是指一个给定排队系统，如何运营可使某个目标函数得到最优。何运营可使某个目标函数得到最优。124排队系统常见的优化问题排队系统常见的优化问题 1)1)确定最优服务率确定最优服务率*；2)2)确定最佳服务台数量确定最佳服务台数量c c*；3)3)选择最为合适的服务规则；选择最为合适的服务规则；4)4)或是确定上述几个量的最优组合。或是确定上述几个量的最优组合。研究排队系统的根本目的在于以最研究排队系统的根本目的在于以最少的设备得到最大的效益。少的设备得到最大的效益