离散时间排队论

美国加州门洛帕克斯坦福研究院工程研究所。1957年10月14日(收到)

摘要：本文对单服务器排队系统进行了分析。时间被视为一个离散变量。到达的顾客数量，在一个固定的时间区间内，假设服从二项概率分布。假定服务时间是相同分布的。统计上是独立的，但没有其他限制。 此外，还假定顾客是按照他们的到达顺序来服务的。推导了平均排队长度和平均等待时间的公式。对于一般情况，它显示了之前得到的结果。得出相应的连续时间系统的结果。这里给出的结果是一个极限过程。结果被应用到两个方面。特殊情况，(1)服务时间分配，其形式为a。几何级数和(2)固定的服务时间分布。

本文推导了一种单服务器排队系统的平均排队时间和平均等待时间，并将其作为离散变量进行处理。你可以把这样的系统想象成一个，在这个系统中，所有的事件只允许发生在一定的定时间隔时间点上;我们将把这些点称为“时间标记”。在电子装置中，可以找到一些离散时间系统的例子，这些装置拥有控制系统内所有操作的内部时钟;然而，这些结果是基于他们自身的优点，作为已经存在的排队论的补充。读者被邀请去考察萨蒂的“排队论”的优秀“概括”，“对理论的现状进行调查，并对这个问题进行广泛的引用。”

在作者已知的之前的结果中，由于Lindley的重要例外，[6]指的是时间轴(系统中的所有事件)是连续的系统。林德利的积分方程单服务器单队列问题的公式可以由a来表示。持续时间或离散时间解释的积分方程.然而，到目前为止，只有在连续的情况下才被应用和解决。林德利对非退化统计平衡演化的条件。不过，这是本文分析的一个有效基础。

假设

这里要考虑的系统仅仅是一个服务设施，它的服务是随机到达的顾客所要求的。客户只能在一个时间点实现需求。客户服务的开始和完成也只能在时间标记上发生。接下来就是等待时间，即对于某一特定客户，到达和开始服务之间的时间限制为等于时间间隔的整数倍的值，即连续两个时间标记之间的值。

分析将局限于以下假设的系统是有效的:

1、不超过一个客户可能到达指定的时间标记。

2、客户在给定时间标记的到达是一个统计上的事件。独立于客户的到来之前的任何时间标记公关(到来一个客户在一个时间标记)t是固定值p;公共关系(一段时间没有到达)。因此，固定值1 -p = q。

3、顾客按他们到达的顺序来服务。

4、不同客户的服务时间在统计上是独立的，具有相同概率分布的变量。

假设1和2导致在给定时间内到达的客户数量的二项概率分布。由于通过一个适当的限制过程(At-gt;O)，这个输入分布进入一个泊松分布，我们将期望我们的结果在极限中达成一致。当输入服从泊松分布时，对于连续时间的情况，已经得到了[1]。

二项输入分布

考虑一个时间周期，tk，包含k个时间标记并让Pr(m到达tk)= Am,k。然后考虑上面的假设1和2。

式(1)表示已经提到的二项分布。以上，很容易看出。

为了将来的参考，我们也会看到:

为了符合大多数关于排队的文献，我们将把需求单位称为“客户”，尽管如果考虑电子系统，它可以更现实地描述为“信息”。在接下来的“Pr(X)”将代表“事件X的概率”。

E(X)将被用作X期望值的符号。

利用式(3)我们可以确定每单位时间到达的平均次数X，

这是人们本能地期待的结果。

服务时间分布

正如前面所提到的服务时间,整体的年代,只能假设值的倍数∆t。因此，s的概率分布可以作为一组概率Ck (k = 0,1)给出。

区间k的取值范围是最右边的，但不是最左边的端点。

当然，我们必须要求这样做。

我们可以得出

以供将来参考,

交通密度

在Erlangs中测量的流量密度，是指平均到达率和平均服务时间的乘积。使用(5)和(8)获得。

因此，我们可以从林德利的一个定理中推断出，随着时间的推移，第一个客户的到来，t趋于一个明确的统计平衡。我们只关心平衡条件。

队列长度

分析依赖于马尔可夫对系统统计行为特征的描述。选择这种嵌入马尔可夫链的理论基础一直是肯德尔研究的课题。[3]这将足以满足我们的目的。

Lindley已经证明了[6]，如果，且仅当E(s)小于到达或s之间的平均时间，那么等待时间分布接近非简并的极限，这肯定等于到达之间的时间。这限制了等待时间分布，并且在启动排队过程时独立于等待时间分布。D. Y. BARRER先生很好地提醒了我们林德利定理。

对于马尔柯夫链的定义和讨论，可以看到[2]

跟随肯德尔的例子。然而，一个简短的讨论将会给我们将使用的队列长度的定义提供可信性。

我们希望将队列长度用作系统的状态变量。为了使这个变量描述组成马尔可夫链的一系列事件，它必须包含过去对未来有决定性影响的所有知识。队列长度为n，定义为等待或服务的客户数量;我们必须规定何时测量排队长度。如果在服务期间测量队列长度，则不包含对过去的完整知识，因为这不是作为状态变量的一部分给出的，对于确定服务时间，在同一客户上花费的时间是必需的。

为了克服这一困难，Kendall的方法规定，只有在服务完成后，才会立即按照客户的指示立即测量排队长度。

当系统处于平衡状态时，队列长度为n的概率将被称为Pn (n=O, 1,2, a)。我们现在将得到一组方程，从这些方程中可以找到PO, P1, P2的值，至少在原则上是这样的。

在Feller^[2]之后我们将考虑转换概率矩阵，

其中rij定义为条件概率如下: rij= Pr(next state will be j if the last state were i).

