第十一章排队论

1、11. 排队论11.1基本概念排队现象是指到达服务机构的顾客数量超过服务机构提供服务的容量,也就是说顾客不能够立即得到服务而产生的等待现象。顾客可以是人,也可以是物,比如说,在银行营业部办理存取款的储户,在汽车修理厂等待修理的车辆,在流水线上等待下一到工序加工的半成品,机场厂上空等待降落的飞机,以及等待服务器处理的网页等,都被认为是顾客。服务机构可以是个人,像理发员和美容师,也可以是若干人,像医院的手术小组。服务机构也还可以是包装糖果的机器,机场的跑道,十字路口的红绿灯,以及提供网页查询的服务器等等。因为顾客到达,服务时间具有不确定性,排队系统又称随机服务系统,它的基本结构如图所示: 排队系统

2、 顾客到达 排队 排队 顾客离去 图表给出了一些现实排队系统的例子。表11.1: 排队系统应用商业服务理发店,银行柜台,机场办理登机手续的柜台,快餐店的点餐柜台运输行业城市道路的红绿灯,等待降落或起飞的飞机,出租车制造业待修理的机器,待加工的材料,生产流水线社会服务法庭,医疗机构11.1.1排队系统的特征为了描述一个排队系统,我们需要说明输入(到达)和输出(服务)过程,及其他基本特征。表列举了一些排队系统的到达和服务过程。表11.2: 排队系统举例排队系统到达过程服务过程银行顾客到达银行银员服务顾客快餐店顾客到达快餐店顾客完成点餐机场出租车等候站顾客到达等候站顾客上出租车并离开汽车修理厂故障车

3、到达修理厂车辆获得修理并被取走到达过程通常,我们假设顾客的相继到达间隔时间是相互独立并且都具有相同概率分布。在许多实际情况中,顾客的相继到达间隔是服从泊松流,或指数分布。顾客源可能是有限的,也可能是无限的。顾客到来方式可能是一个接一个的,也可能是批量的。比如,到达机场海关的旅行团就是成批顾客。一般来说,我们假设到达过程不受排队系统中顾客数量的影响。以银行为例,无论银行内有位顾客还是位顾客,顾客来到银行的到达过程是不会受到影响的。但是在两种情况下到达过程与排队系统中的顾客数量相关。第一种情况发生在顾客源是有限的系统,比如某工厂共有五台机床,若在维修部中已有两台机床,接下来到达维修部的最大量是三台

4、。另一种情况是当顾客到达排队系统时,如果服务机构的设施都被占用,顾客可能耐心等待,也可能选择离开。比如,当一家航空公司的电话订票中心出现排队时,如果顾客等待时间太长,他就可能挂断电话。顾客就会选择另外一家航空公司。服务过程为了描述排队系统的服务过程,我们需要确定服务时间的概率分布。在大多数情况下,服务时间是独立于排队系统中的顾客数量,即服务机构不会因为顾客数量增多而加快服务进度。不同服务机构提供的服务时间之间是相互独立,并都服从同一种概率分布,而且也独立于顾客相继到达间隔时间。服务时间一般分为确定型的和随机型的。在大多数情形下,服务时间的是随机型的,排队论主要研究随机型的服务时间。对于随机型的

5、服务时间,我们必须知道它的概率分布,通常假定是指数分布。从服务队列的安排上来说,我们将重点研究以下几种形式。从队列的数目来看,可以是单列,也可以是多列。服务机构在提供服务时,可以有一个或多个服务台。图说明了一个服务台的排队系统: 顾客到达流 顾客队列 服务台 图 在有多个服务台的情形中,它们可以是并列,可以是串列,也可以是混合排列,最典型的是以下二种排队方式: 顾客到达流 顾客队列 服务台 图 顾客队列 服务台 图 图表示在排队系统中存在多个队列,且服务机构提供多个服务台的排队模型,而图则表示排队系统中存在单队列,且服务机构提供多个服务台的排队模型。在日常生活中,这两种排队方式都是常见的。排队

