排队系统

排队模型典型的排队例子到达的顾客服务内容服务台在公路收费站排队的车辆收费收费车道病人看病医生到达机场上空的飞机降落跑道不能运转的机器修理修理工人到达港口的货船装货（卸货）装卸码头或泊位客户法律咨询法律咨询人员进入我方阵地的敌机我方防空火力射我方高炮或防空导弹汽车驾驶员执照年审换新管理部门年审办事员需加油车辆加油加油站的加油机排队系统基本概念“顾客”——要求服务的对象统称；“服务台”或“服务员”——提供服务的人或机构；不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统，若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。图1单服务台排队系统图2单队列——S个服务台并联的排队系统图3S个队列——S个服务台的并联排队系统图4单队——多个服务台的串联排队系统图5多队——多服务台混联、网络系统图6随机服务系统一般的排队系统，都可由下面图6加以描述。•任一排队系统都是一个随机聚散服务系统。•“聚”表示顾客的到达•“散”表示顾客的离去•随机性——所谓随机性则是排队系统的一个普遍特点，是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。•随机服务系统——一般来说，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是随机服务系统理论——排队论所要研究解决的问题。排队论是1909年由丹麦工程师爱尔朗(A.K．Erlang)在研究电话系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。排队系统的三个基本组成部分：•输入过程(顾客按照怎样的规律到达)；•排队规则(顾客按照一定规则排队等待服务)；•服务机构(服务机构的设置，服务台的数量，服务的方式，服务时间分布等)排队系统的描述符号与分类为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，肯道尔（D．G．Kendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：A/B/C/D/E/FA—表示顾客相继到达间隔时间分布，常用下列符号：M——表示到达过程为泊松过程或负指数分布；D——表示定长输入；Ek——表示k阶爱尔朗分布；G——表示一般相互独立的随机分布。B—表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。M——表示服务过程为泊松过程或负指数分布；D——表示定长分布；Ek——表示k阶爱尔朗分布；G——表示一般相互独立的随机分布。C—表示服务台(员)个数：“1”则表示单个服务台，“s”。(s＞1)表示多个服务台。D—表示系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则0K∞，当K=0时，说明系统不允许等待，即为损失制。K=∞时为等待制系统，此时一般∞省略不写。K为有限整数时，表示为混合制系统。E—表示顾客源限额，分有限与无限两种，∞表示顾客源无限，此时一般∞也可省略不写。F—表示服务规则，常用下列符号：FCFS：表示先到先服务的排队规则；LCFS：表示后到先服务的排队规则；PR：表示优先权服务的排队规则。例如：某排队问题为M／M／S／∞／∞／FCFS／，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。排队系统的主要数量指标队长——是指系统中的平均顾客数(排队等待的顾客数与正在接受服务的顾客数之和)。L或Ls——平均队长，即稳态系统任一时刻的所有顾客数的期望值；队列长——是指系统中正在排队等待服务的平均顾客数。Lq——平均等待队长或队列长，即稳态系统任一时刻的等待服务的顾客数的期望值；逗留时间——从顾客到达时刻起到他接受服务完成止这段时间。W或Ws——平均逗留时间，即(在任意时刻)进入稳态系统的顾客逗留时间的期望值；等待时间——从顾客到达时刻起到他开始接受服务止这段时间。Wq——平均等待时间，即(在任意时刻)进入稳态系统的顾客等待时间的期望值。这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。●一个服务台。●一队顾客。●顾客随机到达。●服务顺序为“先到先服务”。●系统可以到达稳定状态。●对于队列中的顾客数量没有限制。●对于接受服务的顾客数量没有限制。●所有到来的顾客都等待服务。单服务台排队模型（M/M/1）顾客到达：服从泊松随机分布泊松分布(平稳状态),0为单位时间平均到达的顾客数P{I=n}=ne-/n!(n=0,1,2,…)随机服务时间：服从负指数分布负指数分布，为平均服务率，即单位时间服务的顾客数。P（服务时间≤t)=1-e-t，t≥0服务台空闲的概率为：P0=1-λ/μ有n个顾客在系统中的概率为：Pn=(λ/μ)n(1-λ/μ)系统中顾客的平均数：L=λ/(μ-λ)平均排队人数：Lq=λWq=λ2/[μ(μ-λ)]平均逗留时间：W=1/（μ-λ）平均排队时间：Wq=W-1/μ=λ/[μ(μ-λ)]例：某理发店只有一个理发师，每小时平均有4个顾客到来，为一个顾客服务所需平均时间为6分钟。到达人数服从泊松分布，服务时间服从负指数分布，求：（1）理发店空闲和忙的概率。（2）顾客在店内平均逗留时间。（3）店内至少有一个顾客的概率。解：此题为M/M/1型＝4人/小时，＝60/6=10(人/小时）（1）P闲＝1-λ/μ＝0.6P忙＝1－P闲＝0.4（2）W=1/（μ-λ）＝1/6（小时）（3）店内至少有一个顾客的概率相当于店内忙的概率，为0.4。排队系统模拟属随机离散事件模拟应用的条件：顾客到来以及接受服务的时间较复杂，解析计算较困难的情况下。例某售票处有一服务员依次为到达的顾客售票。经观察得知，顾客到达的时间间隔为1分钟、2分钟、．．．、10分钟的可能性相同。试研究顾客在系统中的平均停留时间和售票员的空闲时间。服从均匀分布首先要构造“到达”模型，即要设计一个试验，使它和顾客到达具有相类似的性质。若取点数为１～１０的十张扑克牌，任意抽出一张，然后放回并洗牌，用每次抽出的扑克牌的点数表示相继到达的顾客的时间间隔。抽牌的模型中抽到１～１０各数的概率相等反映了顾客到达时间间隔这一随机变量的概率分布。上述问题的“服务”模型如下：取一颗正六面体的骰子，各面点数分别是１～６。将骰子投在碗中，向上一面的点数用来表示一次服务时间。用以上模型作试验，设时间为０时有一顾客到达，扔一次骰子模拟对该顾客的服务时间，然后抽一张牌、再扔一次骰子模拟第二个顾客的到达及服务情况。用同样的方法模拟以后一系列顾客的情况，并将数据记录在下表中。顾客序号到达间隔服务时间到达时间服务开始时间服务结束时间顾客排队时间顾客停留时间售票员空闲时间10108:0008:0008:0101022608:0208:0208:0806135308:0708:0808:1114044508:1108:1108:1605057308:1808:1808:2103263408:2108:2108:2504079208:3008:3008:3202583608:3308:3308:3906197308:4008:4008:43031101608:4108:4308:49280118108:4908:4908:50010124508:5308:5308:58053136408:5908:5909:03041145209:0409:0409:060211510309:1409:1409:17038166109:2009:2009:21013173609:2309:2309:29062188309:3109:3109:34032197109:3809:3809:39014201409:3909:3909:43040合计37234平均0.153.61.7按以上数据可推算出每一顾客到达、服务开始、服务结束的时刻以及顾客排队等待时间、在系统中停留时间和售票员空闲的时间。将数据依次填入表中。20次试验中顾客停留时间的平均值：72/20＝3.60分。售票员空闲时间占总时间的百分数：34/103＝33%三、排队论研究的基本问题排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。(2)统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。(3)系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。对于一般的排队系统运行情况的分析，通常是在给定输入与服务条件下，通过求解系统状态为n(有n个顾客)的概率Pn(t)，再进行计算其主要的运行指标:①系统中顾客数(队长)的期望值L或Ls；②排队等待的顾客数(排队长)的期望值Lq；③顾客在系统中全部时间(逗留时间)的期望值W或Ws；④顾客排队等待时间的期望值Wq。排队系统中，由于顾客到达分布和服务时间分布是多种多样的，加之服务台数。顾客源有限无限，排队容量有限无限等的不同组合，就会有不胜枚举的不同排队模型。