在统计均衡中，我们必须

如果我们引入一个向量P，

在特殊情况下，当服务时间分解采用几何级数形式(在连续情况下等价于负指数分布)时，这里有一个例外。这个案子将在以后讨论。

然后方程(12)可以用一个矩阵方程表示，

星号表示转置矩阵

下一步将是确定r的组成部分，rij，一旦完成，P，这个状态的概率分布，原则上可以通过求解式(14)找到。为了达到这个目的，我们需要首先消除m客户在服务时间到达的概率。我们可以用公式(6)、(1)和(2)来确定bm

为了关联概率，rij和bm首先考虑我gt; 1的情况。客户X刚刚完成服务，我们知道有一个客户Y将在下一个时间进入服务。国家的下一个决定，即在队列长度中，将是Y离开服务时。Y已经包含在队列长度i中，Y离开服务后，新的队列长度j，将是j = i -1 的客户数量，而Y在服务中。从这句话我们立即得到。

通过重新排列指数

如果我-0，当X离开时，没有顾客，waitinig，去服务。当下一个客户，Y，终于到达他马上开始服务。队列长度j, Y, departs等于已经到达的cus-tomers的数量，而Y是在服务中。从这之后

并顺便说一句

等式(14)现在可以明确地写入为(17)、(18)和(15)，

bm表示式(15)的表达式。结果表明，方程(20)的解是很方便的，然后再参考方程(15)。

确定平均队列长度

式(20)通过应用generatir-g函数的方法，得到平均队列长度E(n)。我们在这里跟随克伦梅林的例子。

我们引入一个函数g(z)定义如下。

我们通过将等式的左边乘以(20)以z的幂来进行形式上的运算，这样g(z)就是由左边的总和形成的。通过在右边形成相应的和。

观察式(21)给出了什么

我们现在解(22)关于g(z)的方程，得到。

为方便起见，介绍了

用式(15)得到

我们将利用等式(23)和(25)来获得g(z)和g(z)的限值，因为z从左边趋近于1。z = 1时g(z)和g(z)的实际值为。

为了证明使用极限值的合理性[自g(z)， usilng方程(23)，不确定z = 1]，我们需要知道g(z)和g(z)[被等式(21)的解罚[de- by equation(21)]在z-1中是连续的。

考虑方程(21)中定义的q(z)。因为级数收敛于z1我们知道收敛半径大于等于1。我们还通过一个基本定理知道g(z)的收敛半径与g(z)相同。当z= 1时，g(z)和g(z)的连续性被阿贝尔定理建立在幂级数的连续性上。

下一步，我们可以通过求方程右边的极限(23)来确定Po,z 1

正如观察到的那样[参见公式(25)，(7)和(10)]

由此我们发现

根据肯德尔的一般结果.

为了得到g(z)，根据式(27)，我们可以得到E(n)，我们微分方程(23)，省去了简单性的自变量。

这可能是简化,

分子和分母都为0，且z = 1的值为0。因此，我们发现g(z)的极限为z- 1，即分子的二阶导数，(z)和分母，(z)的比值，在z =1处取值。我们发现

在前两种表达式中，前面已知的包含z = 1的因子的项被省略了，为了简单起见。h(1)已经被评估(见公式30)。我们需要计算h(1)[参见公式(25)，(5)和(9)]。

参见COPSON，一个复杂变量的函数，p. 100。

结果现在可以写出来了

简化和使用方程(31)，

方程(36)是分析的第一个和基本的结果。它明确给出了平均队列长度。要检查这个结果与之前的一个结果(见Saaty[li])，我们只需要让At-?0，保持p和X不变。然后，二项输入分布将接近泊松分布，其平均到达率是相同的。服务时间分布是连续分布的。我们从式(36)中得到

根据之前的结果。

等待时间

平均等待时间可能是由我经常使用的“1”来推导的。连续的情况。在平均等待时间内到达的顾客数量，E(w)，加上平均服务时间，E(s)， imust等于平均队列长度E(n)，

(见方程(10)),

和使用方程(36),

特殊情况下，服务时间分布是一个几何级数。

让我们假设(见式(6))d lt;1，

注意

当我们考虑一个函数时，一个简单的E(s)和E(s - At)的推导结果。

观察到

然后

.

从这一个获得

.

由此得出[见式(9)]

[见方程(8)]

然后通过插入式(36)和(39)得到几何分布的服务时间。

这两个结果与应用于泊松输入和指数服务时间的连续情况的结果是相同的。

特殊情况下，服务时间是固定的

让固定的服务时间如此。然后

再次插入式(36)和(39)我们得到固定的服务时间，所以

总结

上述结果适用于相当一般的离散时间排队问题。它们与连续时间情况下已有的结果非常类似。连续时间的结果实际上可以从简单的极限过程给出的公式中得到。

在这里考虑的排队系统的更详细的研究可以使用公式(23)中给出的生成函数作为出发点。

在离散时间域内处理其他排队系统的方式可以类似于本文所介绍的方式。甚至可以想象，一些连续时间问题可以更简单地解决，首先考虑离散时间的情况，然后通过限制过程获得连续时间的结果。

参考文献

1、“排队论中有用公式的R6sum6”J. Opns。Soc gt;,。5,161 - 200(1957)。

2、WILLIAM FELLER，概率论及其应用概论，威利,纽约,1950年。

3、所示。DAVID G. KENDALL，“队列理论中的随机过程，并通过嵌入马尔可夫链的方法进行分析。

数学。第24卷，第3期(1953年)。

剩余内容已隐藏，支付完成后下载完整资料

---

英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[280143]，资料为PDF文档或Word文档，PDF文档可免费转换为Word