运筹学课件排队论

《运筹学课件排队论》由会员分享，可在线阅读，更多相关《运筹学课件排队论（81页珍藏版）》请在金锄头文库上搜索。

1、第十四章第十四章 排队论排队论Queuing TheoryQueuing Theory 基本概念基本概念（掌握）（掌握）输入过程和服务时间分布输入过程和服务时间分布（掌握）（掌握） 泊松到达、负指数服务排队模型泊松到达、负指数服务排队模型（掌握）（掌握） 其他模型其他模型（了解）（了解） 排队系统的优化目标与最优化问题排队系统的优化目标与最优化问题（了解）（了解） 本章内容重点本章内容重点 排排队队是是我我们们日日常常生生活活和和生生产产中中经经常常遇遇到到的的现现象象。例例如如，上上、下下班班搭搭乘乘公公共共汽汽车车；顾顾客客到到商商店店购购买买物物品品；病病员员到到医医院院看看病病；旅旅客

2、客到到售售票票处处购购买买车车票票；学学生生去去食食堂堂就就餐餐等等就就常常常常出出现现排排队队和和等等待待现现象象。除除了了上上述述有有形形的的排排队队之之外外，还还有有大大量量的的所所谓谓“无无形形”排排队队现现象象，如如几几个个顾顾客客打打电电话话到到出出租租汽汽车车站站要要求求派派车车，如如果果出出租租汽汽车车站站无无足足够够车车辆辆、则则部部分分顾顾客客只只得得在在各各自自的的要要车车处处等等待待，他他们们分分散散在在不不同同地地方方，却却形形成成了了一一个个无无形形队队列列在在等等待待派派车车。排排队队的的不不一一定定是是人人，也也可可以是物：以是物：前前 言言 例例如如，通通讯讯

3、卫卫星星与与地地面面若若干干待待传传递递的的信信息息；生生产产线线上上的的原原料料、半半成成品品等等待待加加工工；因因故故障障停停止止运运转转的的机机器器等等待待工工人人修修理理；码码头头的的船船只只等等待待装装卸卸货货物物；要要降降落落的的飞飞机因跑道不空而在空中盘旋等等。机因跑道不空而在空中盘旋等等。前前 言言 面面对对拥拥挤挤现现象象，人人们们总总是是希希望望尽尽量量设设法法减减少少排排队队，通通常常的的做做法法是是增增加加服服务务设设施施。但但是是增增加加的的数数量量越越多多，人人力力、物物力力的的支支出出就就越越大大，甚甚至至会会出出现现空空闲闲浪浪费费，如如果果服服务务设设施施太太

4、少少，顾顾客客排排队队等等待待的的时时间间就就会会很很长长，这这样样对对顾顾客会带来不良影响。客会带来不良影响。前前 言言 于于是是，顾顾客客排排队队时时间间的的长长短短与与服服务务设设施施规规模模的的大大小小，就就构构成成了了随随机机服服务务系系统统中中的的一一对对矛矛盾盾。如如何何做做到到既既保保证证一一定定的的服服务务质质量量指指标标，又又使使服服务务设设施施费费用用经经济济合合理理，恰恰当当地地解解决决顾顾客客排排队队时时间间与与服服务务设设施施费费用用大大小小这这对对矛矛盾盾，这这就就是是随随机机服服务务系系统统理理论论排排队队论论所所要要研研究究解解决决的问题。的问题。 排排队队论

5、论是是19091909年年由由丹丹麦麦工工程程师师爱爱尔尔朗朗(A.K(A.KErlang)Erlang)在在研研究究电电活活系系统统时时创创立立的的，几几十十年年来来排排队队论论的的应应用用领领域域越越来来越越广广泛泛，理理论论也也日日渐渐完完善善。特特别别是是自自二二十十世世纪纪6060年年代代以以来来，由由于于计计算算机机的的飞飞速速发发展展，更更为为排排队队论的应用开拓了宽阔的前景。论的应用开拓了宽阔的前景。前前 言言 排排队队论论(Queuing (Queuing Theory)Theory)，又又称称 随随 机机 服服 务务 系系 统统 理理 论论 (Random (Random

6、Service Service System System Theory),Theory),是是一一门门研研究究拥拥挤挤现现象象( (排排队队、等等待待) )的的科科学学。具具体体地地说说，它它是是在在研研究究各各种种排排队队系系统统概概率率规规律律性性的的基基础础上上，解解决决相相应应排排队队系系统统的的最最优优设设计计和和最最优优控控制制问问题。题。前前 言言 显显然然，上上述述各各种种问问题题虽虽互互不不相相同同，但但却却都都有有要要求求得得到到某某种种服服务务的的人人或或物物和和提提供供服服务务的的人人或或机机构构。排排队队论论里里把把要要求求服服务务的的对对象象统统称称为为“顾顾客客

7、”,”,而而把把提提供供服服务务的的人人或或机机构构称称为为“服服务务台台”或或“服服务务员员”。不不同同的的顾顾客客与与服服务务组组成成了了各各式式各样的服务系统。各样的服务系统。前前 言言图图1 1 单服务台排队系统单服务台排队系统 前前 言言n顾客为了得到某种服务而到达系统、若不顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见入等待队伍，待获得服务后离开系统，见图图1至图至图5。图图2 2 单队列单队列SS个服务台并联的排队系统个服务台并联的排队系统图图3 S3 S个队列个队列SS个服务台的并