6、规则服务机构确定的排队规则是排队系统中的一项重要条件,服务机构为顾客提供服务的规则可以采用下列几种规则,即:先到先服务,后到先服务,随机服务,和具有优先权的服务.- 先到先服务,顾客按到达排队系统的顺序接受服务,这是最普遍情况。- 后到先服务,卡车的卸货和乘用电梯的顾客都是后进入排队系统先接受服务的。- 随机服务,服务机构从等待的顾客中随机地选取其一进行服务。- 有优先权的服务,航空公司的金卡旅客有优先登机权。我们将区分有限和无限等待空间。随着顾客数目的增加,排队系统的等待空间将被占满。例如在数据通信网络中,交换机每次只能传输有限量的数据,如果数据流是无穷大,就会导致系统阻塞现象。如果不断有顾

7、客到达排队系统,服务机构必须连续提供服务。所以排队系统的服务强度反应了服务机构的繁忙程度。11.1.2 到达和服务过程的分布我们首先讨论排队系统到达过程的概率分布。设为第个顾客到达排队系统的时间.对于,定义为第个顾客与第个顾客的到达时间间隔。图说明了到达间隔和到达时间的关系.比如,及.为了推导顾客到达过程的概率模型,我们假设到达间隔之间是相互独立,对应于连续随机变.如果的密度函数为,那么对于足够小的,概率近似于. 图我们定义为到达间隔的平均值,则有: 如果时间是按分钟度量的,就是每次到达的平均间隔分钟。而则表示单位时间内的到达率,即在分钟内的顾客的到达数。在排队论的应用中,一个重要方面是选择到

8、达过程的概率分布。而最常用的概率分布是指数分布。具有参数为的指数分布的密度函数为： 那么到达间隔服从指数分布。它的分布函数是： 我们可以证明到达间隔的期望值,方差,和标准差分别为：， 指数分布具有”无记忆性”.对于任意的,有:比如,对于,和指数分布具的无记忆性说明了如果我们希望预测下一位顾客到达时间的概率分布,那么,它是与上一位到达时间无关。如果相继到达间隔服从指数分布,发生在任何一段时间内的到达数服从泊松分布。离散随机变量服从参数为的泊松分布是指对于,有: 设表示在时间区间内的到达数，那么,随机变量服从下述泊松分布: 随机变量的均值和方差分别为：； 式表明泊松分布的一个重要特征是期望值等于方

9、差。我们可利用来计算指数分布和泊松分布的概率。设具有参数指数分布的随机变量,利用的函数,有:返回随机变量小于等于的概率;返回随机变量密度函数值比如,到达间隔服从均值为的指数分布。那么,给出到达间隔小于等于分钟的概率为。函数给出和的指数密度函数的高度等于,参见表。设泊松分布的随机变量的均值为,利用的函数,有下述表达式:返回随机变量的均值小于等于的概率返回随机变量的均值等于的概率比如,如果顾客平均到达率为/每小时,并服从泊松分布,那么函数给出在一小时内到达排队系统的顾客小于等于的概率为。函数给出在一小时内到达排队系统的顾客正好等于的概率为,参见表。表11.3: 指数和泊松分布接下来,我们再讨论排队

10、系统的服务过程的概率模型。我们假设不同顾客的服务时间是相互独立的随即变量。设每位顾客服务时间随即变量为,密度函数为,设为每位顾客的平均服务时间,那么 变量表示每为顾客的平均服务时间,所以每小时服务的顾客数。这样,我们也称为服务率。比如说,意味着排队系统每小时可服务位顾客每位顾客的平均服务时间为小时。如果我们能够用指数分布来描述服务时间的随机性,我们就能直接确定顾客的剩余服务时间,而不需要知道顾客在排队系统中已经接受服务的时间。如果服务时间服从指数分布,它的密度函数为,每位顾客的平均服务时间为。11.1.3排队系统的分类根据排队系统的基本特征,对排队系统设计出一个简便分类方法。任何一类排队系统都

11、可用下述标记来表示 第一个字符表示到达过程的基本特性 到达时间间隔相互独立,服从指数分布 到达时间间隔相互独立,确定型 到达时间间隔相互独立,服从一般概率分布第二个字符说明服务过程的基本特性 服务时间相互独立,服从指数分布 服务时间间隔相互独立,确定型 服务时间间隔相互独立,服从一般概率分布第三个字符表示排队系统中的服务台数。第四个字符代表排队规则:先到先服务后到先服务随机服务 其他排队规则第五个字符说明排队系统的最大容量,即排队系统能够接受顾客的最大值(排队顾客加接收服务的顾客)。第六个字符说明了顾客源的总体大小。那么,表示到达时间间隔服从指数分布,服务时间服从指数分布,单服务台,先到先服务

