Stability of the stochastic matching model. (English) Zbl 1356.60147

Mairesse, Jean; Moyal, Pascal

J. Appl. Probab. 53, No. 4, 1064-1077 (2016).

Summary: We introduce and study a new model that we call the matching model. Items arrive one by one in a buffer and depart from it as soon as possible but by pairs. The items of a departing pair are said to be matched. There is a finite set of classes \(\mathcal V\) for the items, and the allowed matchings depend on the classes, according to a matching graph on \(\mathcal V\). Upon arrival, an item may find several possible matches in the buffer. This indeterminacy is resolved by a matching policy. When the sequence of classes of the arriving items is independent and identically distributed, the sequence of buffer-content is a Markov chain, whose stability is investigated. In particular, we prove that the model may be stable if and only if the matching graph is nonbipartite.

MSC:

60K25	Queueing theory (aspects of probability theory)
60J10	Markov chains (discrete-time Markov processes on discrete state spaces)
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90B22	Queues and service in operations research
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems
05C75	Structural characterization of families of graphs

Keywords:

Markovian queueing theory; graphs; stability; matching