8、联排队系统个服务台的并联排队系统前前 言言图图4 4 单队单队多个服务台的串联排队系统多个服务台的串联排队系统图图5 5 多队多队多服务台混联、网络系统多服务台混联、网络系统前前 言言图图6-6 6-6 随机服务系统随机服务系统前前 言言一一般般的的排排队队系系统统，都都可可由由下下面图面图6 6加以描述。加以描述。 通通常常称称由由图图6 6表表示示的的系系统统为为一一随随机机聚聚散散服服务务系系统统，任任一一排排队队系系统统都都是是一一个个随随机机聚聚散散服服务务系系统统。这这里里，“聚聚”表表示示顾顾客客的的到到达达，“散散”表表示示顾顾客客的的离离去去。所所谓谓随随机机性性则则是是排排

9、队队系系统统的的一一个个普普遍遍特特点点，是是指指顾顾客客的的到到达达情情况况( (如如相相继继到到达达时时间间间间隔隔) )与与每每个个顾顾客客接接受受服服务务的的时时间间往往往往是是事事先先无无法法确确切切知知道道的的，或或者者说说是随机的）。是随机的）。 一一般般来来说说，排排队队论论所所研研究究的的排排队队系系统统中中，顾顾客客到到来来的的时时刻刻和和服服务务台台提提供供服服务务的的时时间间长长短短都都是是随随机机的的，因因此此这这样样的的服服务务系系统统被被称称为为随机服务系统。随机服务系统。前前 言言1.1.基基 本本 概概 念念 一一 排队系统的描述排队系统的描述 （一）系统特征

10、和基本排队过程（一）系统特征和基本排队过程 实际的排队系统虽然千差万别，但是它们实际的排队系统虽然千差万别，但是它们 有以下的共同特征：有以下的共同特征： (1) (1)有请求服务的人或物有请求服务的人或物顾客顾客； (2) (2)有为顾客服务的人或物，即服务员或有为顾客服务的人或物，即服务员或服务台服务台； (3)(3)顾客到达系统的时刻是随机的，为顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，每一位顾客提供服务的时间是随机的，因而整个因而整个排队系统的状态也是随机的排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段排队系统的这种随机性造成某个阶段顾客排队较长，而另

11、外一些时候服务顾客排队较长，而另外一些时候服务员员( (台台) )又空闲无事。又空闲无事。 任任何何一一个个排排队队问问题题的的基基本本排排队队过过程程都都可可以以用用图图6 6表表示示。从从图图6 6可可知知，每每个个顾顾客客由由顾顾客客源源按按一一定定方方式式到到达达服服务务系系统统，首首先先加加入入队队列列排排队队等等待待接接受受服服务务，然然后后服服务务台台按按一一定定规规则则从从队队列列中中选选择择顾顾客客进进行行服服务务，获获得得服务的顾客立即离开。服务的顾客立即离开。1.1.基基 本本 概概 念念 （二）排队系统的基本组成部分（二）排队系统的基本组成部分 通通常常，排排队队系系统

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

13、而而某某个个工工厂厂因因故故障待修的机床则是有限的。障待修的机床则是有限的。1.1.基基 本本 概概 念念 (2)(2)顾顾客客到到达达方方式式。这这是是描描述述顾顾客客是是怎怎样样来来到到系系统统的的，他他们们是是单单个个到到达达，还还是是成成批批到到达达。病病人人到到医医院院看看病病是是顾顾客客单单个个到到达达的的例例子子。在在库库存存问问题题中中如如将将生生产产器器材材进进货货或或产产品品入入库库看看作作是是顾顾客客，那么这种顾客则是成批到达的。那么这种顾客则是成批到达的。 1.1.基基 本本 概概 念念(3)(3)顾顾客客流流的的概概率率分分布布，或或称称相相继继顾顾客客到到达达的的时

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

15、制和混合制等损失制、等待制和混合制等3 3大类。大类。 (1)(1)损损失失制制。这这是是指指如如果果顾顾客客到到达达排排队队系系统统时时，所所有有服服务务台台都都已已被被先先来来的的顾顾客客占占用用，那那么么他他们们就就自自动动离离开开系系统统永永不不再再来来。典典型型例例子子是是，如如电电话话拔拔号号后后出出现现忙忙音音，顾顾客客不不愿愿等等待待而而自自动动挂挂断断电电话话，如如要要再再打打，就需重新拔号，这种服务规则即为损失制。就需重新拔号，这种服务规则即为损失制。1.1.基基 本本 概概 念念 (2)(2)等等待待制制。这这是是指指当当顾顾客客来来到到系系统统时时，所所有有服服务务台台

16、都都不不空空，顾顾客客加加入入排排队队行行列列等等待待服服务务。例例如如，排排队队等等待待售售票票，故故障障设设备备等等待待维维修修等等。等等待待制制中中，服服务务台台在在选选择择顾顾客客进进行行服服务务时时，常有如下四种规则：常有如下四种规则： 先先到到先先服服务务。按按顾顾客客到到达达的的先先后后顺顺序序对对顾顾客客进进行行服服务务，这这是是最最普普遍遍的情形。的情形。 后后到到先先服服务务。仓仓库库中中迭迭放放的的钢钢材材，后后迭迭放放上上去去的的都都先先被被领领走走，就就属属于这种情况。于这种情况。1.1.基基 本本 概概 念念 随随机机服服务务。即即当当服服务务台台空空闲闲时时，不不

17、按按照照排排队队序序列列而而随随意意指指定定某某个个顾顾客客去去接接受受服服务务，如如电电话话交交换换台台接接通通呼呼叫叫电电话话就是一例。就是一例。 优优先先权权服服务务。如如老老人人、儿儿童童先先进进车车站站；危危重重病病员员先先就就诊诊；遇遇到到重重要要数数据据需需要要处处理理计计算算机机立立即即中中断断其其他他数数据据的的处处理等，均属于此种服务规则。理等，均属于此种服务规则。1.1.基基 本本 概概 念念 (3)(3)混混合合制制这这是是等等待待制制与与损损失失制制相相结结合合的的一一种种服服务务规规则则，一一般般是是指指允允许许排排队队，但但又又不不允允许许队队列列无无限限长长下下

