第十一章排队论.doc

11. 排队论 基本概念排队现象是指到达服务机构的顾客数量超过服务机构提供服务的容量, 也就是说顾客不能够立即得到服务而产生的等待现象。顾客可以是人, 也可以是物, 比如说, 在银行营业部办理存取款的储户, 在汽车修理厂等待修理的车辆, 在流水线上等待下一到工序加工的半成品,机场厂上空等待降落的飞机, 以及等待服务器处理的网页等, 都被认为是顾客。服务机构可以是个人, 像理发员和美容师, 也可以是若干人, 像医院的手术小组。服务机构也还可以是包装糖果的机器, 机场的跑道, 十字路口的红绿灯, 以及提供网页查询的服务器等等。因为顾客到达, 服务时间具有不确定性, 排队系统又称随机服务系统, 它的基本结构如图 1. 11 所示: 排队系统顾客到达排队排队顾客离去图1. 11 表1. 11 给出了一些现实排队系统的例子。表 : 排队系统应用商业服务理发店, 银行柜台, 机场办理登机手续的柜台, 快餐店的点餐柜台运输行业城市道路的红绿灯, 等待降落或起飞的飞机, 出租车制造业待修理的机器, 待加工的材料, 生产流水线社会服务法庭, 医疗机构 排队系统的特征为了描述一个排队系统, 我们需要说明输入( 到达) 和输出( 服务) 过程, 及其他基本特征。表 2. 11 列举了一些排队系统的到达和服务过程。表 : 排队系统举例排队系统到达过程服务过程银行顾客到达银行银员服务顾客快餐店顾客到达快餐店顾客完成点餐机场出租车等候站顾客到达等候站顾客上出租车并离开汽车修理厂故障车到达修理厂车辆获得修理并被取走)1( 到达过程通常, 我们假设顾客的相继到达间隔时间是相互独立并且都具有相同概率分布。在许多实际情况中, 顾客的相继到达间隔是服从泊松)( Poisson 流, 或指数分布。顾客源可能是有限的, 也可能是无限的。顾客到来方式可能是一个接一个的, 也可能是批量的。比如, 到达机场海关的旅行团就是成批顾客。一般来说, 我们假设到达过程不受排队系统中顾客数量的影响。以银行为例, 无论银行内有 3 位顾客还是 300 位顾客, 顾客来到银行的到达过程是不会受到影响的。但是在两种情况下到达过程与排队系统中的顾客数量相关。第一种情况发生在顾客源是有限的系统, 比如某工厂共有五台机床, 若在维修部中已有两台机床, 接下来到达维修部的最大量是三台。另一种情况是当顾客到达排队系统时, 如果服务机构的设施都被占用, 顾客可能耐心等待, 也可能选择离开。比如, 当一家航空公司的电话订票中心出现排队时, 如果顾客等待时间太长, 他就可能挂断电话。顾客就会选择另外一家航空公司。)2( 服务过程为了描述排队系统的服务过程, 我们需要确定服务时间的概率分布。在大多数情况下,服务时间是独立于排队系统中的顾客数量, 即服务机构不会因为顾客数量增多而加快服务进度。不同服务机构提供的服务时间之间是相互独立, 并都服从同一种概率分布, 而且也独立于顾客相继到达间隔时间。服务时间一般分为确定型的和随机型的。在大多数情形下, 服务时间的是随机型的, 排队论主要研究随机型的服务时间。对于随机型的服务时间, 我们必须知道它的概率分布, 通常假定是指数分布。从服务队列的安排上来说, 我们将重点研究以下几种形式。从队列的数目来看, 可以是单列, 也可以是多列。服务机构在提供服务时, 可以有一个或多个服务台。图2. 11 说明了一个服务台的排队系统: 顾客到达流顾客队列服务台图2. 11 在有多个服务台的情形中, 它们可以是并列, 可以是串列, 也可以是混合排列, 最典型的是以下二种排队方式: 顾客到达流顾客队列服务台图3. 11 顾客队列服务台图4. 11 图3. 11 表示在排队系统中存在多个队列, 且服务机构提供多个服务台的排队模型, 而图 4. 11 则表示排队系统中存在单队列, 且服务机构提供多个服务台的排队模型。在日常生活中, 这两种排队方式都是常见的。)3( 排队规则服务机构确定的排队规则是排队系统中的一项重要条件, 服务机构为顾客提供服务的规则可以采用下列几种规则,即: 先到先服务)( FCFS , 后到先服务)( LCFS , 随机服务)( SIRO , 和具有优先权的服务)( NPRP . ---- 先到先服务, 顾客按到达排队系统的顺序接受服务, 这是最普遍情况。--- 后到先服务, 卡车的卸货和乘用电梯的顾客都是后进入排队系统先接受服务的。--- 随机服务, 服务机构从等待的顾客中随机地选取其一进行服务。--- 有优先权的服务, 航空公司的金卡旅客有优先登机权。我们将区分有限和无限等待空间。随着顾客数目的增加, 排队系统的等待空间将被占满。例如在数据通信网络中, 交换机每次只能传输有限量的数据, 如果数据流是无穷大, 就会导致系统阻塞