Stochastic non-bipartite matching models and order-independent loss queues
From MaRDI portal
(Redirected from Publication:5030973)
Abstract: The problem of appropriately matching items subject to compatibility constraints arises in a number of important applications. While most of the literature on matching theory focuses on a static setting with a fixed number of items, several recent works incorporated time by considering a stochastic model in which items of different classes arrive according to independent Poisson processes and assignment constraints are described by an undirected non-bipartite graph on the classes. In this paper, we prove that the Markov process associated with this model has the same transition diagram as in a product-form queueing model called an order-independent loss queue. This allows us to adapt existing results on order-independent (loss) queues to stochastic matching models and, in particular, to derive closed-form expressions for several performance metrics, like the waiting probability or the mean matching time, that can be implemented using dynamic programming. Both these formulas and the numerical results that they allow us to derive are used to gain insight into the impact of parameters on performance. In particular, we characterize performance in a so-called heavy-traffic regime in which the number of items of a subset of the classes goes to infinity while items of other classes become scarce.
Recommendations
Cites work
- A distributional form of Little's law
- A general stochastic matching model on multigraphs
- A product form for the general stochastic matching model
- Computational complexity of loss networks
- Exact FCFS matching rates for two infinite multitype sequences
- Fcfs infinite bipartite matching of servers and customers
- scientific article; zbMATH DE number 3223982 (Why is no real title available?)
- Job assignment in large-scale service systems with affinity relations
- Networks with customers, signals, and product form solutions
- Order independent loss queues
- Poly-symmetry in processor-sharing systems
- Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview
- Quasi-reversible multiclass queues with order independent departure rates
- Reversibility and further properties of FCFS infinite bipartite matching
- Reversibility and stochastic networks. With a new preface
- Stability of the bipartite matching model
- Stability of the stochastic matching model
Cited in
(19)- Order independent loss queues
- Matching queues with reneging: a product form solution
- Directed FCFS infinite bipartite matching
- Fluid and diffusion approximations of probabilistic matching systems
- Stability of the stochastic matching model
- One-Attribute Sequential Assignment Match Processes in Discrete Time
- A product form for the general stochastic matching model
- A general stochastic matching model on multigraphs
- On the dynamic control of matching queues
- Stability regions of systems with compatibilities and ubiquitous measures on graphs
- Editorial introduction: Special issue on product forms, stochastic matching, and redundancy
- Multi-component matching queues in heavy traffic
- Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy
- New directions in pass-and-swap queues
- Performance paradox of dynamic matching models under greedy policies
- On the sub-additivity of stochastic matching
- Insensitivity for matching systems
- Perfect sampling of stochastic matching models with reneging
- Admission control of quasi-reversible queueing systems: optimization and reinforcement learning
This page was built for publication: Stochastic non-bipartite matching models and order-independent loss queues
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5030973)