12、,无限容量和无限顾客源的排队模型。表示到达时间间隔为指数分布,服务时间为一般概率分布,有三个平行服务台,随机服务,无限容量和无限顾客源的排队模型。11.1.4排队论研究的内容和目的排队论研究的内容主要有：数量指标：队长、等待时间和逗留时间的分布、忙期和闲期的分布、服务设备利用率、顾客损失率等；排队系统优化问题：系统最优设计问题和动态控制问题。而研究目是利用排队系统数量指标的概率规律，设计排队系统,使系统达到成本最小的最优设计和最优控制,或到达以最小费用实现系统的最大效益。 排队系统的数量指标是为了判断排队系统运行的效率,评估服务质量,确定系统参数的最理想值。在排队论中,用于评估排队系统的主要运

13、行指标有:排队时间和逗留时间的分布 排队时间: 顾客在排队系统中排队等待的时间也是随机变量,以表示等待时间的平均值。 逗留时间: 顾客在排队系统中的停留时间,即排队等待时间加服务时间。以表示等待时间的平均值。并且:逗留时间 等待时间 服务时间排队长和系统队长分布 排队长: 在排队系统中排队等待服务的顾客数,显然它也是随机变量。以表示排队等待服务顾客数的平均值。系统队长:在排队系统中的顾客数,即排队等待服务的顾客数加正在接受服务的顾客数。以表示顾客数的平均值,即排队系统的平均队长。 系统队长 等待服务的顾客数 正接受服务的顾客数服务机构忙期的分布忙期: 服务机构连续工作的时间长度,也是随机变量。

14、以表示服务机构连续工作的时间长度的平均值。工作量的分布 工作量:在排队系统中,顾客排队等待服务的时间加上正在接受服务顾客的剩余服务时间。定律定律给出了系统的平均队长和平均逗留时间之间的重要关系,假设系统的容量是足够大,那么:由于顾客到达排队系统的时间间隔和服务机构的服务时间都是随机变量,上述排队指标也都是随即变量。所以说,为了计算这些指标,我们需要知道它们的概率分布。我们将会看到,这些概率分布与排队系统的状态概率分布,即:排队系统队长的概率分布直接相关。如果在排队系统中有个顾客,则系统的状态就是。状态概率一般是随时刻而变化,若以表示在时刻系统状态为的概率。通常,我们用它的极限值:作为系统状态为

15、的概率。我们称极限值为系统状态到达稳态的概率,在实际应用中,对于大多数排队问题,系统会很快趋于稳定。11.2 排队模型在本节中,我们将讨论到达排队系统的时间间隔服从指数分布,服务时间服从指数分布,单服务台,服务规则是单队列,先到先服务,无限系统容量和顾客源的排队系统,根据记号,我们将它表示为模型。在下面讨论中,我们定义系统的输入和输出参数分别为: 单位时间内到达排队系统的平均数;排队系统在单位时间内的平均服务数那么,就表示平均到达时间间隔,表示平均服务时间。同时,我们还假设顾客到达排队系统的时间间隔和服务时间两个随机变量是相互独立的。由于到达时间间隔和服务时间的随机性,系统队长,即排队系统中的

16、顾客数,也具有随机性。我们也称排队系统的系统队长为系统状态。一般来说,系统状态是与时间相关的。下面首先研究模型随时间变化的系统状态,然后再分析在稳态情形下系统的状态。11.2.1依赖时间的系统状态模型的到达和服务过程都服从指数分布,我们假设到达率为,服务率为。若以表示在时刻的系统状态等于,那么在时间区间内,系统状态的变化由顾客的到达和离开确定。我们首先计算在时间区间内,发生位顾客到达的概率。指数分布的无记忆性告诉我们位顾客的到达概率不依赖于系统处于状态的时间长短,那么在时间区间内位顾客的到达概率为:利用泰勒展开式:所以,在时间区间内位顾客的到达概率等于。这说明在系统状态等于的情况下的到达率,等

