排队论之简单排队系统

5.2.4 无限源的简单排队系统 所谓无限源的简单排队系统是指顾客的来源是无限的，输入过程是简单流，服务时间是负指数分布的排队系统。本节我们讨论一些典型的简单排队系统。1.排队系统排队系统是单服务台等待制排队模型,可描述为：假设顾客以Poisson过程（具有速率）到达单服务员服务台，即相继到达时间间隔为独立的指数型随机变量，具有均值，若服务员空闲，则直接接受服务，否则，顾客排队等待，服务完毕则该顾客离开系统，下一个排队中的顾客（若有）接受服务。相继服务时间假定是独立的指数型随机变量，具有均值。两个指的是相继到达的间隔时间和服务时间服从负指数分布，1指的是系统中只有一个服务台，指的是容量为无穷大，而且到达过程与服务过程是彼此独立的。为分析之，我们首先确定极限概率，为此，假定有无穷多房间，标号为 ，并假设我们指导某人进入房间（当有个顾客在系统中），则其状态转移框图如图5.8所示。图5.8 排队系统状态转移速率框图由此，我们有 状态 离开速率进入速率 解方程组，容易得到 再根据 得到：， 令，则称为系统的交通强度（traffic intensity）。值得注意的是这里要求，因为若，则，且系统中的人数随着时间的推移逐渐增多直至无穷，因此对大多数单服务排队系统，我们都假定。于是，在统计平衡的条件下（），平均队长为 （5-52） 由于，根据式（5-2）、（5-3）以及上式，可得： 平均逗留时间为： （5-53） 平均等待时间为： （5-54） 平均等待队长为： （5-55）另外，根据队长分布易知，也是系统空闲的概率，而正是系统繁忙的概率。显然，越大，系统越繁忙。队长由0变成1的时刻忙期即开始，此后第一次又变回0时忙期就结束。由简单流与负指数分布的性质，显见忙期的长度与忙期的起点无关。可以证明，闲期的期望值为，令忙期平均长度为， 则在统计平衡下，有：平均忙期：平均闲期，因此平均忙期长度为： （5-56） 一个忙期中所服务的平均顾客数为 （5-57）不难看出，在忙期内相继输出的间隔时间是独立、同参数的随机变量，即为参数的Poisson流。但是，当系统空闲后，从开始空闲时刻起，到下一个顾客服务完毕离去时之间的间隔时间显然不与服务时间同分布。下面简要推导一下排队系统的输出过程特征。令表示第个顾客服务完毕的离去时刻，则表示离去的间隔时间，于是，对， 其中表示剩余到达间隔时间，与（服务时间间隔）独立，而表示第个离去顾客服务完毕离开系统时的队长。由于 而（根据两独立随机变量和的分布计算公式计算），所以 （5-58） 此式表示在统计平衡下，相继输出的间隔时间服从参数的负指数分布。例5.5 某通信团电话维修站，有1个维修技师，每天工作10小时。待维修电话的到来服从Poisson分布，每天平均有90部电话到来，维修时间服从指数分布，平均速率为部/小时。试求排队等待维修的平均电话数；等待维修电话的多于2部的概率；如果使等待维修的电话数平均为2部，维修速率应提高多少？ 解：这是一个模型已知，则 ，解得：所以，接待速率应提高：。例5.6假设顾客以Poisson速率为每12分钟1人到达，服务时间是指数型的且服务速率是每8分钟服务1个人，和分别是多少？解：因为（人分），（人分），我们得到：，因此，系统中顾客的平均个数为2，顾客在系统中平均花费的时间是24分钟。现假设到达速率提高20到，重新计算和得到，因此，到达速率20的增加导致系统中平均顾客数增加了1倍。事实上，从式（5-52）和式（5-53）可以清楚看到，当趋于1时，的一个微小的增加都会导致和大的增加。例5.7 战时，集团军通信团的通信设备以指数速率每小时6台损坏，有一个维修技师，其维修速率是指数速率每小时8台，设备损坏而没有得到及时维修造成的损失是每台设备每小时100次通话，问：由于损坏的设备引起的平均通话损失率是多少？解：该问题是一个排队模型，其中，。则平均通话损失率每台设备每小时100次损坏设备的平均数而损坏设备的平均数就是因此，平均通话损失率等于每小时300次。2. 排队系统排队系统是一种多服务等待制系统,指的是：有个服务台独立地并行服务。当顾客到达时，若有空闲服务台便立刻接受服务，若没有空闲的服务台，则排队等待，直到有空闲的服务台时再接受服务。假定顾客单个到达，相继到达时间间隔服从参数的负指数分布，每个服务台服务时间独立、服从相同参数的负指数分布，系统容量为无穷大，而且到达与服务是彼此独立的。设表示系统中的顾客数，则是无限状态上的生灭过程，其参数为 （5-59）其分布的平稳状态分布记为，则与无限源生灭过程分析类似，考虑有个服务台，对任一状态，在统计平衡下，其平衡方程为： 状态 离开速率进入速率 。 。 。若记，则当时，解上述平衡方程组，可得： （5-60） 再由概率分布的要求：，解得上式中的。由于系统中有个服务台，所以顾客到达时需要等待的概率为 （5-61） 其中，。 式（5-61）称为Erlang等待公式，它给出了顾客到达系统时需要等待的概率。在统计平衡下，等待队长显然有分布 （5-62）所以当时，有 （5-63） 又令表示系统平衡时，正在被服务的顾客数，则 （5-64） 所以正在接受服务的顾客的平均数为： （5-65）上式表明，平均在忙的服务台的个数与服务台个数无关。平均队长为 （5-66）可以验证，时，即化为系统结果（讨论略），时即化为的有关结果。对多服务台系统，Littles公式依然成立，即有：平均等待时间为 （5-67）而平均逗留时间为 （5-68）和类似，若令表示平衡下相继离去的间隔时间，可以证明其分布函数为这表明在统计平衡下相继离去的间隔时间服从参数的负指数分布。因此，统计平衡下排队系统的输出过程与到达过程相同。 例5.8 工件按Poisson流到达服务台，平均间隔时间为10分钟，假设对每一工件的服务（加工）所需时间服从负指数分布，平均服务时间为8分钟。求： 工件在系统内等待服务的平均数和工件在系统内平均逗留时间； 若要求有90的把握使工件在系统内的逗留时间不超过30分钟，则工件的平均服务时间最多是多少？ 若每一工件的服务分两段，每段所需时间服从负指数分布，平均都为4分钟。在这种情况下，工件在系统内的平均数是多少？解：该问题属于模型依题意知 ， （个） （分钟） 由，解得，故工件的平均服务时间最多是7.69分钟。 系统已变为模型，。，=0.2，于是，以上结果表明，采用多服务员、单队列的排队系统方案，其各项运行指标都优于多队列的排队系统。事实上，该结论是一般性的，其证明过程如下。例5.9 设排队模型中到达速率为，服务速率为；排队模型中到达速率为，服务速率为。证明：排队模型中的逗留时间少于排队模型中的逗留时间，给出一个直观解释。对排队等待时间有类似结论吗？证明： 对排队模型，建立平衡方程（每个服务台服务速率为） 方程有解：，其中。又因为，可解得，也即可得。因此 由，我们得到 而对具有服务速率为的排队系统，有要使排队系统是稳定的，则，即有直观的解释是：如果一个人发现在情形中系统是空的，那么有两个服务台没有什么益处。而具有一个更快的服务台会更好。记，则 ， 那么即，而这正是排队系统稳定的要求。故对于排队等待时间也有类似结论。3. 混合制排队系统排队系统是一种多服务混合制排队系统，系统有个位置，独立平行工作的服务台数有个，。当系统中有空位置时，新到的顾客就进人系统排队等待服务，反之，若个位置已被顾客全部占用，则新到的顾客自动离开。顾客的相继到达时间间隔服从参数为的负指数分布（即按Poisson流到达），每个服务台的服务时间独立、服从参数为的负指数分布，到达与服务相互独立。与排队系统分析类似，假定表示在时刻系统中的顾客数，则是有限状态上的生灭过程，其参数为 ； （5-69）其分布的平稳分布记为，对任一状态，在统计平衡下，其平衡方程为： 状态 离开速率进入速率 。 于是对一切，有 （5-70）其中，。是损失制，当系统处于状态时，顾客不能进入系统，即顾客可进入系统的概率为，而顾客损失的概率为 （5-71） 单位时间内平均损失的顾客数为 （5-72） 单位时间内平均进入系统的顾客数为 （5-73） 由平稳分布记为，可得平均等待队长为 （5-74） 其中，。以表示平衡时正在被服务的顾客数，则，； 于是正在被服务的平均顾客数（或平均被占用的服务台数）为 （5-75） 于是得平均队长 （5-76） 再由Littles公式，得到 （5-77）特别地，对一些特殊排队系统的运行指标，有：(1) 排队系统： （5-78） （5-79） （5-80） （5-81） ， （5-82）对单服务台损失制系统，读者可自行推导相关数量指标。(2) 多服务台损失制系统： （5-83）这就是著名的Erlang（埃尔朗）公式。个服务台均忙的概率（或顾客损失的概率） （5-84）这就是著名的Erlang（埃尔朗）损失公式，它在通信网规划与设计中有重要作用。因为不允许排队，故有 ， （5-85）其中为有效到达率，在损失制系统中，还常用表示系统的绝对通过能力，用表示系统的相对通过能力，它们分别表示单位时间内系统实际可完成的服务次数和被服务的顾客数与请求服务的顾客数的比值。服务台利用率（或信道利用率）为： （5-86）此外，也可以将系统、系统、等系统看作是排队系统的特例，如令即为系统。例5.10某通信维修站，目前只有一个维修技师。假设需要维修通信设备的到来的规律服从Poisson流，平均每4小时到来一台，而设备修理的时间服从负指数分布，平均每3小时1台。如果要求等待维修的通信设备数占要维修设备数的比例为7，维修站应安排几个位置供待维修通信设备逗留？解：属于模型依题意知 （台/时），（台/时），因为 ，令，解得 。例5.11 设有一个信息交换中心，信息流为Poisson流，每分钟到达240份，线路输出率是每秒800个字符，信息长度（包括控制字符）近似负指数分布，平均长度176个字符。要使在任何瞬间缓冲器充满的概率不超过0.005，问缓冲器的容量至少应取多大？解：信息平均到达率240份分4份秒， 份秒， 0.88。显然按系统处理，于是缓冲器充满的概率为要使，由于所以即缓冲器的容量至少应为26个单位。例5.12 设某计算机有4个终端，用户按Poisson流到达，平均每10分钟到达1.5个用户。假定每个用户平均用机时间为20分钟，用机时间服从负指数分布，如果4个终端已被占用，则用户到其它计算机处接受服务，求此系统的各种指标。解：此为损失制系统，9人/小时，人/小时，3，顾客损失的概率为，单位时间内实际进入系统的平均顾客数为（人/小时），平均忙的终端数为2.295（个）。4. 具有可变到达率和可变服务率的排队模型在实际中，顾客的到达率和服务率是依系统状态的变化而变化的。一般来说，是状态的函数。例如，系统中人数较多时，后来的顾客可能不愿意再进入系统；而服务台的服务效率在顾客人数较多时则有可能提高。因此，对单服务台系统，可假设实际的到达率和服务率为：而对于多服务系统，实际的到达率和服务率可假设为：，例如，考虑一个参数为，的到达依赖状态的单服务台等待制排队系统，其相关的运行指标见下（读者可自己推导一下）：，有效到达率，其中。5.2.5 有限源简单排队系统1. 系统顾客总数是有限的排队系统称为有限源排队系统，这类排队系统的典型例子就是机器维修模型。如有个工人共同看管台机器，当机器发生故障时即由工人进行适当的修理，修复后再投入使用，修好后的机器有可能再发生故障。或看作是有个顾客来到有个服务台的系统里接受服务，每个顾客接受服务后仍回到原来的总体，还有可能再来。设每个顾客的到达率均为（含义是指单位时间内该顾客来到系统请求服务的次数），且每一顾客在系统外的时间均服从参数为的负指数分布，每个服务台的服务时间均服从参数的负指数分布。服务时间和顾客到达的时间间隔相互独立。由于在系统外的顾客的平均数为，故系统的有效到达率为。仿前分析，设平稳状态下的队长分布为，则状态间的转移速率为： ； （5-87） 其状态转移强度图如图5.9所示。图5.9系统转移速率 根据生灭过程的极限定理容易得到：记则存在,且 （5-88） 其中，。 特别地，当时，有 （5-89） 其中，。用与分别表示在统计平衡下系统平均顾客数和等待服务的顾客数，则有 （5-90）（5-91）或 （5-92）， （5-93）另外，系统运行的其它一些重要指标如下平均忙的服务台数为 （5-94）不需接受服务的顾客平均数为 （5-95）统计平衡下单位时间内需要服务的顾客平均数为 （5-96）统计平衡下单位时间内平均忙的服务台数为 （5-97）统计平衡下单位时间内平均忙的服务台数等于单位时间内需要服务的顾客平均数，即 （5-98）特别地，对单服务台（）系统，读者可自己推出相关指标。 2.损失制系统 假定有个顾客，个服务台，当个服务台都在忙时，这时需要服务的顾客不等待而离开，其它有关假定条件与系统相同。假定表示时刻系统中需要服务的顾客数，类似于系统的分析易知是有限状态上的生灭过程，其状态转移速率图如图5.10所示。参数为。图5.10 系统状态转移速率记，则根据生灭过程的极限定理易知： （5-99） 该分布称为恩格塞特（Engset）分布，而 （5-100） 称为恩格塞特损失公式，这是损失的概率。特别地，当时， （5-101） 平均需服务顾客数为 （5-102）5.2.6 其它排队系统前面讨论的内容都是按Poisson流到达与负指数服务时间的生灭过程排队系统，其主要特点是马尔可夫性，能比较容易地得到队长分布的平稳解。但如果输入过程不是Poisson流或服务时间不服从负指数分布时，仅知道系统当前的顾客数是不足以推断系统未来状态的。在这一部分里，主要介绍一些特殊排队模型，对有的模型只给出基本运行指标，而不再给出详细的推导。1. 排队系统排队系统是一种在通信网设计中经常遇到一般服务的排队系统， 它是指顾客按参数的Poisson流到达，即相邻到达的间隔时间序列独立、同负指数分布；服务时间序列独立，分布为同一般分布，记平均服务时间为。系统中只有一个服务台，容量为无穷大。顾客到达时，若服务台空闲就立即接受服务，否则就排队等待，并按到达的顺序接受服务，服务完毕后就离开系统，到达与服务彼此独立。我们首先引入概念工作量，然后用这个概念来帮助分析排队系统。对任一排队系统，定义任意时间系统的工作量为系统中所有顾客在时间的剩余服务时间总和。比如：假设系统中有3个顾客，1个顾客已经接受3个时间单位服务，而其所需服务时间是5个时间单位，还有2个在排队，各需6个时间单位的服务时间，则此时的工作量是26614。记为系统的（时间）平均工作量，回忆一下我们在（5-1）给出的基本代价方程，并考虑下面花费规则：若顾客的剩余服务时间是，则该顾客以速率为单位时间花费，而无论他是在排队或是正在接受服务。则基本代价方程变为：一个顾客花费量以和分别表示某个顾客的服务时间和花费在排队上的等待时间，由于等待时该顾客的花费速率为常数，而在接受服务时花费速率为（服务用去时间后），因此，有： 一个顾客花费量 所以 （5-103）需要特别指出的是，上述等式是一个基本排队恒等式（和5-25-4一样），并对几乎所有的模型有效。另外，若顾客的服务时间和等待时间独立，则由式（5-103）得到： （5-104）对排队系统中任一顾客，由于服务台只有一个，故有：顾客在系统中的等待他到达时系统的工作量 （5-105）对上式两边同时取数学期望，得 =到达者所看到的系统的工作量的平均值 又由于是Poisson到达，所以，对模型，有：再结合式（5-104），解得： （5-106） 而队长，等待队长，以及平均逗留时间可以由式（5-106）得到： ， （5-107）系统是以闲期和忙期交替出现的，以和分别表示第个闲期和第个忙期的长度，因此，在第一个单位时间里，服务台的空闲时间为，所以服务台空闲的时间比例，即，可以表示为： 显然，上式中的，（）相互独立，将分子和分母同除以，并利用大数定律，我们得到： （5-108） 其中和表示空闲和繁忙时间随机变量。表示的是顾客离开系统且系统为空到下一个顾客到达的时间，由于是Poisson到达，所以 （5-109）由式（5-4），知：忙服务台平均数，而忙服务台平均数又等于，所以有 （5-110）这样，由（5-108）（5-110），解得：， （5-111）另一个有意思的量是忙期中被服务的顾客数，显然， （5-112）另外，一些特殊的排队系统指标有： (1)排队系统：即，当时，有 （5-113）(2)排队系统：即服务时间分布为定长的定长分布 则当时，有 而且 （5-114）(3)排队系统：即服务时间分布为超指数分布，则当时，有 其中，且，而且 （5-115）(4)排队系统：即服务时间分布为参数的阶埃尔朗分布，则当时，有 其中，而且 （5-116）而对多服务台的系统，目前还没有精确的计算公式计算，但有一个近似公式： 例5.13 考虑一个系统：忙期中的第一个顾客的服务时间服从分布，其它顾客有服务分布。以表示忙期中的顾客数，表示任意顾客的服务时间。试证明： ； ，其中具有分布； 用和证明忙期的期望长度 求。证明： 由于是Poisson到达，假设每个顾客在服务中单位时间花费为1元，则由代价方程得 服务的平均顾客数 即 因为是具有服务分布为的到达者的比例，是具有服务分布为的到达者的比例，因此结论成立。 我们有 ， 因此 由和 或 代入到，结果得证。 ，推导出 2. 排队系统变形1）随机批大小到达的系统假设排队模型中，到达是速率为的Poisson流，但每次到达不是一个顾客，而是随机数量的顾客，服务台仍假设1个，其服务时间具有分布。以表示任意批到达的顾客数为的概率；以表示批大小的随机变量，即有。因为，基本的工作量公式变为： （5-117）为获得与的第二个关系，考虑平均顾客数。我们有：他在队列中的等待他到达时系统的工作量由于他的同批而所需的等待时间对上述等式两边同时取数学期望，得：由于同批而需的等待 （5-118）令是一个大数，则第一个批中大约有批有顾客数是，因此，这批中来自顾客数是的批次的顾客比例大约等于，令，则有：来自大小批次的顾客比例由此，大小的批次 （5-119）现在，若该批次中有个顾客，若某顾客在该批成员中位于第位，则他需等待前面的位顾客被服务完，又由于他在各个位置的可能性是一样的，故有：大小的批次将其代入式（5-119），得到： 再由式（5-117）和（5-118），我们得到： （5-120） 注： 使有限的条件是，这再次说明了到达速率一定要小于服务速率（服务台忙时）。 对确定的，随的增加而增加，表明：单服务台排队“不喜欢”方差。 其它的指标，以及可以由式（5-119）得到： （5-121）2）有优先权的排队系统有优先权的排队系统就是指将系统中的顾客分成若干类，并根据类的不同给予不同的服务优先的系统。考虑有两类顾客的情形：两类顾客独立地按参数为和的Poisson流到达，分别具有的服务分布为和。我们假定第一类顾客有服务优先权，即若有第一类顾客在排队，则不对第二类顾客服务，当然，若第二类顾客正在接受服务时第一类顾客到了，则服务继续进行直至完成。令表示第类顾客的平均等待时间，我们的目标就是计算。首先，注意到是否采用优先规则或采用什么样的优先规则，系统在任意时刻的总工作量是一样的（只要系统有顾客系统就在忙），因此，系统在有优先权规则下的工作量等于在FIFO模式下的工作量。而在FIFO模式下对排队系统有： （5-122）式（5-122）成立是因为独立的两个Poisson过程的组合仍是Poisson过程，且速率为两个分过程的速率之和。而服务分布可以对两类顾客服务时间的条件化得到。由此，由排队系统的结果，有优先权的排队系统的工作量为： （5-123） 其中有分布。记及表示任一顾客在队列中的服务和等待，它们在优先模型下是不独立的，这是因为关于的知识会给予顾客类型的信息也即给予了我们的信息。为此我们分别计算出系统类型1和类型2的平均工作量，记为类型的平均工作量，正如前面所讨论的，有： （5-124）如果我们定义 则表示类型排队平均工作量，表示类型服务平均工作量。现在我们准备计算，为此，首先考虑任一类型1顾客的到达情况，我们有：他的等待他到达时系统的类型1工作量+他到达时正接受服务的类型2工作量两边取数学期望，得： （5-125）由，再结合（5-123）（5-125），解得： （5-126）注：使有限的条件是，它独立于类型1参数；要使有限则有，因为，一个顾客的平均服务时间为，故上述条件就表示平均到达速率小于平均服务速率。 若有种类型的顾客，我们可以用类似的方式解出，最后有结果： （5-127）3排队模型排队模型是假设顾客相继到达时间间隔服从一般分布，服务时间服从指数分布并具有速率，服务台个数为1。分析这个模型直接困难来自于系统不能提供关于系统中作为状态空间的顾客数的足够信息。要知道目前所发生的，我们不但需要知道系统中顾客的数量，还要知道上一个到达至现在的流逝时间（因为无记忆），该模型的求解过程已超出本书范围，这里只给出相关指标： （5-128） （5-129） 其中，满足方程。4串联排队模型所谓的串联排队系统是指系统由串联的各个服务台组成，顾客必须依次通过每个台的服务才算服务结束。为方便，我们仅考虑一个由两个服务台组成的串联排队系统：顾客以速率到达第1台，接受服务后加入到第2台前队列，第2台服务完后就离去。假设两个服务台等待容量为无穷大。每个服务台每次服务一个顾客，服务时间服从指数分布，服务速率分别为。每个服务台服务相互独立，并且与到达过程独立（见图5.11）。图5.11 串联排队为分析这个系统，我们需要明了在这两个服务台的顾客数，为此定义状态对表示有个顾客在服务台1，个顾客在服务台2，平衡方程有：状态 离开速率进入速率 （5-130）我们不直接求解上面的方程组，回忆我们学习系统得到的结果，可知：第1个服务台输出过程仍是参数为的Poisson过程，因而第2台的输入过程还是一个参数为的Poisson过程，因而有： 服务台1有个顾客类似地，有 服务台2有个顾客如果服务台1和服务台2的顾客数是独立的随机变量，则有 （5-131）可以验证（5-131）确实是满足平衡方程组（5.130）的解，因而是极限概率。由式（5-131）可以求出系统的顾客平均数为： （5-132） 由此得一个顾客在系统中花费的平均时间为 （5-133）注：上面的结果可以进行推广。考虑有个服务台的情形：顾客从系统外到达第服务台服从参数为的负指数分布，然后他们加入到第服务台队列直至轮到他们被服务，一旦在第服务台服务完，他们就以概率加入到第服务台队列。因此，且表示顾客在第服务台服务完后离开系统的概率。我们令表示顾客到服务台的总速率，则可以从下面的方程组解出： （5-134）等式（5-134）成立是因为是自系统外到达服务台顾客的速率，而是顾客离开服务台的速率（流入速率等于流出速率），是自服务台到达服务台的顾客速率。由此，每个服务台顾客数彼此独立且具有形式： 服务台有个顾客其中是服务台的指数服务速率，是（5-134）的解，且对所有的，。它等价于证明极限概率有个顾客在服务台满足： （5-135）而（5-135）的证明可以通过验证它满足该模型的平衡方程得到证明。系统的平均顾客数为 服务台的平均顾客数 （5-136）顾客在系统中花费的平均时间可以由和（为什么不是？）得到： （5-137） 例5.14 考虑两个服务台系统，系统外顾客以Poisson速率4到达服务台1，以Poisson速率5到达服务台2；服务台1和服务台2的服务速率分别为8和10，在服务台1完成服务后等可能到服务台2和离开系统（即），而在服务台2完成服务后以25的概率到服务台1或离开系统（即）。确定极限概率，和。 解：由（5-134），服务台1和服务台2的总的到达速率和满足：解之，得：因此，5.2.7 排队论在军事通信中的应用1用排队论分析通信网的业务模型的一般步骤通信网中的信息流总是随机的，当用到一些网络资源（比如信道）时，必然会出现排队现象。通信网中的许多指标都可以与排队论的术语相对应。如：通道数相当于服务台个数（窗口数），单位时间内的平均呼叫数相当于顾客到达率，每次呼叫占用线路的平均时间相当于平均服务时间。信道利用率即单位时间通过的业务量与线路容量的比值，相当于排队模型中的窗口占用率等等。 通信网中的业务模型可以用排队论来分析，一般有以下几个步骤： 第一步：选择适当的排队模型，使之与实际问题