18、去去。具具体体说说来来，大致有三种：大致有三种： 队队长长有有限限。当当排排队队等等待待服服务务的的顾顾客客人人数数超超过过规规定定数数量量时时，后后来来的的顾顾客客就就自自动动离离去去，另另求求服服务务，即即系系统统的的等等待待空空间间是是有有限限的的。例例如如最最多多只只能能容容纳纳K K个个顾顾客客在在系系统统中中，当当新新顾顾客客到到达达时时，若若系系统统中中的的顾顾客客数数( (又又称称为为队队长长) )小小于于K K，则则可可进进入入系系统统排排队队或或接接受受服服务务；否否则则，便便离离开开系系统统，并并不不再再回回来来。如如水水库库的的库库容容是是有有限限的的，旅旅馆的床位是有

19、限的。馆的床位是有限的。1.1.基基 本本 概概 念念 等等待待时时间间有有限限。即即顾顾客客在在系系统统中中的的等等待待时时间间不不超超过过某某一一给给定定的的长长度度T T，当当等等待待时时间间超超过过T T时时，顾顾客客将将自自动动离离去去，并并不不再再回回来来。如如易易损损坏坏的的电电子子元元器器件件的的库库存存问问题题，超超过过一一定定存存储储时时间间的的元元器器件件被被自自动动认认为为失失效效。又又如如顾顾客客到到饭饭馆馆就就餐餐，等等了了一一定定时时间间后后不不愿愿再再等而自动离去另找饭店用餐。等而自动离去另找饭店用餐。1.1.基基 本本 概概 念念 逗逗留留时时间间( (等等待

20、待时时间间与与服服务务时时间间之之和和) )有有限限。例例如如用用高高射射炮炮射射击击敌敌机机，当当敌敌机机飞飞越越高高射射炮炮射射击击有有效效区区域域的的时时间间为为t t时时，若若在在这这个个时时间间内内未未被被击击落落，也也就就不不可可能能再再被击落了。被击落了。 不难注意到，不难注意到，损失制和等待制可看成损失制和等待制可看成是混合制的特殊情形，如记是混合制的特殊情形，如记s s为系统中服为系统中服务台的个数，则当务台的个数，则当K K= =s s时，混合制即成为时，混合制即成为损失制；当损失制；当K K=时，混合制即成为等待制。时，混合制即成为等待制。1.1.基基 本本 概概 念念

21、3 3服服务务台台情情况况。服服务务台台可可以以从从以以下下3 3方面来描述：方面来描述： (1) (1) 服务台数量及构成形式服务台数量及构成形式。从数量上。从数量上说，服务台有单服务台和多服务台之分。说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：从构成形式上看，服务台有： 单队单队单服务台式；单服务台式； 单队单队多服务台并联式；多服务台并联式； 多队多队多服务台并联式；多服务台并联式； 单队单队多服务台串联式；多服务台串联式； 单队单队多服务台并串联混合式多服务台并串联混合式, ,以及以及 多队多队多服务台并串联混合式等等。多服务台并串联混合式等等。见前面图见前面图1 1

22、至图至图5 5所示。所示。 1.1.基基 本本 概概 念念 (2) (2) 服服务务方方式式。这这是是指指在在某某一一时时刻刻接接受受服服务务的的顾顾客客数数，它它有有单单个个服服务务和和成成批批服服务务两两种种。如如公公共共汽汽车车一一次次就就可可装载一批乘客就属于成批服务。装载一批乘客就属于成批服务。 (3) (3) 服服务务时时间间的的分分布布。一一般般来来说说，在在多多数数情情况况下下，对对每每一一个个顾顾客客的的服服务务时时间间是是一一随随机机变变量量，其其概概率率分分布布有有定定长长分分布布、负负指指数数分分布布、K K级级爱爱尔尔良良分分布布、一一般般分分布布( (所所有有顾顾客

23、客的的服服务务时时间间都都是是独独立同分布的立同分布的) )等等。等等。1.1.基基 本本 概概 念念（三）排队系统的描述符号与分类（三）排队系统的描述符号与分类 为为了了区区别别各各种种排排队队系系统统，根根据据输输入入过过程程、排排队队规规则则和和服服务务机机制制的的变变化化对对排排队队模模型型进进行行描描述述或或分分类类，可可给给出出很很多多排排队队模模型型。为为了了方方便便对对众众多多模模型型的的描描述述，肯肯道道尔尔（D DG GKendallKendall）提提出出了了一一种种目目 前前 在在 排排 队队 论论 中中 被被 广广 泛泛 采采 用用 的的“Kendall“Kendal

24、l记记号号”，完完整整的的表表达达方方式式通通常用到常用到6 6个符号并取如下固定格式：个符号并取如下固定格式：A A/B/C/D/E/F/B/C/D/E/F 各符号的意义为：各符号的意义为：1.1.基基 本本 概概 念念A A表表示示顾顾客客相相继继到到达达间间隔隔时时间间分分布布，常常用下列符号：用下列符号：M M表示到达过程为泊松过程或负指数分布；表示到达过程为泊松过程或负指数分布；D D表示定长输入；表示定长输入；E Ek k表示表示k k阶爱尔朗分布；阶爱尔朗分布；G G表示一般相互独立的随机分布。表示一般相互独立的随机分布。B B表表示示服服务务时时间间分分布布，所所用用符符号号与