17、于系统的到达率。为了计算在时刻的离去(服务)率,我们注意到如果系统状态等于,没有顾客在接受服务,所以,在时间区间内的服务率等于,即。如果系统状态等于,这时只有位顾客在接受服务。根据指数分布的无记忆性,在时间区间内位顾客完成服务的概率为:所以,对于,。根据上述结论,我们来求解排队系统在时刻的状态变化。在时间区间内,系统状态等于的概率是由下述两个事件构成: 在时刻的系统状态为,在时间区间内无顾客到达,则状态变化的概率为; 在时刻的系统状态为,在时间区间内有位顾客离去, 则状态变化的概率为;所以系统状态为的概率等于: 其中表示多于一个顾客到达或离去的概率,当非常小时,是可以忽略的,即。系统状态等于的

18、概率可由下述四个事件构成,参见表表示。表系统状态等于的事件构成情况方式时刻的状态概率内发生的事件发生的概率1无到达,无离去2到达一个,无离去3无到达,离去一个4到达一个, 离去一个在内, 系统状态等于的概率就表示为:对上式整理后并只考虑项:其中,当时,。整理后,有: 其中: 当时,那么,令,我们得到: 求解随时间变化的微分方程式是非常困难的。所以我们将主要研究当排队系统状态达到极限或稳态情况下,系统的状态概率。11.2.2极限系统状态 我们可以证明当时,及,。那么,根据微分方程式,在稳态情形下的系统状态概率,为: 或 显然,状态概率,还必须满足: 我们也可以从另外一个角度更加直观地推导中的关系

19、式.考虑模型系统状态的转移情况,参见图。 n+11nn-132101 图为了方便大家理解,假设图代表在只有个理发员的理发店中顾客人数(系统状态)的变化情况。如果在理发店中只有个顾客(状态),那么,这种状态是从店中无顾客,然后个顾客到达,或者店中有个顾客,其中个顾客接受完服务之后离去。这两种情况由图中两个指向状态的箭头所表示,一个是从状态指向状态的上箭头,另一个是从状态指向状态的下箭头。除了状态之外,其他任何一种状态都存在两种离开该状态的可能性,比如说,状态的上离开箭头说明从状态向前进入状态(从个顾客增加到个顾客),而下离开箭头说明从状态,向后退回状态(从个顾客减少到个顾客)。另一方面,任何一种

20、状态都可由两种方式进入。箭头旁边还标明从一个状态到另一个状态的平均变化率,表示向前进入下一个状态的平均变化率,表示向后退回下一个状态的平均变化率。在相继到达时间间隔和服务时间都是服从指数分布的情形下,进入和离开同一个状态的可能性是完全相等的。而在非常短的时间段内,状态转换只可能发生在两个相邻的状态,例如状态到状态,状态到状态,状态到状态等。状态转换的概率等于变化率(为到达率,为服务率)乘以发生状态转换的时间长度:状态 离开概率=进入概率 求解式,有: 考虑到,那么,所以有:如果令,则上式可以被表示为:根据我们有: 为了避免队列出现无限长的排队现象,我们有必要假设,这样一来,等比序列收敛于:将其

21、带入式左端后,得:对其整理后,我们获得:把代入公式,有: 所以,公式是排队系统在稳态情形下,系统状态为的概率计算公式。11.2.3系统指标我们可以利用系统状态概率公式推导的其他重要数量指标的概率分布和特征值。平均系统队长 平均排队长 平均逗留时间 平均排队时间 11.2.4应用举例例 短信以平均每分钟条的速度到达短信发送平台,线路的传输速度是每秒汉字。短信长度的分布近似于期望值为汉字的指数分布。假设短信处理中心的容量非常大,请计算下列系统指标:系统中短信的平均数量,系统中等待发送短信的平均数量,短信在系统中的平均逗留时间,短信在系统中等待发送的时间,系统中等待发送短信的数量多于条的可能性有多大

