毕业设计（论文）文献译文：排队论

排队论在几乎所有的服务设施调查中，排队论都扮演着重要的角色。本文旨在介绍排队论的重点，对多服务器系统、矩阵分析技术和客户的重复行为着重介绍。它偏向于电话和呼叫中心的应用，通过为广泛的排队问题提供适用的结果，试图在理论上和实用价值之间达到一定的平衡。如果没有可用的精确解，则提供合理的近似解。1.1介绍排队论1.1.1历史作为概率论的一部分，排队理论从过去几十年的经典远程交通工程演变而来。1909年，丹麦电信工程师埃尔朗(A.K.Erlang)发表了一篇题为“概率与电话通话理论”的论文。在20世纪20年代早期，他创建了著名的Erlang模型来评估多通道点对点转换的损失概率。Erlang模型被扩展到允许在有限的源输入情况下进行计算，这是由T.O.恩特在几年后创建的Engset模型。1951年，d·g·肯德尔出版了他关于嵌入式马尔科夫斯克的著作，这是在相当普遍的输入条件下计算排队系统的基础。他还为使用的排队系统作出了定义。与此同时，林德利开发了一个方程，允许在相当普遍的输入和服务条件下，对排队系统的结果进行计算。1957年，J.R.杰克逊开始对网络队列进行调查，从而创建所谓的排队网络模型。随着计算机和计算机网络的出现，排队系统和排队网络被认为是各种应用程序的强大分析设计工具。1.1.2应用程序如上所述，排队理论允许计算广泛的应用程序。这些包括：在制造系统中，原材料是从一个站运送到下一站的。每一站都完成了任务，原材料被允许进入下一站。如果在所有站的处理时间都是相等的，当装配线在同步模式下工作时，当项目从一个站到另一个站的频率不变时，就不会发生等待。在异步模式下，对站点的排队可能会发生，并且对整体性能有明显的影响。计算机系统要执行实时或高速的操作，通常会由于单个的设备，如CPU、磁盘驱动器、图形卡、通信端口或总线系统无法正常工作而导致糟糕的性能。通过使用分析模型，可以检测到异常装置，并进行升级。根据计算机网络中使用的协议的性质，由于传输网络的拥塞而延迟，这些延迟可能被视为等待时间，直到媒体重获自由，从而允许计算吞吐量、整体延迟和其他性能值。远程交通工程处理的是站点和连接线的可用性。尽管这些系统的特点是阻塞多于延迟，但它们仍然属于排队系统。随着新媒体在远程交通工程中的引入，延迟变得更加重要。远程交通工程现在还需要覆盖范围广泛的新单位，如公告板、交互式语音响应单元、媒体服务器、媒体和信号网关。人力资源管理关心的最重要的是个人配置。在人力资源管理中，排队理论的应用在呼叫中心是最明显的，在呼叫中心，代理必须根据调用的负载分配。依赖于其他的技术，如预测，排队理论可以被看作是一个广泛的解决方法，用于解决人力管理中出现的问题。显然，上面的列表还不充足，可能还会扩展到其他应用程序。为了获得更多信息，读者可以参考诸如IEEE通讯杂志、IEEE计算机、贝尔实验室技术系统杂志之类的出版物。1.1.3特征排队系统可以被描述为一个随机服务系统，在此系统中，客户根据一个服务过程的服务设施来到达一个过程。每个服务设施可能包含一个或多个服务器。一般认为，每个服务器一次只能服务一个客户。如果所有服务器都处于繁忙状态，则客户必须排队等待服务。如果服务器再次获得自由，则根据队列规则给出的规则从队列中选择下一个客户。在服务期间，客户可能会运行一个或多个服务阶段，然后离开这个系统。进入进一步的细节之前,最重要的方面的排队系统将列出并简要描述。到达过程由统计分布及其参数给出。通常，指数分布被假定为到达模式，以作为时间单位的平均数量。当在PBX中确定主干负载时，通常会在繁忙时间的调用中给出到达模式。更多的一般到达过程也以其他模式为特征。这包括批批到达和时间依赖。服务过程描述类似于到达过程。再一次，当释放这些过程时，在实践中，与到达过程相反，服务过程高度依赖于系统的状态。如果排队系统是空的，服务设施是空闲的。排队过程是指在排队条件下为服务选择客户的方式。经常使用,最常见的是先来先服务。其他包括后来先服务,随机和优先级服务。离开过程很少被用来描述排队系统，因为它可以被看作是排队纪律、到达和服务过程的结果。在某些情况下，到达和离开过程遵循相同的统计分布。这已经成为队列网络建模中的一个非常重要的事实。系统容量引入了排队系统中的自然边界。在生命系统中,只有有限数量的资源,如树干PBX,计算机内存或网络缓冲区。在排队网络中,节点与有限的系统容量可能阻止客户前面的节点,以及节点的容量限制。服务器的数量指的是并行节点的数量，它可以同时服务客户。在电话系统中，服务器可以描述箱子、音调检测器、音频发生器和时间槽。服务阶段的数量和结构，客户在离开系统之前可能需要访问。在计算机系统中，作业可能必须两次访问CPU，一次只访问I/O处理器。在实践中，存在很多情况，这些情况可以通过复杂的队列系统和服务阶段或简单的计算机网络来建模。1.1.4在排队系统中使用统计分布如上所述，到达、服务和离开过程通过统计分布来描述。最常见的分布是指数和泊松分布。统计分布通过自定义参数来调整。显然,更多的参数可用于特定分布,更灵活。另一方面，估计一堆参数可能成为不可行的任务。结果表明，更复杂的分布会导致几乎难以处理的排队模型。因此，选择一个合适的分布，从而确定一个分析模型，该模型提供了对正在考虑的系统的近似值。有时结果仅局限于一个特定的地区。一个例子是重负荷近似，它不能为轻负载系统提供适当的结果。排队系统中最有吸引力的属性之一是指数分布的无记忆或马尔可夫属性。无记忆的属性状态，即指数过程的剩余时间不依赖于过去。对排队系统进行分析的结果包括：给定一个指数分布的服务时间，在将来某个时间完成服务的客户是独立于他目前为止服务的时间。剩余的服务时间仍然是服从指数分布的。工作的结束可以被看成是一个突发事件，而不是工作进展的结果。服务器只会忘记它运行的时间。给定泊松分布的到达时间，在任何时间点到达的时间是服从指数分布的，而且，可以证明，指数分布是唯一连续分布的无记忆性质的分布。指数分布的离散对应关系是几何分布，它通常被用于基于单元的网络。为了证明统计分布的几个方面及其对排队模型的影响，将系统的分析作为一个例子。它将显示，抽样数据如何与指数服务时间分布相匹配。相位法没有处理剩余时间的需要，指数分布的使用变得非常流行。为了克服排队系统中指数分布的不足，在标准模型中经常使用指数分布的混合，而不是推导出适合所需的新模型。实际上，这些混合分布由于其广泛的参数集而变得高度灵活。1.1.5近似的任意分布在大多数实际情况下，很少会遇到像指数和Erlang这样的分布。这就提出了一个问题，在实践中，哪种类型的分布可能足以捕获几乎所有的情况。幸运的是，有一个答案。结果表明，串行或并行(也称为广义Erlang分布)的指数分布混合能够合理地近似于任何非负(和绝对连续的)分布。但没有损失，还有更多收获。事实上，每个分支中相等强度的假设并不影响结果。这就导致了超Erlang分布的存在，它由Erlang分布的混合物所组成。在此之前，必须引入概率分布的弱收敛概念。这里省略了证明，因为它在概率度量空间中咨询了完整性和密度等概念。对于上面提到的问题，值得注意的是，串行或并行的指数分布是等价于考克斯分布的，这是阶段类型分布的一部分。因此每个所述分布的存在足够接近所需的目标分布。1.1.6更新流程在前面的部分中，我们已经了解到泊松过程对应于指数间的到达时间。通过对指数的假设，为一个到达的更新过程。更新过程的特征是在一个共同的分布之后独立的互连时间。它们可能被应用到到达以及服务过程中，因此在接下来的事件中，将被称为更新。对于泊松过程，根据指数分布，Tn的分布是独立的。因此，Sn的分布是由指数分布的n倍卷积得到的，这是一个n阶的Erlang分布。N(t)数到时间t(描述泊松过程)的更新数。证明是基于大数定律的，这里省略了。第二个极限只包含概率1。也就是说，规则中有例外，但这些例外是可以忽略的。在到达和服务过程的上下文中，仅仅描述了接口和服务时间。因此，这两种限制汇合到到达和服务过程。这些结果证实了我们的猜想:观察过程很长一段时间,出现的数量除以总时间,为到达这一过程的速度。因为它需要点进程的理论，而这不是当前讨论的核心。还要注意上面的连续性的准确描述。它源于这样一个事实,不能从左边定义0并且连续分布为正实数。更多信息在点进程的叠加上咨询。1.1.7队列系统的性能特征讨论了队列模型和统计分布的各个方面。由于模型的有效性随其结果而变化，因此必须选择合适的模型和算法。另一个重要的因素是人们的观点。对一个到达客户的性能值并不一定和从服务器的角度所确定的值相同。同样，统计分布的影响也不容忽视。然而，事实证明，当使用具有指数分布的互抵和服务时间的模型时这些性能值是相同的。另一方面，许多有用的关系也已经决定了更多的一般情况。尽管队列模型在应用程序和复杂性方面各不相同，但一般都具有常见的性能特征。1.1.8排队学科大多数排队系统将先到先服务作为一个排队纪律。事实证明,大多数结果推导出根据先到先服务来保持有效,例如先得(lcf)、轮循(RR)和处理器共享(PS)学科，但这并不适用于更复杂的学科。在优先级系统中，客户按类分组，每