25、与表表示示顾客到达间隔时间分布相同。顾客到达间隔时间分布相同。M M表示服务过程为泊松过程或负指数分布；表示服务过程为泊松过程或负指数分布；D D表示定长分布；表示定长分布；E Ek k 表示表示k k阶爱尔朗分布；阶爱尔朗分布；G G表示一般相互独立的随机分布。表示一般相互独立的随机分布。1.1.基基 本本 概概 念念C C表表示示服服务务台台( (员员) )个个数数：“1”“1”则则表表示示单单个个服服务务台台，“s s”。( (s s1)1)表表示示多个服务台。多个服务台。D D表表示示系系统统中中顾顾客客容容量量限限额额，或或称称等等待待空空间间容容量量；如如系系统统有有K K个个等等

26、待待位位子子，则则 00K K，当当 K K=0 =0 时时，说说明明系系统统不不允允许许等等待待，即即为为损损失失制制。K K= = 时时为为等等待待制制系系统统，此此时时般般省省略略不不写写。K K为为有有限限整整数数时时，表示为混合制系统。表示为混合制系统。E E表表示示顾顾客客源源限限额额，分分有有限限与与无无限限两两种种，表表示示顾顾客客源源无无限限，此此时时一一般般也也可可省省略略不写。不写。1.1.基基 本本 概概 念念 F F表示服务规则，常用下列符号表示服务规则，常用下列符号： FCFS FCFS：表示先到先服务的排队规则；：表示先到先服务的排队规则； LCFS LCFS：表

27、示后到先服务的排队规则；：表示后到先服务的排队规则； PR PR：表示优先权服务的排队规则。：表示优先权服务的排队规则。 例例如如：某某排排队队问问题题为为M MM MS SFCFSFCFS，则则表表示示顾顾客客到到达达间间隔隔时时间间为为负负指指数数分分布布( (泊泊松松流流) )；服服务务时时间间为为负负指指数数分分布布；有有s s( (s s1)1)个个服服务务台台；系系统统等等待待空空间间容容量量无无限限( (等等待待制制) )；顾顾客客源源无无限限，采采用用先先到到先先服服务规则。务规则。 某某些些情情况况下下，排排队队问问题题仅仅用用上上述述表表达达形形式式中中的的前前3 3个个、

28、4 4个个、5 5个个符符号号。如如不不特特别别说说明明则则均均理理解解为为系系统统等等待待空空间间容容量量无无限限；顾顾客客源源无无限限，先先到到先先服务，单个服务的等待制系统。服务，单个服务的等待制系统。1.1.基基 本本 概概 念念 二、排队系统的主要数量指标二、排队系统的主要数量指标 研研究究排排队队系系统统的的目目的的是是通通过过了了解解系系统统运运行行的的状状况况，对对系系统统进进行行调调整整和和控控制制，使使系系统统处处于于最最优优运运行行状状态态。因因此此，首首先先需需要要弄弄清清系系统统的的运运行行状状况况。描描述述一一个个排排队队系系统统运运行行状状况况的的主主要要数数量量

29、指指标标有：有： 1.1.基基 本本 概概 念念 1.1.队长和排队长（队列长）队长和排队长（队列长） 队队长长是是指指系系统统中中的的平平均均顾顾客客数数( (排排队队等等待待的的顾顾客客数数与与正正在在接接受受服服务务的的顾顾客客数数之之和和) )， 排排队队长长是是指指系系统统中中正正在在排排队队等等待待服服务务的的平均顾客数。平均顾客数。 队队长长和和排排队队长长一一般般都都是是随随机机变变量量。我我们们希希望望能能确确定定它它们们的的分分布布，或或至至少少能能确确定定它它们们的的平平均均值值( (即即平平均均队队长长和和平平均均排排队队长长) )及及有有关关的的矩矩( (如如方方差差

30、等等) )。队队长长的的分分布布是是顾顾客客和和服服务务员员都都关关心心的的，特特别别是是对对系系统统设设计计人人员员来来说说，如如果果能能知知道道队队长长的的分分布布，就就能能确确定定队队长长超超过过某某个个数数的的概概率率，从而确定合理的等待空间。从而确定合理的等待空间。1.1.基基 本本 概概 念念 2 2等待时间和逗留时间等待时间和逗留时间从从顾顾客客到到达达时时刻刻起起到到他他开开始始接接受受服服务务止止这这段段时时间间称称为为等等待待时时间间，是是随随机机变变量量，也也是是顾顾客客最最关关心心的的指指标标，因因为为顾顾客客通通常常希希望望等等待待时间越短越好。时间越短越好。从从顾顾

31、客客到到达达时时刻刻起起到到他他接接受受服服务务完完成成止止这这段段时时间间称称为为逗逗留留时时间间，也也是是随随机机变变量量，同同样样为为顾顾客客非非常常关关心心。对对这这两两个个指指标标的的研研究究当当然然是是希希望望能能确确定定它它们们的的分分布布，或或至至少少能能知知道顾客的平均等待时间和平均逗留时间。道顾客的平均等待时间和平均逗留时间。1.1.基基 本本 概概 念念 3 3忙期和闲期忙期和闲期 忙忙期期是是指指从从顾顾客客到到达达空空闲闲着着的的服服务务机机构构起起，到到服服务务机机构构再再次次成成为为空空闲闲止止的的这这段段时时间间，即即服服务务机机构构连连续续忙忙的的时时间间。这