22、?解: 以表示发送短信的速率,以表示短信的到达速率。我们先计算发送短信的速率,因为发送一条短信平均耗时为:短信平均长度/线路的传输速度秒/条所以,发送短信的速率等于:条/秒短信的平均到达速率为:条/分钟 条/秒那么,系统中短信的平均条数: 条系统中等待发送短信的平均条数:条短信在系统中的平均逗留时间短信在系统中等待发送的时间系统中等待发送短信的条数多于条的概率可以被表示为:所以,系统中等待发送短信的条数多于条的概率为:11.2.5用电子表格求解排队模型例 考虑首都经贸公司办公用品领取问题的管理。在正常工作时间内,公司职员可以到办公用品库房领取办公用品,根据统计,到达办公用品库房职员的平均人数是

23、每小时人。公司专门雇佣一个工作人员负责处理办公用品的领取,包括检查手续和发放办公用品,平均完成办理一个职员的领取时间为两分钟。检查手续和发放的方式完全是手工操作。请用电子表格计算以下指标:库房中职员的平均人数,库房中等待办理领取手续职员的平均人数,职员在库房中的平均逗留时间,职员在库房中等待办理领取手续的时间,库房中等待职员是人的可能性有多大?解: 如果以小时为到达间隔和服务时间的基本单位,那么平均到达率为:,平均服务速度:。表给出了关于以上五个问题的解:库房中职员的平均人数可由电子表格的单元格获得:;库房中等待办理领取手续职员的平均人数可由电子表格的单元格获得: ;职员在库房中的平均逗留时间

24、可由电子表格的单元格获得:;职员在库房中等待办理领取手续的时间可由电子表格的单元格获得:;库房中等待职员是人的概率可由电子表格的单元格获得:;表11.5: 办公用品管理排队系统11.2.6 排队模型的经济分析对于排队系统来说,提高服务机构的服务水平能够降低顾客平均逗留时间,参见式,从而节省顾客的等待成本;另一方面,提高服务效率会增加服务机构的成本,所以排队系统的优化目标之一是使两者成本之和为最小。我们将看到对于模型,排队系统的优化问题完全等同于求解最优服务率。如果以表示服务机构服务每位顾客的平均成本,以表示每位顾客在排队系统中的逗留成本,以表示在单位时间内排队系统的服务成本与顾客的逗留成本之和

25、,那么: 根据,有:,将其代入上式,获得: 为了求使达到最小值的,令,那么有:求出两个最优解: 和 但是为了保证排队系统能够有效地运行,必须要求,选择为最优解,所以式的最优解为: 接下来,我们对例办公用品领取管理的排队系统进行成本分析。假设负责办理办公用品领取手续的库房管理员的工资是每小时元,公司职员的平均工资是每小时元。 那么,公司职员在领取办公用品的小时逗留成本为:元/小时由于每个职员在领取办公用品的过程中平均需要逗留小时,那么每位职员的平均排队成本为:元/小时而在小时之内,系统的逗留成本为:元/小时库房管理员服务位顾客的服务成本为:元在小时之内,系统的服务成本为:元/小时所以,在小时之内

26、,因领取办公用品而产生的逗留成本和服务成本(都是公司的成本)之和为:元/小时 我们看到职员花费在领取办公用品的成本是相当高的,倍于库房管理员的工资。有两种方法可以补救。第一种方法是提高服务效率,比如说,用工作效率更高的库房管理员替代,改进检查领取手续的流程,或者利用半制动化技术等;另一种方法是再增加一个库房管理员,我们将在下一节介绍这种方法。假设公司考虑引进半制动化系统,使库房管理员的服务效率提升,即每小时可检查个手续,如果半制动化系统的成本是每小时元,那么系统每小时的平均成本是多少?该成本是否是最优成本?这时,系统每小时的平均排队成本变成:元/小时系统每小时的平均服务成本变为:元/小时那么系

27、统每小时的平均排队成本加平均服务变为:元/小时所以,引进半制动化后,排队系统每小时平均节约:元根据,最优服务率为: 所以接近最优服务速率。11.3 排队模型的改进由于在排队模型中,关于到达,服务分布,排队规则,系统容量,和顾客源的假设非常严格,现实排队问题很难满足其所有条件。接下来我们介绍几类应用广泛的排队模型,它们都是通过对排队模型的部分条件进行修改而得到的,所以它们是排队模型的拓展。11.3.1 排队模型排队模型是设定系统的容量是有限的,即系统只能容纳有限数量的顾客。其中,表示系统能够接受顾客数的上限,在这种情况下,系统中排队等待的顾客数最多为。在任何一个时刻,当某个顾客到达排队系统时发现

