Exact FCFS Matching Rates for Two Infinite Multitype Sequences

Ivo Adan () and Gideon Weiss ()
Additional contact information
Ivo Adan: Department of Mechanical Engineering, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands
Gideon Weiss: Department of Statistics, The University of Haifa, 31905 Haifa, Israel

Operations Research, 2012, vol. 60, issue 2, 475-489

Abstract: Motivated by queues with multitype servers and multitype customers, we consider an infinite sequence of items of types (C-script) = { c 1 ,..., c I }, and another infinite sequence of items of types (S-script) = { s 1 ,..., s J }, 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 (alpha), (beta). Matching the two sequences on a first-come, first-served basis defines a unique infinite matching between the sequences. For ( c i , s j ) (in) G we define the matching rate r c i , s j as the long-term fraction of ( c i , s j ) 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.

Keywords: service system; first-come; first-served policy; multitype customers and servers; infinite bipartite matching; infinite bipartite matching rates; Markov chains; product-form solution (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.1027 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:2:p:475-489

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().