32、这是是个个随随机机变变量量，是是服服务务员员最最为为关关心心的的指指标标，因因为为它它关关系系到到服服务务员员的的服服务务强强度度。与与忙忙期期相相对对的的是是闲闲期期，即即服服务务机机构构连连续续保保持持空空闲闲的的时时间间。在在排排队队系系统统中中，忙忙期期和闲期总是交替出现的。和闲期总是交替出现的。 1.1.基基 本本 概概 念念 除除了了上上述述几几个个基基本本数数量量指指标标外外，还还会会用用到到其其他他一一些些重重要要的的指指标标，如如在在损损失失制制或或系系统统容容量量有有限限的的情情况况下下，由由于于顾顾客客被被拒拒绝绝，而而使使服服务务系系统统受受到到损损失失的的顾顾客客损损

33、失失率率及及服服务务强强度度等等，也也都都是十分重要的数量指标。是十分重要的数量指标。 4.4.一些数量指标的常用记号一些数量指标的常用记号 (1)(1)主要数量指标主要数量指标n N N( (t t) )：时时刻刻t t系系统统中中的的顾顾客客数数( (又又称称为系统的状态为系统的状态) )，即队长；，即队长；n N Nq q( (t t) )：时时刻刻t t系系统统中中排排队队的的顾顾客客数数，即排队长；即排队长；n T T( (t t) )：时时刻刻t t到到达达系系统统的的顾顾客客在在系系统中的逗留时间；统中的逗留时间；n T Tq q( (t t) )：时时刻刻t t到到达达系系统统

34、的的顾顾客客在在系系统中的等待时间。统中的等待时间。1.1.基基 本本 概概 念念 上上面面给给出出的的这这些些数数量量指指标标一一般般都都是是和和系系统统运运行行的的时时间间有有关关的的随随机机变变量量，求求这这些些随随机机变变量量的的瞬瞬时时分分布布一一般般是是很很困困难难的的。为为了了分分析析上上的的简简便便，并并注注意意到到相相当当一一部部分分排排队队系系统统在在运运行行了了一一定定时时间间后后，都都会会趋趋于于一一个个平平衡衡状状态态( (或或称称平平稳稳状状态态) )。在在平平衡衡状状态态下下，队队长长的的分分布布、等等待待时时间间的的分分布布和和忙忙期期的的分分布布都都和和系系统

35、统所所处处的的时时刻刻无无关关，而而且且系系统统的的初初始始状状态态的的影影响响也也会会消消失失。因因此此，我我们们在在本本章章中中将将主主要要讨讨论论与与系系统统所所处处时时刻刻无无关关的的性性质质，即即统统计计平衡性质。平衡性质。1.1.基基 本本 概概 念念nL L或或L Ls s 平平均均队队长长，即即稳稳态态系系统统任任一一时时刻刻的所有顾客数的期望值；的所有顾客数的期望值；nL Lq q 平平均均等等待待队队长长或或队队列列长长，即即稳稳态态系系统任一时刻的等待服务的顾客数的期望值；统任一时刻的等待服务的顾客数的期望值；nW W或或W Ws s 平平均均逗逗留留时时间间，即即( (

36、在在任任意意时时刻刻) )进入稳态系统的顾客逗留时间的期望值；进入稳态系统的顾客逗留时间的期望值；nW Wq q 平平均均等等待待时时间间，即即( (在在任任意意时时刻刻) )进进入稳态系统的顾客等待时间的期望值。入稳态系统的顾客等待时间的期望值。n这这四四项项主主要要性性能能指指标标( (又又称称主主要要工工作作指指标标) )的的值值越越小小，说说明明系系统统排排队队越越少少，等等待待时时间间越越少少，因因而而系系统统性性能能越越好好。显显然然，它它们们是是顾客与服务系统的管理者都很关注的。顾客与服务系统的管理者都很关注的。1.1.基基 本本 概概 念念 A AB BC CD DE E 其中

37、其中AA顾客到达的概率分布，可取顾客到达的概率分布，可取M M、D D、G G 、E Ek k 等；等；BB服务时间的概率分布，可取服务时间的概率分布，可取M M、D D、G G 、E Ek k 等；等；CC服务台个数，取正整数；服务台个数，取正整数；DD排队系统的最大容量，可取正整数或排队系统的最大容量，可取正整数或 ；EE顾客源的最大容量，可取正整数或顾客源的最大容量，可取正整数或 。例如例如 M M / / M M / 1 / / 1 / / / 表表示示顾顾客客到到达达过过程程服服从从泊泊松松分分布布，服服务务时时间间服服从从负负指指数数分分布布，一一个个服服务务台台，排排队队的的长长

