Exact FCFS Matching Rates for Two Infinite Multitype Sequences
- 1 April 2012
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 60 (2), 475-489
- https://doi.org/10.1287/opre.1110.1027
Abstract
Motivated by queues with multitype servers and multitype customers, we consider an infinite sequence of items of types 𝒞 = {c1,…,cI}, and another infinite sequence of items of types 𝒮 = {s1,…,sJ}, and a bipartite graph G of allowable matches between the types. We assume that the types of items in the two sequences are independent and identically distributed (i.i.d.) with given probability vectors α, β. Matching the two sequences on a first-come, first-served basis defines a unique infinite matching between the sequences. For (ci,sj) ∈ G we define the matching rate rci, sj as the long-term fraction of (ci, sj) matches in the infinite matching, if it exists. We describe this system by a multidimensional countable Markov chain, obtain conditions for ergodicity, and derive its stationary distribution, which is, most surprisingly, of product form. We show that if the chain is ergodic, then the matching rates exist almost surely, and we give a closed-form formula to calculate them. We point out the connection of this model to some queueing models.This publication has 14 references indexed in Scilit:
- Stability of the bipartite matching modelACM SIGMETRICS Performance Evaluation Review, 2010
- Fcfs infinite bipartite matching of servers and customersAdvances in Applied Probability, 2009
- Exact asymptotics for the stationary distribution of a Markov chain: a production modelQueueing Systems, 2009
- Fluid Models for Overloaded Multiclass Many-Server Queueing Systems with First-Come, First-Served RoutingManagement Science, 2008
- The Modern Call Center: A Multi‐Disciplinary Perspective on Operations Management ResearchProduction and Operations Management, 2007
- Telephone Call Centers: Tutorial, Review, and Research ProspectsManufacturing & Service Operations Management, 2003
- Computational complexity of loss networksTheoretical Computer Science, 1994
- A PUBLIC HOUSING QUEUE WITH RENEGINGDecision Sciences, 1988
- The slow server problemJournal of Applied Probability, 1985
- On the Stochastic Matrices Associated with Certain Queuing ProcessesThe Annals of Mathematical Statistics, 1953