排队论论文.doc

摘要：本文首先对排队论中的基本建模与相关知识点进行了总结，然后对生活中排队论的运用的例子进行了讲解，接下来对无线通信中排队论的运用进行了相关的说明。最后进行了总结。关键词：排队论，随机过程，泊松分布1、 排队论中的基本建模与相关知识点 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开系统。 各个顾客由顾客源(总体)出发，到达服务机构(服务台、服务员)前排队等候接受服务，服务完成后离开。 排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。 排队过程的一般模型 实际的排队系统虽然千差万别，但是它们有以下的共同特征： (1)有请求服务的人或物顾客； (2)有为顾客服务的人或物，即服务员或服务台； (3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。 排队系统由三个基本部分组成：输入过程排队规则服务机构。 输入过程： 这是指要求服务的顾客是按怎样的规律到达排队系统的过程。 (1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。 (2)顾客到达方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。 (3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。 服务规则： (1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。 (2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。 先到先服务。 后到先服务。 随机服务。 优先权服务。 (3)混合制。这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。 逗留时间(等待时间与服务时间之和)有限。 不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。 服务台情况： (1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。(2) 服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。(3) 服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。 排队系统的描述符号与分类 为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，肯道尔（DGKendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式： A/B/C/D/E/F 各符号的意义为： A表示顾客相继到达间隔时间分布，常用下列符号： M表示到达过程为泊松过程或负指数分布； D表示定长输入； Ek表示k阶爱尔朗分布； G表示一般相互独立的随机分布。 B表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。 M表示服务过程为泊松过程或负指数分布； D表示定长分布； Ek 表示k阶爱尔朗分布； G表示一般相互独立的随机分布。 C表示服务台(员)个数：“1”则表示单个服务台，“s”。(s1)表示多个服务台。 D表示系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则 0K，当 K=0 时，说明系统不允许等待，即为损失制。K= 时为等待制系统，此时般省略不写。K为有限整数时，表示为混合制系统。 E表示顾客源限额，分有限与无限两种，表示顾客源无限，此时一般也可省略不写。 F表示服务规则，常用下列符号： FCFS：表示先到先服务的排队规则； LCFS：表示后到先服务的排队规则； PR：表示优先权服务的排队规则。 例如：某排队问题为MMSFCFS，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。 排队系统的主要数量指标: 1.队长N(t)和排队长（队列长）Nq(t)队长是指系统中的平均顾客数(排队等待的顾客数与正在接受服务的顾客数之和)，排队长是指系统中正在排队等待服务的平均顾客数。我们希望能确定它们的分布，或至少能确定它们的平均值(即平均队长和平均排队长)及有关的矩(如方差等)。L或Ls：平均队长；Lq：平均等待队长或队列长2 等待时间Tq(t)和逗留时间T(t)从顾客到达时刻起到他开始接受服务止这段时间称为等待时间,从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间,都是随机变量。我们希望能确定它们的分布，或至少能确定它们的平均值(即平均队长和平均排队长)及有关的矩(如方差等)。 W或Ws：平均逗留时间；Wq：平均等待时间。 3忙期和闲期忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。闲期是服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。二、利用排队论在生活中建立的模型及分析 在学习中可以发现，所有的排队论建模：都是先确定人或物到达满足泊松分布（最常用的），所以人到达的时间间隔满足夫指数分布。然后建模，并使用排队论的生灭过程的结论，写出状态转移图，算出状态转移概率即可。 1.入库理货区规划 把排队论的原理应用于仓库入库理货区规划研究，建立了入库理货区规划模型；用蒙特卡洛模拟来进行大量的数据分析，减弱随机性对结果造成的影响。结果显示利用排队论原理来规划仓库入库理货区面积，可以使得理货区的利用率达到71.2%，该种方法是合理有效的。利用排队论原理，合理规划仓库功能区之一入库理货区的面积是研究的重点。主要应用的原理是排队论原理，货物入库服从M/M/1 排队模型，表示顾客相继到达间隔时间服从负指数分布（到达的顾客流是泊松流）、服务时间为负指数分布、一个服务台。使用了蒙特卡洛模拟法。建模：1.模型约束条件建立把货物到达接受服务送到货架上的过程视作一个排队系统，该系统满足以下三个条件：（1）理货区只存在一个服务窗口；（2）货物到达时间服从泊松分布；（3）货物接受理货服务时间服从负指数分布，当有货物正在接受理货服务时，再来的货物将处于等待状态。2.货物入库模型建立由货物入库模型的约束条件及理货区服务的运行机制可知，该货物入库模型服从M/M/1 排队模型，设货物到达率是，理货区的理货服务率是，可画出该系统的状态流程图。该状态图表示当系统内有k 单货物时，理货服务人员正在理货，有k-1单货物正在排队等待。 状态转移图把排队论应用于仓库布局规划。从货物到达入库再到货物出库的过程其实就是：到达- 排队- 服务- 排队- 服务- 离开这样的一个完整过程。2.在快速公交停车站中的应用 随着社会不断发展与进步，快速公共已经成为解决交通拥堵的主要手段。虽然快速公交通过了专用通道实现了区间的快速运行，但是车站站台的服务水平也决定了其整体服务水平。本文运用排队论的基本原理建立数学模型，量化了站台的停车位数以及站台可容纳的公交线路数，从而得出最优的解决方案。 基于排队论的停车位数量模型 车辆就是“顾客”,而停车位就是可提供服务的“通道”，有多少个停车位就有多少个通道提供车辆被服务。由此，我们可以这样认为:快速公交系统中的专用车道就相当于排队系统的单列多通道服务系统（M/M/N），到达的车辆按照先到先服务的原则，当停车位都有车辆接受服务时，那后到的车辆就要依次排队等候服务。这样的一个“服务系统”满足排队论的特征。 参数设置 车辆单位时间到达停车站的车辆数就是系统的到达率， 车辆单位时间接受系统服务的车辆数就是系统的服务率，即每辆车接受的服务时间就是1/。表示单位时间到达每一个通道的车辆数，既有=N。根据排队论的原理：=/，若1，则系统是不稳定的，产生的排队无法消散;若1，则系统是稳定的。 （3）模型建立 若系统中没有车辆的概率;若系统中n 辆车的概率;排队系统中的平均车辆数;平均排队长度. 对上述模型分析得出：假设N表示为有效的停车位，若nN，则说明车辆到站后没有有效地停车位，会产生等候拥堵，既是停车位无法满足公交到达的要求。若nN，说明现有停车位可以满足车辆到达的要求。一般的多车位停车位的利用率表1 所示： （4）停车位确定 为了确保排队系统的稳定， 需要满足1， 再代入nN是否满足，在进行P（nN）M 验证。（注：M 为系统的置信度，既是系统车辆数不超过设计停车位的置信度，一般取值为85%-95%。）。如若不满足则继续优化计算，一直到满足要求停止。运用了排队论的基本原理建立了停车位和站台容纳公交线路的数学模型，对快速公交的停车站场优化有一定的作用。但是还有不足之处就是没有考虑实际每辆公交车进入停车站的停车时间是不一样的，还有就是天气、车辆的长度等等一些复杂的外在因素，这些在以后的学习中会有更深入的研究。3.基于排队论下的自助取款机排队系统实证研究 ATM 客户排队是一个亟待解决的问题，衡量客户等待成本，并控制好银行随之引发的成本上升，是解决此类问题的目标。银行经营以客户至上为原则，且其营销过程中始终以提高客户满意度为原则。本文基于排队论相关理论，并结合调研数据，根据已有的排队系统分析模型，估计出当前排队系统的运行效率，以此为依据对现行排队系统的服务水平做出合理评估，有针对的提出系统优化方案。排队等待的时间越短，服务机构就越受顾客欢迎。客户满意度跟银行利润率有显著的关系，客户满意度越高，银行效益越好。 排队论是运筹学的一个分支，一般排队系统由三个基本部分组成：输入过程、排队规则、服务机构。其中服务系统一般分为三类：损失制系统。若顾客到达某系统时，正遇系统繁忙，则顾客选择离去，放弃排队，称为损失制系统。等待制系统。若顾客到达某系统时，先到顾客优先受到服务，后到顾客则需耐心等待，顺序服务，称为等待制系统。混合制系统。该系统处于损失制与等待制之间。 根据研究问题，排队论中排队系统几个重要指标：平均排队长度：Lq；顾客等待时间（平均时间）：Wq；顾客逗留时间（逗留时间）：WS；顾客数（平均数）：LS。本文选取几个常用的数量指标：平均到达率；平均服务率；系统中并联服务台数目S；服务台强度；系统处于稳态的概率P0，系统处于繁忙的概率P。在排队论的四种模型中模型一排队结构偏向单通道形式，服务阶段单一，顾客总体趋于无限，顾客到达的分布属于泊松分布，排队规则属于先来先服务，服务时间分布选取指数分布，队列长度无限。 单个服务台排队模型的构建：可以看作一个标准的M/M/1系统； 两个服务台排队模型的构建： 若该模型中顾客的排队方式是顾客到达后排成一队，依次接受服务，则该模型可以看作一个M/M/2/系统； 若在该模型中，顾客的排队方式变为到达自助银行后可到任一窗口排队，且入队后不再换队，则可形成并列的队列，这时该模型变成了由3 个M/M/1/ 子系统组成的排队系统。 三个服务台排队模型的构建： 若该模型中顾客的排队方式是顾客到达后排成一队，依次接受服务，则该模型可以看作一个M/M/3/系统； 若在该模型中，顾客的排队方式变为到达自助银行后可到任一窗口排队，且入队后不再换队，则可形成并列的队列，这时该模型变成了由3 个M/M/1/子系统组成的排队系统。 经过建模和计算，我们可以得知本市某大型生活区附近的自助银行应设为三个服务台模式，即同时开设三个自动提款机并同时运行，排队方式是顾客到达后排成一队，依次接受服务，此方案的效率最高。4.基于排队论的西安国际港务区公交优化研究 通过对西安国际港务区人流量和公交现状的分析，运用确定性排队论的方法，建立乘客流量和站台数量的合理化数学模型。运用模型分析该地区的公交状况，得出在一定显著性水平下的优化结果，最后，采用敏感性分析的方法，探讨不确定性因素对公交优化产生的影响，为优化资源配置提供一种较有效的管理决策手段。通过运用排队理论建立合理化模型探索其对该区域公交的影响，优化公交现状，方便市民出行和促进周边经济发展，解决制约港务区发展的问题，实现其经济效益和规模效益的最大化。运用排队论进行公交优化： 客户到达速率的获取和检验：客户到达情况的了解采用实地观测法；对客户到达的速率 服从的分布进行检验: 通常我们采用X2检验法来检验在时间间隔t 内出现的事件流X(t)是否服从泊松分布。经检验该数据流服从泊松分布。 模型优化分析 令N(t)表示在时间(0，t)内到达的乘客数，由于乘客到达服从泊松分布，所以具有该分布的特点。 （1）N(0)=0，即在0s内没有顾客到达。 （2）独立性，即在时刻0，t1，t2，tn到达的顾客相互独立。 （3）在(t，t+t)时间内到达的顾客只与时间间隔t有关，与起始点无关。在时间段充分小时，2 或2 以上的顾客到达系统的概率极小，可以忽略不计。 （4）车辆到达系统是相对独立的，车辆间影响较少；5. 基于排队论的仓储企业物流中心服务系统优化研究优化运输车辆的作业时间，是提高物流服务质量的有效途径之一。根据客户对时间敏感度的不同，将进仓库运输的车辆分流成了两部分；依据排队论理论,将仓储运输车辆排队系统看作是由两个独立的排队系统组成，建立了相应的数学优化模型；探讨了该模型求解算法，以使系统中的客户时间成本总和最小。 鉴于仓储运输是企业物流中的重要环节，各类货物的装卸中转需要通过仓储物流来完成。运输车辆到达物流中心，可能需要经历等待、装卸等过程，因而会产生相应的时间成本。实践表明，物流中心需要为一些重要客户提供更为快捷的服务，以满足其较为苛刻的时间要求,根据不同客户对时间敏感度不同，即单位时间成本的不同，对仓储物流服务系统中的运输车辆进行分流，将物流中心对于运输车辆的服务过程看作由两个相对独立的的子排队系统组成，运用排队论方法分析仓储物流服务系统的时间优化问题。 运用排队论的理论方法对仓储物流服务系统进行优化:从不同客户对时间敏感度存在差异为切入点，对车辆进行预分流，将最初的排队系统模型优化分为相对独立的两个小排队系统模型，优化客户在服务系统中的时间成本，提高系统的整体服务水平。 模型建立: 模型的基本假设: 1.排队和装卸服务的时间; 2.不同客户因自身原因或者其他原因，而导致对时间的敏感度不同，即他们在单位时间内所承受的时间成本不同,可以将这些客户依据对时间敏感程度进行分类，为时间敏感度较高的客户设定VIP 通道，缩短车辆在系统中的停留时间，进而降低服务系统中客户时间成本的总体水平，从而提升物流中心对于运输车辆的整体服务水平。 3.车辆到达服从泊松分布 作出这一假设，是因为到达系统的车辆满足泊松分布的三个条件： （1）车辆到达系统是相对独立的，车辆间影响较少； （2）在任意的时间段内，运输车辆到达系统所发生的概率相对稳定； （3）在时间段充分小时，2 辆或2 辆以上的车辆到达系统的概率极小，可以忽略不计。 对于车辆到达服从泊松分布，其参数为，表示单位时间内平均到达系统的车辆数。 4.物流中心对于运输车辆进行服务的时间服从负指数分布。 5.服务规则为单队，先到先服务，队长没有限制并且车辆不会因为等待而离开系统。 6.运输车辆在单位时间内的时间成本服从正态分布，即xN（，2）,并且具有不同单位时间成本的车辆在到达时间的分布上较为均匀。3、 在通信过程中的使用，尤其是无线传感器网络中的应用。 所有的排队论建模：都是先确定人或物到达满足泊松分布（最常用的），所以人到达的时间间隔满足夫指数分布。然后建模，并使用排队论的生灭过程的结论，写出状态转移图，算出状态转移概率即可。在无线通信中，也是。 在无线通信中，数据的产生满足随机分布可以看成是泊松分布。 在无线传感器网络中也会常常使用到排队论的相关内容。因为传感器网络的每个单元接收数据的能量消耗比每个单元传送数据的能量消耗小，所以常常会会当数据存储到一定的量再传输，这就有了排队论知识的相关应用。还有在传感器网络中常常用到簇的概念，就是在每个分组中选出一个“班长”簇头，所有的节点都将数据传至“班长”簇头。这里也就存在排队论的运用。下面对于簇结合的排队论运用进行了说明。一般的在cluster-tree拓扑下的WSN网络包含许多节点或CHs。实现所有这些CHs和CHs终端节点之间的同步产生周期性的信标帧。在cluster-tree拓扑,CHs组织下的每个CHs有不同的能量和层次。有些为簇头，有些是组织的成员。数据包到达MAC子层的到达率(每秒数据包)。监控事件持续至少在一段时间内。交通由簇头接收上层(l + 1)等于交通从集群的聚集在较低水平(l)。所有集群满足M / G / 1 / L队列;不同簇头的数据都满足参数为泊松分布。每个集群(即单跳的星型拓扑)建模与马尔可夫链模型描述的M / G / 1 / L队列相同。每个CH缓冲区(B)来存储数据包到达(从自己的终端节点或转发的低级别CHs)。这个缓冲区可以容纳所有传入的流量。 4 结语 在学习排队论的运用中可以发现，生活中有很多地方可以用到排队论。所有的排队论建模：都是先确定人或物到达满足泊松分布（最常用的），所以人到达的时间间隔满足负指数分布。然后建模，并使用排队论的生灭过程的结论，写出状态转移图，算出状态转移概率即可。 可以看到排队论不仅给了排队系统的一般特征，还研究不同的排队系统模型，可以直接进行使用。只需找准是什么模型，用了什么参数即可到的状态转移图和状态转移概率。给予我们建模以科学的思路和定量的方法。参考文献：1 于占泉,基于排队论的入库理货区规划研究,物流技术,2013.092 李仙仙,浅谈排队论在快速公交停车站中的应用,高校讲坛,2013.113 苏良鹏,基于排队论下的自助取款机排队系统实证研究,信息技术,2013.114 Zaker, N. ; Sch. of Electr. Eng. & Comput. Sci., Univ. of Ottawa, Ottawa, ON,Canada;Kant