28、系统中已经有个顾客,则这个顾客就被拒绝进入排队系统。 我们只考虑在稳态情形下,如何计算排队系统的状态概率,根据式,有: 根据概率分布的基本特性,有:把式代入上式,则有:由于上式左端的等比数列可以被表示为:我们可以求出:将上式代入式,获得: 因为可被改写为,所以: 根据系统状态概率公式和,我们可以计算出排队系统的主要指标:平均系统队长 平均排队长 平均逗留时间 平均排队时间 表计算了在领取办公用品的库房只能容纳人的情况下,办公用品领取排队模型的主要数量指标。表11.6: 办公用品管理排队系统(有限容量)在排队系统中,由于到达排队系统的顾客可以被拒之在系统之外,那么到达率可以大于或小于服务率,换言

29、之,可以大于或小于.如果,则,那么:, 根据,我们有:那么:根据式,情形下的系统状态为:, 利用状态概率,我们可以计算出当时,排队系统的主要指标:平均系统队长: 平均排队长 平均逗留时间 平均排队时间: 11.3.2 排队模型如果到达排队系统的顾客是来自有限的顾客群,则称顾客源为有限的。若以表示顾客源的上限,显然到达率与系统状态相关。在某个时刻,如果系统的状态等于,那么到达率就一定等于零。比如说,某工厂共有五部机床,服务机构为工厂的机床服务中心,对该服务机构来说,同时修理机床的上限为五台.表提供了只有一个维修工人的机床服务中心的系统状态随顾客源上限变化的解释:表11.7状态正常工作机床正在等待

30、维修机床服务台状况0GGGGG01GGGG12GGGB13GGBB14GBBB15BBBB1其中表示机床正常工作,表示机床正在维修.为了计算这种排队系统的系统状态(正在或等待维修机床数目),我们将系统状态的转移情况用图表示: 5图4图3图2101 图根据图,我们将每个状态的进入和离开概率表示为:状态 离开概率 = 进入概率 令,那么在稳态情形下的系统状态概率为:, 根据以及,我们可以计算排队系统的各项主要指标:平均排队长: 平均系统队长: 平均逗留时间: 平均排队时间: 表计算了在顾客源()是有限的情况下,办公用品领取管理排队模型的主要数量指标。表11.8: 办公用品管理排队系统(有限顾客源)

31、11.3.3 排队模型 如果排队系统的服务过程服从一般概率分布,并且已知它的均值为,方差为,我们可以得出的主要指标:平均排队长: 平均系统队长: 平均排队时间: 平均逗留时间: 我们注意到,以及,和都依赖服务时间的方差,显然服务时间的波动越大,平均系统和排队队列就越长,而且平均逗留和排队时间也就会越久。表给出了服务时间服从正态分布的情况下,单理发员理发店管理排队模型的主要数量指标。表11.9: 理发店排队管理系统(服务时间服从正态分布)如果排队模型的服务时间是确定的,即对所有顾客提供的服务时间都是固定的,则不再是随机变量。如果服务率为,则服务机构服务任何一位顾客的服务时间都是,并且,这时排队系

32、统的主要指标如下:平均排队长: 平均系统队长: 平均排队时间: 平均逗留时间: 我们可以通过计算当服务机构的服务率为常数的情形下,办公用品管理问题排队模型的主要指标。表给出了计算结果。表11.10: 公司办公用品管理分析: 服务时间为常数11.3.4 排队模型到目前为止,我们研究的排队系统的排队规则是先到先接受服务,我们曾经提到过其他服务规则,包括后到先接受服务,随即挑选顾客进行服务。在本节中,我们将介绍按照顾客类型提供服务的排队模型,即具有优先权的排队模型。设,和分别表示位顾客在, ,和排队系统中的平均逗留时间,那么我们可以证明: 所以,平均逗留时间不依赖于服务规则。我们还可以证明: 关系式

