Hostname: page-component-6bf8c574d5-2jptb Total loading time: 0 Render date: 2025-02-21T20:12:34.687Z Has data issue: false hasContentIssue false
  • English
  • Français

A stochastic matching model on hypergraphs

Part of: Computer system organization Markov processes Graph theory

Published online by Cambridge University Press:  22 November 2021

Youssef Rahme  and
Pascal Moyal Open the ORCID record for Pascal Moyal [Opens in a new window]
Youssef Rahme*
Affiliation:
Université de Technologie de Compiègne
Pascal Moyal*
Affiliation:
Université de Lorraine
*
*Postal address: LMAC, Université de Technologie de Compiègne, 60203 Compiègne Cedex, France. Email: [email protected]
**Postal address: Institut Elie Cartan, Université de Lorraine, F-54506 Nancy Cedex, France. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Motivated by applications to a wide range of areas, including assemble-to-order systems, operations scheduling, healthcare systems, and the collaborative economy, we study a stochastic matching model on hypergraphs, extending the model of Mairesse and Moyal (J. Appl. Prob.53, 2016) to the case of hypergraphical (rather than graphical) matching structures. We address a discrete-event system under a random input of single items, simply using the system as an interface to be matched in groups of two or more. We primarily study the stability of this model, for various hypergraph geometries.

Keywords

Markovian queueing theorystabilitymatchinghypergraph

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 68M20: Performance evaluation; queueing; scheduling 05C65: Hypergraphs
Type
Original Article
Information
Advances in Applied Probability , Volume 53 , Issue 4 , December 2021 , pp. 951 - 980
Check for updates
Copyright
© The Author(s) 2021. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adan, I., Bušić, A., Mairesse, J. and Weiss, G. (2017). Reversibility and further properties of the FCFM bipartite matching model. Preprint. Available at https://arxiv.org/abs/1507.05939.Google Scholar
Adan, I., Kleiner, I., Righter, R. and Weiss, G. (2018). FCFS parallel service systems and matching models. Performance Evaluation 127, 253–272.CrossRefGoogle Scholar
Adan, I. and Weiss, G. (2012). Exact FCFS matching rates for two infinite multi-type sequences. Operat. Res. 60, 475–489.10.1287/opre.1110.1027CrossRefGoogle Scholar
Berge, C. (1989). Hypergraphs: Combinatorics of Finite Sets, 3rd edn. North-Holland, Amsterdam.Google Scholar
Boxma, O., David, I., Perry, D. and Stadje, W. (2011). A new look at organ transplantation models and double matching queues. Prob. Eng. Inf. Sci. 25, 135–155.10.1017/S0269964810000318CrossRefGoogle Scholar
Brémaud, P. (1999). Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, New York.CrossRefGoogle Scholar
Büke, B. and Chen, H. (2015). Stabilizing policies for probabilistic matching systems. Queueing Systems 80, 35–69.CrossRefGoogle Scholar
Büke, B. and Chen, H. (2017). Fluid and diffusion approximations of probabilistic matching systems. Queueing Systems 86, 1–33.CrossRefGoogle Scholar
Bušić, A., Gupta, V. and Mairesse, J. (2013). Stability of the bipartite matching model. Adv. Appl. Prob. 45, 351–378.CrossRefGoogle Scholar
Bušić, A. and Meyn, S. (2014). Approximate optimality with bounded regret in dynamic matching models. Preprint. Available at https://arxiv.org/abs/1411.1044.Google Scholar
Caldentey, R., Kaplan, E. H., and Weiss, G. (2009). FCFS infinite bipartite matching of servers and customers. Adv. Appl. Prob. 41, 695–730.CrossRefGoogle Scholar
Fayolle, G., Malyshev, V. A. and Menshikov, M. (1995). Topics in the Constructive Theory of Countable Markov Chains. Cambridge University Press.CrossRefGoogle Scholar
Gurvich, I. and Ward, A. (2014). On the dynamic control of matching queues. Stoch. Systems 4, 1–45.Google Scholar
Hall, P. (1935). On representatives of subsets. J. London Math. Soc. 10, 26–30.CrossRefGoogle Scholar
Haxell, P. E. (1995). A condition for matchability in hypergraphs. Graphs Combin. 11, 245–248.CrossRefGoogle Scholar
Mairesse, J. and Moyal, P. (2016). Stability of the stochastc matching model. J. Appl. Prob. 53, 1064–1077.CrossRefGoogle Scholar
Moyal, P., Bušić, A. and Mairesse, J. (2018). Loynes construction for the extended bipartite matching. Preprint. Available at https://arxiv.org/abs/1803.02788.Google Scholar
Moyal, P., Bušić, A. and Mairesse, J. (2021). A product form for the general stochastic matching model. J. Appl. Prob. 58, 449–468.CrossRefGoogle Scholar
Moyal, P. and Perry, O. (2017). On the instability of matching queues. Ann. Appl. Prob. 27, 3385–3434.CrossRefGoogle Scholar
Nazari, M. and Stolyar, A. L. (2018). Reward maximization in general dynamic matching systems. Queueing Systems 91, 143–170.CrossRefGoogle Scholar
Özkan, E. and Ward, A. (2020). Dynamic matching for real-time ridesharing. Stoch. Systems 10, 29–70.CrossRefGoogle Scholar
Talreja, R. and Whitt, W. (2008). Fluid models for overloaded multiclass many-server queueing systems with first-come, first-served routing. Manag. Sci. 54, 1513–1527.CrossRefGoogle Scholar