第一象限内随机游动及其在排队论中的应用

We will study the invariant measures and performance measures of the random walks in the quarter-plane and their applications in queueing theory. This research is one of the popular topics in queueing theory and management science. We will solve the following three problems: Firstly, for the fundamental models of random walks in the quarter-plane, we will enlarge the candidate set of the random walks in the quarter-plane which may have a tractable invariant measure. Secondly, for the variated random walks in the quarter-plane, we will characterize such random walks of which the invariant measures could be expressed as a sum of geometric terms. For the rest random walks, we will develop an approximation scheme to find the performance bounds. Finally, we will apply our theoretical results to the two-server queueing systems. The main scheme to solve the first problem is to enlarge the candidate set for the basic product-form solutions. For the second problem, the scheme is to generalize the results for the fundamental models of random walks in the quarter-plane. For the last problem, we will formulate efficient two-server queueing models from real situation. Then we will analyze these models based on the theoretical results we obtained above.

我们将研究第一象限内随机游动的平稳分布和性能指标的求解问题及其在排队论中的相关应用。该研究是当今排队论研究和管理科学研究中的热点问题。我们将解决以下几个重要问题：一，对于第一象限内随机游动的基本模型，我们将扩大拥有易得的解析解的该类随机游动的范围。二，对于几类第一象限内随机游动的变异模型，我们将刻画具有易得的解析解的该类随机游动并对剩余的随机游动的性能指标进行逼近。三，将得到的理论结果应用到基于两个服务台的排队系统中。针对第一个问题，我们解决问题的思路是扩大基本解，即几何乘积项的取值范围。针对第二个问题，我们解决问题的思路是对第一象限内随机游动基本模型所得到的结果进行推广。针对第三个问题，我们解决问题的思路是考察具体的两个服务台的排队问题，建立相关的数学模型，并运用前两个问题的理论结果及其拓展来对问题进行分析和求解。

首先，我们进一步刻画了不变测度能够表示成无穷可数个几何乘积项的线性组合的第一象限内随机游动的范围。Adan等人发现针对一些特殊的第一象限内随机游动，使用抵消方法(compensation approach)可以得到能表示成无穷可数个几何乘积项的线性组合的不变测度。我们的研究表明抵消方法(compensation approach)是唯一能得到此类不变测度的构造方法。同时，我们给出了不变测度具有此类特殊形式的第一象限内随机游动需要满足的条件。其次，我们考虑了一维或者二维有界的第一象限内的随机游动，即在双服务台排队系统中一条队伍或者两条队伍的容量有限的情形。我们利用马尔可夫报酬过程和具有易得解析形式不变测度的扰动的随机游动，建立具有通用性的逼近策略，来得到此类系统各项性能指标的逼近。我们将理论结果应用到了各类串联模型和相关双服务台排队模型。我们的研究结果比van Dijk等人人工构造的逼近策略得到的逼近结果要好，因为他们的结果是我们基于逼近策略建立的线性规划中的一个可行解，而我们的逼近结果是所有可行域中的最优解。同时，我们提出的逼近策略的计算复杂度为常数，这为有界的容量偏大的工程实际问题提供了有效的解决方法。最后，我们研究了更多双服务台排队问题及其在管理科学中的应用。在考虑顾客在非指定服务台接受服务时服务时间增加和系统不对称这两种特性时，基于模型的解析解，我们比较独立的系统，全部合作的系统和部分合作的系统的通过量。与现存主要针对对称系统发现部分合作几乎能达到全部合作的效果不同，在我们的系统中，部分合作的收益在某些参数条件下甚至能超过全部合作的收益。因此，当实际系统的形态与我们系统的参数组合类似时，可以借鉴我们的研究结果来决定最佳的合作方式。另外，我们还发现顾客的错误分配(wrong assignment)和错位接受服务(malposition)对服务时间依赖顾客类型的双服务台排队系统的合作带来的负面影响是不可忽视的。同时，我们研究了止步、插队和中途退出行为对具有优先权顾客的多服务台排队系统的影响，并利用该结果来控制系统的服务水平。