33、说明排队系统的平均逗留时间具有最大的波动性。然而有些服务机构的服务规则是根据顾客的类型提供服务次序。比如,医院的急诊室对重病人优先提供服务。在许多计算机系统中,在等待处理的作业队列中,耗时长的作业要等到耗时短的作业完成之后,才由CPU进行处理。我们将依据顾客类别提供服务的排队模型称为具有优先权的排队系统。假设我们可将顾客划分为种类型,记为类型,类型类型,每类顾客到达间隔服从到达率为的指数分布。服务机构对类型的服务率为。最后,我们假设标号小的类型具有先获得服务的权力。在同一类型中,顾客是根据先到先接受服务。例如,某排队系统共有三类顾客,假设系统的当前状态为,如果位类型的顾客和位类型的顾客出现在排

34、队系统中,则下一个接受服务的顾客应当是类型中最先进入排队系统的那位顾客.接下来,我们再引入下述记号: 类型顾客的平均排队长 类型顾客的平均队长 类型顾客的平均排队等待时间 类型顾客的平均逗留时间定义: 假设:那么,我们可以获得: 例 考虑单复印机的复印系统.复印排队规则为短复印工作优先于长复印工作。短复印工作的平均到达率为每小时件,长复印工作的平均到达率为每小时件;另一方面,复印一件短工作平均需要分钟,复印一件短工作平均需要分钟.计算每种工作的平均复印时间。计算两类复印工作的平均逗留和排队时间。解: 设类型短复印工作;设类型长复印工作,那么,件/小时,件/小时, 件/小时,件/小时,所以,及.

35、因为,排队系统可到达稳态.又因为,根据式,两类顾客的排队等待时间分别为:小时小时他们在系统中的逗留时间分别为:小时小时11.3.5 排队模型逗留时间的分布排队模型的主要数量指标是通过到达间隔分布和服务时间分布的特征值计算的。一般来说，在一段期间内到达率是服从泊松分布，而到达间隔和服务时间是服从指数分布。在排队模型中，顾客在系统中的逗留时间也是随机变量，我们可以证明逗留时间服从参数为的指数分布，分布函数为逗留时间的期望值为： 排队时间的期望值为：表说明了办公用品领取管理排队模型的平均逗留时间和平均排队等待时间随时间变化的情况。表11.11: 等待时间的概率分布11.4排队模型在本节中,我们把单服

36、务台的排队模型扩充到单队列,多服务台的排队模型,参见图。利用分类,记为,其中表示服务台数。排队模型的各种假设和排队规则与排队模型相同。除此之外,我们还假设各服务台之间的工作是相互独立并且具有相同的服务效率,即: 那么整个服务机构的平均服务率为: 服务机构的平均利用率则为: 显然,只有当时, 排队模型才不会出现无限的队列。11.4.1排队模型的系统指标我们首先推导排队模型的状态概率,然后根据状态概率求排队模型的主要系统指标。图说明了排队模型系统状态间的转移关系。 S+11SS-1S-232101 无顾客等待 等待队列 图我们注意到在多服务台排队系统中,如果系统中的顾客数小于服务机构提供的服务台数

37、量,排队系统就不会出现排队现象。在这种情况下,到达系统的顾客不需要排队等待,系统的整体服务效率等于,闲置服务效率为。如果顾客数大于等于服务机构的服务台数量,排队系统的所有服务台都被占据,系统的整体服务效率等于,它也是系统能够提供的最大服务效率。如果顾客到达排队系统的时间间隔和服务时间都是服从指数分布,我们可以认为在非常短的时间内进入和离开同一系统状态的概率是相等的,那么:状态 进入概率=离开概率 根据上述平衡方程,可求得: 对上式求解后,我们可获得排队模型的状态概率如下: 根据状态概率公式,我们可获得排队系统的其他数量指标:平均排队长: 平均系统队长: 平均排队时间: 平均逗留时间: 11.4.2 排队系统应用举例例 首都证券公司为节约管理费用,管理部门考虑租用办公复印机。假设有两种方案可供选择,一种方案是租用两台型复印机,型复印机每分钟可完成复印页。然而,型复印机需要手工添加纸张,有效复印速度显得较慢。顾客的复印时间与复印张数直接相关,假设复印时间是服从指