38、度度无无限限制和顾客的来源无限制。制和顾客的来源无限制。22单服务台泊松到达、负指数服务时间的排队模型单服务台泊松到达、负指数服务时间的排队模型M M / / M M / 1 / / / 1 / / 设单位时间顾客平均到达数为设单位时间顾客平均到达数为 ，单位时间平均单位时间平均服务的顾客数为服务的顾客数为 ( ( c 时。时。例例 在前例的储蓄所里多设一个服务窗口，即储在前例的储蓄所里多设一个服务窗口，即储蓄所开设两个服务窗口。顾客的到达过程仍服蓄所开设两个服务窗口。顾客的到达过程仍服从泊松分布，平均每小时到达顾客仍是从泊松分布，平均每小时到达顾客仍是 36 人；人；储蓄所的服务时间仍服从负

39、指数分布，平均每储蓄所的服务时间仍服从负指数分布，平均每小时仍能处理小时仍能处理 48 位顾客的业务，其排队规则为位顾客的业务，其排队规则为只排一个队只排一个队，先到先服务。试求这个排队系统，先到先服务。试求这个排队系统的数量指标。的数量指标。解：解： c = 2， 平均到达率平均到达率 = 36/60 = 0.6， 平均服务率平均服务率 = 48/60 = 0.8。P0=0.4545,Lq = 0.1227 (个个顾客顾客),Ls = Lq + / = 0.8727 (个个顾客顾客),Wq = Lq / = 0.2045（分钟）（分钟）,Ws = Wq+ 1/ = 1.4545 （分钟）（分

40、钟）,Pw = 0.2045,P1 = 0.3409, P2 = 0.1278, P3 = 0.0479, P4 = 0.0180, P5 = 0.0067， P6 = 0.0040。在储蓄所里使用在储蓄所里使用 M / M / 2 模型与使用两个模型与使用两个 M / M / 1 模型，它们的服务台数都是模型，它们的服务台数都是 2，服务率，服务率和顾客到达率都一样，只是在和顾客到达率都一样，只是在 M / M / 2 中只排中只排一队，在一队，在 2 个个 M / M / 1 中排两队，结果却不一样。中排两队，结果却不一样。 M / M / 2 使得服务水平有了很大提高。如果把使得服务水平

41、有了很大提高。如果把 M / M / 2 与原来的一个与原来的一个 M / M / 1比较，那么服务水比较，那么服务水平之间的差别就更大了。平之间的差别就更大了。值得值得注意注意，在任何排队模型中，在任何排队模型中 Ls ， Lq， Ws，Wq 之间都有如下关系：之间都有如下关系：LsLq / ， WqLq / ， Ws = Wq+ 1/ 。 4 排队系统的经济分析排队系统的经济分析我们把一个排队系统的单位时间的总费用我们把一个排队系统的单位时间的总费用 TC 定义为服务机构的单位时间的费用和顾客在排队系定义为服务机构的单位时间的费用和顾客在排队系统中逗留单位时间的费用之和。即统中逗留单位时间

42、的费用之和。即TC = cw Ls + cs c其中其中 cw 为一个顾客在排队系统中逗留单位时间付为一个顾客在排队系统中逗留单位时间付出的费用；出的费用；Ls 为在排队系统中的平均顾客数；为在排队系统中的平均顾客数；cs 为为每个服务台单位时间的费用；每个服务台单位时间的费用；c 为服务台的数目。为服务台的数目。例例 在前两例中，设储蓄所的每个服务台的费用在前两例中，设储蓄所的每个服务台的费用cs = 18，顾客在储蓄所中逗留一小时的成本，顾客在储蓄所中逗留一小时的成本 cw =10。这。这样，样，对储蓄所对储蓄所 M / M / 1 模型可知模型可知 Ls = 3， c = 1，得，得TC

43、 = cw Ls + cs c = 48 元元 / 每小时。每小时。对储蓄所对储蓄所 M / M / 2 模型可知模型可知 Ls = 0.8727， c = 2，得得 TC = cw Ls + cs c = 44.73 元元 / 每小时。每小时。通过经济分析可知通过经济分析可知 M / M / 2 系统是一个更为经济的系统是一个更为经济的模型。模型。5 5 单服务台泊松到达、任意服务时间的单服务台泊松到达、任意服务时间的排队模型排队模型M / G / 1 / / 单位时间顾客平均到达数单位时间顾客平均到达数 ，单位平均服务顾单位平均服务顾客数客数 ，一个顾客的平均服务时间一个顾客的平均服务时间

44、 1 / ，服务服务时间的均方差时间的均方差 。数量指标公式数量指标公式:1、系统中无顾客的概率、系统中无顾客的概率 P0=1 / 2、平均排队的顾客数、平均排队的顾客数 3、系统中的平均顾客数、系统中的平均顾客数 Ls = Lq + / 4、顾客花在排队上的平均等待时间、顾客花在排队上的平均等待时间 Wq = Lq / 5、系统在中顾客的平均逗留时间、系统在中顾客的平均逗留时间 Ws = Wq+ 1/ 6、系统中顾客必须排队等待的概率、系统中顾客必须排队等待的概率 Pw = / 7、系统中恰好有、系统中恰好有 n 个顾客的概率个顾客的概率 Pn例例1. 某杂货店只有一名售货员，已知顾客的到某

45、杂货店只有一名售货员，已知顾客的到达过程服从泊松分布，平均到达率为每小时达过程服从泊松分布，平均到达率为每小时 20 人人；不清楚这个系统的服务时间服从什么分布，但；不清楚这个系统的服务时间服从什么分布，但从统计分析知道售货员平均服务一名顾客的时间从统计分析知道售货员平均服务一名顾客的时间为为 2 分钟，服务时间的均方差为分钟，服务时间的均方差为 1.5 分钟。试求分钟。试求这个排队系统的数量指标这个排队系统的数量指标。解：解：这是一个这是一个 M / G / 1 的排队系统，其中的排队系统，其中 = 20/60 = 0.3333 人人/分钟，分钟，1/ = 2分钟分钟， = = 0.5 人人

46、/分钟，分钟， =1.5。P0 =1 / = 0.33334,Lq =1.0412 (人人),Ls = Lq + / = 1. 7078 (人人), Wq = Lq / = 2.25/0.6 = 3.1241（分钟）（分钟）,Ws = Wq+ 1/ =5.1241（分钟）（分钟）,Pw = / = 0.6666。6 6 单服务台泊松到达、定长服务时间的单服务台泊松到达、定长服务时间的排队模型排队模型M / D / 1 / / 注：它是注：它是 M / G / 1 / / 的特殊情况的特殊情况 = 0。1、系统中无顾客的概率、系统中无顾客的概率 P0=1 / 2、平均排队的顾客数、平均排队的顾客

47、数 3、系统中的平均顾客数、系统中的平均顾客数 Ls = Lq + / 4、顾客花在排队上的平均等待时间、顾客花在排队上的平均等待时间 Wq = Lq / 5、系统在中顾客的平均逗留时间、系统在中顾客的平均逗留时间 Ws = Wq+ 1/ 6、系统中顾客必须排队等待的概率、系统中顾客必须排队等待的概率 Pw = / 7、系统中恰好有、系统中恰好有 n 个顾客的概率个顾客的概率 Pn例例2 . 某汽车冲洗服务营业部，有一套自动冲洗设某汽车冲洗服务营业部，有一套自动冲洗设备，冲洗每辆车需要备，冲洗每辆车需要 6 分钟，到此营业部来冲洗分钟，到此营业部来冲洗的汽车到达过程服从泊松分布，每小时平均到达

48、的汽车到达过程服从泊松分布，每小时平均到达 6 辆，试求这个排队系统的数量指标。辆，试求这个排队系统的数量指标。解：解：这是一个这是一个 M / D / 1 排队模型，其中排队模型，其中 = 6 辆辆/小时，小时， = 60/6 =10 辆辆/小时小时，得，得P0 =1 / = 0.4,Lq =0.45,Ls = Lq + / = 1.05, Wq = Lq / = 0.0750，Ws = Wq+ 1/ = 0.1750,Pw = / = 0.6。7 7 多服务台泊松到达、任意的服务时间、多服务台泊松到达、任意的服务时间、损失制排队模型损失制排队模型这种排队模型记为这种排队模型记为 M / G

49、 / c / c / ，是一种损，是一种损失制的模型，它要解决的主要问题是在服务机构失制的模型，它要解决的主要问题是在服务机构的空闲与顾客的流失之间找到平衡，找出最合适的空闲与顾客的流失之间找到平衡，找出最合适服务台数，使得该系统收益最大。服务台数，使得该系统收益最大。 下面我们给出计算该模型数量指标的一些公式。下面我们给出计算该模型数量指标的一些公式。注：注：该排队模型不存在平均排队的顾客数该排队模型不存在平均排队的顾客数 Lq 和顾和顾客平均的排队等待时间客平均的排队等待时间 Wq。系统中的平均顾客数系统中的平均顾客数 Ls = / (1 Pc )其中其中 Pc 是系统中恰好有是系统中恰好

50、有 c 个顾客的概率，也个顾客的概率，也就是系统里就是系统里 c 个服务台都被顾客占满的概率。个服务台都被顾客占满的概率。系统中恰好有系统中恰好有 n 个顾客的概率个顾客的概率例例3. 某电视商场专营店开展了电话订货业务，到达过某电视商场专营店开展了电话订货业务，到达过程服从泊松分布，平均到达率为每小时程服从泊松分布，平均到达率为每小时 16 个，而一个，而一个接话员处理订货事宜的时间是随着订货的产品、规个接话员处理订货事宜的时间是随着订货的产品、规格、数量及顾客的不同而变化的，但平均每个人每小格、数量及顾客的不同而变化的，但平均每个人每小时可以处理时可以处理 8 个订货电话，在此电视商场专营

51、店里安个订货电话，在此电视商场专营店里安装了一台电话自动交换台，它接到电话后可以接到任装了一台电话自动交换台，它接到电话后可以接到任一个空闲的接话员的电话上，试问该公司应安装多少一个空闲的接话员的电话上，试问该公司应安装多少台接话员的电话，使得订货电话因电话占线而损失的台接话员的电话，使得订货电话因电话占线而损失的概率不超过概率不超过 10% 。解：解：这是一个这是一个 M / G / c / c / 模型。当模型。当 c =3 时，系统中正好有时，系统中正好有 3 位顾客的概率为位顾客的概率为因因 21.05% 10%，所以不符合要求。，所以不符合要求。当当 c = 4 时，系统中正好有时，

52、系统中正好有 4 位顾客的概率为位顾客的概率为因因 9.52% 10%，所以设置四个电话较合适。，所以设置四个电话较合适。此时，电话系统里的平均顾客数为此时，电话系统里的平均顾客数为这种形式的更一般形式为这种形式的更一般形式为 M / G /c / N / ，这个一般形式和，这个一般形式和 M / G / c / c / 的区别在于的区别在于一般形式允许排队，但排队长度不超过（一般形式允许排队，但排队长度不超过（Nc）。）。 8 8 顾客来源有限制的排队模型顾客来源有限制的排队模型以上所介绍的排队系统都是顾客来源无限制的以上所介绍的排队系统都是顾客来源无限制的情况，这一节我们将介绍顾客来源有限

53、制的情况。情况，这一节我们将介绍顾客来源有限制的情况。从从 M / M / 1 / / m 这个记号中我们可以知道这个排这个记号中我们可以知道这个排队模型的顾客的总数为有限数队模型的顾客的总数为有限数 m。M / M / 1 / / m条件：条件： 单位时间顾客平均到达数单位时间顾客平均到达数 单位平均服务顾客数单位平均服务顾客数 数量指标公式数量指标公式:1、系统中无顾客的概率、系统中无顾客的概率 2、平均排队的顾客数、平均排队的顾客数 3、系统中的平均顾客数、系统中的平均顾客数 Ls = Lq + (1-p0)4、 顾客在排队上的平均花费等待时间顾客在排队上的平均花费等待时间 Wq = L

54、q /（m -Ls) 5、系统在中顾客的平均逗留时间、系统在中顾客的平均逗留时间 Ws = Wq+ 1/ 6、系统中有、系统中有 n 个顾客的概率个顾客的概率,n =0,1,2,m例例4. 某车间有某车间有 5 台机器，每台机器连续运转时台机器，每台机器连续运转时间服从负指数分布，平均连续运转时间为间服从负指数分布，平均连续运转时间为 15 分钟，有一个修理工，每次修理时间服从负分钟，有一个修理工，每次修理时间服从负指数分布，平均每次指数分布，平均每次12 分钟，假设一个机器分钟，假设一个机器停一个小时损失停一个小时损失1000元元,而一个机修工及其设而一个机修工及其设备运行备运行1小时费用为

55、小时费用为350元元.求该排队系统的数求该排队系统的数量指标量指标 P0，Lq，Ls， Wq，Ws，以及，以及 P5 ；并用并用“管理运筹学管理运筹学”软件进行经济分析，问安排多软件进行经济分析，问安排多少个修理工可使公司的运行最经济？少个修理工可使公司的运行最经济？解：解：这是一个这是一个 M / M / 1 / /5 系统。其中，系统。其中，m =5, =1/15, = 1/12, / = 0.8Lq= 2.766 ; Ls = 3.759； Wq= 33.43; Ws = 45.43； P5 = 0.2870。可见修理工几乎没有空闲时间，机器排队的时可见修理工几乎没有空闲时间，机器排队的

56、时间过长。应提高服务率或增加服务台数目间过长。应提高服务率或增加服务台数目。=0.0073 例例4:4:某某车车站站候候车车室室在在某某段段时时间间旅旅客客到到达达服服从从泊泊松松流流分分布布，平平均均速速度度为为5050人人/h/h，每每位位旅旅客客在在候候车车室室内内停停留留的的时时间间服服从从负负指指数数分分布布，平平均均停停留留时时间间为为0.5h0.5h，问问候候车车室室内平均人数为多少？（内平均人数为多少？（L)L)应应 用用 举举 例例解解：把把旅旅客客停停留留在在候候车车室室看看做做服服务务，于是系统为于是系统为M/MM/M/ / =50 =50 =1/0.5=2=1/0.5=

