搜索
排队论QueueingTheory前言•排队论（queuing),也称随机服务系统理论(RandomServiceSystemTheory),拥塞理论(CongestionTheory)，是运筹学的一个主要分支。是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。•丹麦哥本哈根电子公司电话工程师A.K.Erlang在研究电活系统时创立的，1909~1920年发表了一系列根据话务量计算电话机键配置的方法，其开创性论文“概率论和电话通讯理论”标志此理论的诞生。•排队论的发展最早是与电话，通信中的问题相联系的，到现在是排队论的传统的应用领域。•几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。•在计算机通讯网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。WheretheTimeGoes美国人一生中平均要花费--6年吃5年排队等待4年做家务2年回电话不成功1年寻找放置不当的物品8个月打开邮寄广告6个月停在红灯前排队是我们在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。前言除了上述有形的排队之外，还有大量的所谓“无形”排队现象。如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。前言排队的不一定是人，也可以是物：例如，通讯卫星与地面若干待传递的信息；生产线上原料、半成品等待加工；因故障停止运转的机器等待修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋；等等。前言•顾客可以是有限的也可以是无限的；可以是可数的，也可以是不可数的．•在水库问题里，上游来的水就是不可数的．•服务员也不一定固定在一个地方对顾客进行服务．•如出租汽车随机到来为乘客服务．上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,提供服务的人或机构称为“服务台”或“服务员”。前言商业服务系统系统类型顾客服务台理发店人理发师银行出纳服务人出纳ATM机服务人ATM机商店收银台人收银员管道服务阻塞的管道管道工电影院售票窗口人售票员机场检票处人航空公司代理人经纪人服务人股票经纪人内部服务系统系统类型顾客服务台秘书服务雇员秘书复印服务雇员复印机计算机编程服务雇员程序员大型计算机雇员计算机急救中心雇员护士传真服务雇员传真机物料处理系统货物物料处理单元维护系统设备维修工人质检站物件质检员运输服务系统系统类型顾客服务台公路收费站汽车收费员卡车装货地卡车装货工人港口卸货区轮船卸货工人等待起飞的飞机飞机跑道航班服务人飞机出租车服务人出租车电梯服务人电梯消防部门火灾消防车停车场汽车停车空间急救车服务人急救车不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。图1单服务台排队系统前言图2单队列——S个服务台并联的排队系统图3S个队列——S个服务台的并联排队系统前言图4单队——多个服务台的串联排队系统图5多队——多服务台混联网络系统前言图6随机服务系统前言一般的排队系统，都可由下面图加以描述。通常称由图8-6表示的系统为一随机聚散服务系统。任一排队系统都是一个随机聚散服务系统。“聚”表示顾客的到达，“散”表示顾客的离去。面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费。如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。前言顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。•服务系统存在来自两个矛盾方面的要求–顾客希望服务质量好，如排队等待时间短，损失率低–系统运营方希望设备利用率高•给用户一个经济上能够承受的满意的质量•哪些系统特性会影响系统的性能？–服务机构的组织方式与服务方式–顾客的输入过程和服务时间分布–系统采用的服务规则如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论——排队论所要研究解决的问题。前言它研究的内容有下列三部分：（1）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。（2）最优化问题，有分静态最优和动态最优，前者指最优设计，后者指现有排队系统最优运营。（3）排队系统的统计推断，即判断一个给定的排队系统符合于那种模型，以便根据排队理论进行分析研究。1.基本概念一排队系统的描述（一）系统特征和基本排队过程实际的排队系统虽然千差万别，但是它们有以下的共同特征：(1)有请求服务的人或物——顾客；(2)有为顾客服务的人或物，即服务员或服务台；(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。所谓随机性则是排队系统的一个普遍特点，是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。一般来说，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统。任何一个排队问题的基本排队过程都可以用表示为：每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。1.基本概念排队系统的基本特征离开排队规则到达过程排队结构服务过程退出离开需求群体一个排队系统是由三个基本部分组成的：输入过程、排队规则及服务机构．(1)输入过程输入过程就是顾客按怎样的规律到达．有时也把它称为顾客流．(2)排队规则排队规则是指服务机构什么时候允许排队，什么时候不允许排队；顾客在什么条件下不愿意排队，在什么条件下愿意排队；在顾客排队时，服务的顺序是什么，它可以是先到先服务、后到先服务、随机服务、有优先权的服务等．(3)服务机构服务机构主要是指服务台的数目，多个服务台进行服务时，服务的方式是并联还是串联；服务时间服从什么分布等．（a）没有服务员，多个服务员（ｂ）平行排列（并列）的，前后排列（串列）的，也可以是混合的。（ｃ）对单个顾客进行，对成批顾客进行（ｄ）确定型，随机型（ｅ）假定是平稳的，即分布的期望值、方差等参数都不受时间的影响。（a）先到先服务，后到先服务（b）具体的处所，抽象的处所（c）单列，多列输入即指顾客到达排队系统，可能有下列各种不同情况，当然这些情况并不是彼此排斥的1.输入过程2.排队规则3.服务机构输入过程静态动态预约定价接受/拒绝不加入排队退出排队恒定到达率的随机到达变动到达率的随机到达由设施控制顾客控制输入过程1．输入过程．一般可以从3个方面来描述—个输入过程。(1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。(2)顾客到达方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。输入过程的内容顾客总体数或顾客源数有限或无限顾客的到达类型单个或成批顾客的到达间隔时间，服务时间的分布间隔时间分布排队结构领号多条队列有限队长有限队长有限或无限队长快速通道排队结构单一队列允许或不允许移动排队结构-例多队多服务台领号34826101211579单队多服务台入口服务台...顾客源需要服务服务完毕队列排队规则排队规则静态(FCFS规则)(LCFS规则).动态基于排队状况选择即与特定顾客特征选择等待的顾客数协商优先级强占顾客服务时间(SPT规则)服务过程服务过程静态服务过程动态服务过程自我服务机械速度不同的服务率开关服务通道2.服务规则。这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。(1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。(2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：①先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。②后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。③随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。④优先权服务。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。(3)混合制．这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：①队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。②等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。③逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=∞时，混合制即成为等待制。3．服务台情况。服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：①单队——单服务台式；②单队——多服务台并联式；③多队——多服务台并联式；④单队——多服务台串联式；⑤单队——多服务台并串联混合式,以及多队——多服务台并串联混合式等等。(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。排队规则的内容损失制系统服务台被占用时新到的顾客将离开等待制系统先到先服务(FIFO，FCFS)，后到先服务LCFS，随机服务RS，优先权服务PR混合制系统损失制与等待制的混合逐个到达，成批服务；成批到达，逐个服务服务机构的内容组织方式与服务方