论文标题
随机的非双方匹配模型和与订单无关的损失队列
Stochastic Non-Bipartite Matching Models and Order-Independent Loss Queues
论文作者
论文摘要
在许多重要的应用程序中出现了适当匹配的项目的适当匹配项目的问题。尽管有关匹配理论的大多数文献都集中在具有固定数量的静态设置上，但最近的几项作品通过考虑一个随机模型，其中包含了一个随机模型，在该模型中，不同类别的项目根据独立的Poisson过程和分配约束来描述，由无方向性的非方向图描述。在本文中，我们证明了与该模型相关的Markov过程具有与称为独立于订单无关的损失队列的产品形式排队模型相同的过渡图。这使我们能够将现有结果适应与订单无关的（损失）队列，以适应随机匹配的模型，尤其是可以通过动态编程来实现多个性能指标的封闭形式表达式，例如等待概率或平均匹配时间。这些公式和它们允许我们得出的数值结果都可以洞悉参数对性能的影响。特别是，我们表征了所谓的重型交通制度中的性能，其中一部分的项目数量流向无穷大，而其他班级的项目变得稀缺。
The problem of appropriately matching items subject to compatibility constraints arises in a number of important applications. While most of the literature on matching theory focuses on a static setting with a fixed number of items, several recent works incorporated time by considering a stochastic model in which items of different classes arrive according to independent Poisson processes and assignment constraints are described by an undirected non-bipartite graph on the classes. In this paper, we prove that the Markov process associated with this model has the same transition diagram as in a product-form queueing model called an order-independent loss queue. This allows us to adapt existing results on order-independent (loss) queues to stochastic matching models and, in particular, to derive closed-form expressions for several performance metrics, like the waiting probability or the mean matching time, that can be implemented using dynamic programming. Both these formulas and the numerical results that they allow us to derive are used to gain insight into the impact of parameters on performance. In particular, we characterize performance in a so-called heavy-traffic regime in which the number of items of a subset of the classes goes to infinity while items of other classes become scarce.