57、24.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 以以完完全全消消除除排排队队现现象象为为研研究究目目标标是是不不现现实实的的，那那会会造造成成服服务务人人员员和和设设施施的的严严重重浪浪费费，但但是是设设施施的的不不足足和和低低水水平平的的服服务务，又又将将引引起起太太多多的的等等待待，从从而而导导致致生生产产和和社社会会性性损损失失。从从经经济济角角度度考考虑虑，排排队队系系统统的的费费用用应应该该包包含含以以下下两两个个方方面面：一一个个是是服服务务费费用用，它它是是服服务务水水平平的的递递增增函函数数；另另一一个个是是顾顾客客等等待待的的机机会会损损失失( (费

58、费用用) )，它它是是服服务务水水平平的的递递减减函函数数。两两者的总和呈一条者的总和呈一条U U形曲线。形曲线。 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 系系统统最最优优化化的的目目标标就就是是寻寻求求上上述述合合成成费费用用曲曲线线的的最最小小点点。在在这这种种意意义义下下，排排队队系系统统的的最最优优化化问问题题通通常常分分为为两两类类：一一类类称称之之系系统统的的静静态态最最优优设设计计，目目的的在在于于使使设设备备达达到到最最大大效效益益，或或者者说说，在在保保证证一一定定服服务务质质量量指指标标的的前前题题下下，要要求求机机构构最最为为经经济济；另另

