Fcfs infinite bipartite matching of servers and customers
René A. Caldentey, Edward H. Kaplan, Gideon Weiss · Advances in Applied Probability · 2009
We consider an infinite sequence of customers of types and an infinite sequence of servers of types where a server of typejcan serve a subset of customer typesC(j) and where a customer of typeican be served by a subset of server typesS(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 rateri,jthat customers of typeiare assigned to servers of typej. 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 calculateri,j.