论文标题
随机二分匹配模型的性能评估
Performance Evaluation of Stochastic Bipartite Matching Models
论文作者
论文摘要
我们考虑了由多级客户和多级服务器组成的随机两分匹配模型。客户和服务器类之间的兼容性约束用两分图描述。每次插槽，恰好一个客户和一台服务器到达。传入的客户（分别服务器）与最早的到达服务器（分别客户）匹配，其类与自己的类兼容（如果有的话），在这种情况下，匹配的客户服务器夫妇立即离开系统；否则，传入的客户（分别服务器）将在系统中等待直到匹配为止。与古典排队模型相反，客户和服务器都可能需要等待，以便它们的角色可以互换。尽管（基础过程）该模型已经众所周知，该模型具有产品形式的固定分布，但本文为该分布的标准化常数以及客户和服务器的等待概率和平均等待时间提供了新的紧凑型表达式。我们还提供了一个数字示例，并进行了一些重要的观察。
We consider a stochastic bipartite matching model consisting of multi-class customers and multi-class servers. Compatibility constraints between the customer and server classes are described by a bipartite graph. Each time slot, exactly one customer and one server arrive. The incoming customer (resp. server) is matched with the earliest arrived server (resp. customer) with a class that is compatible with its own class, if there is any, in which case the matched customer-server couple immediately leaves the system; otherwise, the incoming customer (resp. server) waits in the system until it is matched. Contrary to classical queueing models, both customers and servers may have to wait, so that their roles are interchangeable. While (the process underlying) this model was already known to have a product-form stationary distribution, this paper derives a new compact and manageable expression for the normalization constant of this distribution, as well as for the waiting probability and mean waiting time of customers and servers. We also provide a numerical example and make some important observations.
