Approximating the First-Come, First-Served Stochastic Matching Model with Ohm's Law

• 成果类型: Article
• 署名作者: Fazel-Zarandi, Mohammad M.; Kaplan, Edward H.
• 署名单位: Yale University; Massachusetts Institute of Technology (MIT); Yale University; Yale University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1737
• 发表日期: 2018
• 页码: 1423-1432
• 关键词: Servers

摘要

The first-come, first-served (FCFS) stochastic matching model, where each server in an infinite sequence is matched to the first eligible customer from a second infinite sequence, developed from queueing problems addressed by Kaplan (1984) in the context of public housing assignments. The goal of this model is to determine the matching rates between eligible customer types and server types, that is, the fraction of all matches that occur between type-i customers and type- j servers. This model was solved in a beautiful paper by Adan and Weiss, but the resulting equation for the matching rates is quite complicated, involving the sum of permutation-specific terms over all permutations of the server types. Here, we develop an approximation for the matching rates based on Ohm's Law that in some cases reduces to exact results, and via analytical, numerical, and simulation examples is shown to be highly accurate. As our approximation only requires solving a system of linear equations, it provides an accurate and tractable alternative to the exact solution.