59、一一类类叫叫作作系系统统动动态态最最优优运运营营，是是指指一一个个给给定定排排队队系系统统，如如何何运运营营可可使使某某个个目目标标函函数数得得到到最最优优。归归纳纳起起来来，排排队队系系统统常常见见的的优化问题在于：优化问题在于： 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题(1)(1)确定最优服务率确定最优服务率 * *；(2)(2)确定最佳服务台数量确定最佳服务台数量c c* *；(3)(3)选择最为合适的服务规则；选择最为合适的服务规则；(4)(4)或是确定上述几个量的最优组合。或是确定上述几个量的最优组合。 研研究究排排队队系系统统的的根根本本目目的的在在于

60、于以以最最少少的的设设备备得得到到最最大大的的效效益益，或或者者说说，在在一一定定的的服服务务质质量量的的指指标标下下要要求求机机构构最最为为经经济济。排排队队系系统统的的最最优化问题分为两大类：优化问题分为两大类： 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 系系统统的的静静态态最最优优设设计计问问题题和和系系统统的的动动态态最最优优控控制制问问题题。由由于于系系统统动动态态最最优优控控制制问问题题涉涉及及更更多多的的数数学学知知识识，因因此此，本本章章只只讨讨论论系系统统静静态态的的最最优优设设计计问问题题。这这类类问问题题一一般般可可以以借借助助于于前前面所得

61、到的一些表达式来解决。面所得到的一些表达式来解决。 本本节节仅仅就就 ，c c 这这两两个个决决策策变变量量的的分分别别单单独独优优化化，介介绍绍两两个个较较简简单单的的模模型型，以以便便读读者者了了解解排排队队系系统统优优化化设设计的基本思想。计的基本思想。习题：习题：n某街道口有一电话亭，在步行距离为某街道口有一电话亭，在步行距离为分钟的拐弯处有另一个电话亭，已分钟的拐弯处有另一个电话亭，已知每次电话的平均通话时间为知每次电话的平均通话时间为/ =3=3分钟的负指数布分钟的负指数布, ,又已知到达这两个电又已知到达这两个电话亭的顾客流均为话亭的顾客流均为=10个个/小时的泊松小时的泊松流流,假如有名顾客去其中一个电话亭打假如有名顾客去其中一个电话亭打电话电话,到达时正好有人通话到达时正好有人通话,并且还有一并且还有一个人在等候个人在等候,问该顾客在原地等候问该顾客在原地等候,还是还是转去另一个电话亭打电话转去另一个电话亭打电话?