Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T15:15:45.433Z Has data issue: false hasContentIssue false

Fcfs infinite bipartite matching of servers and customers

Published online by Cambridge University Press:  01 July 2016

René Caldentey*
Affiliation:
New York University
Edward H. Kaplan*
Affiliation:
Yale School of Management, Yale School of Medicine, and Yale School of Engineering and Applied Science
Gideon Weiss*
Affiliation:
University of Haifa
*
∗ Postal address: IOMS Department, Stern Business School, New York University, New York. Email address: rcaldent@stern.nyu.edu
∗∗ Postal address: Yale School of Management, Box 208200, New Haven, CT 06520-8200, USA. Email address: edward.kaplan@yale.edu
∗∗∗ Postal address: Department of Statistics, The University of Haifa, Mount Carmel 31905, Israel. Email address: gweiss@stat.haifa.ac.il
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider an infinite sequence of customers of types and an infinite sequence of servers of types where a server of type j can serve a subset of customer types C(j) and where a customer of type i can be served by a subset of server types S(i). We assume that the types of customers and servers in the infinite sequences are random, independent, and identically distributed, and that customers and servers are matched according to their order in the sequence, on a first-come–first-served (FCFS) basis. We investigate this process of infinite bipartite matching. In particular, we are interested in the rate r i,j that customers of type i are assigned to servers of type j. We present a countable state Markov chain to describe this process, and for some previously unsolved instances, we prove ergodicity and existence of limiting rates, and calculate r i,j .

Information

Type
General Applied Probability
Copyright
Copyright © Applied Probability Trust 2009