TY - GEN
T1 - Performance Evaluation of Stochastic Bipartite Matching Models
AU - Comte, Céline
AU - Dorsman, Jan-Pieter L.
PY - 2021
Y1 - 2021
N2 - We consider a stochastic bipartite matching model consisting of multi-class customers and multi-class servers. Compatibility constraints between the customer and server classes are described by a bipartite graph. Each time slot, exactly one customer and one server arrive. The incoming customer (resp. server) is matched with the earliest arrived server (resp. customer) with a class that is compatible with its own class, if there is any, in which case the matched customer-server couple immediately leaves the system; otherwise, the incoming customer (resp. server) waits in the system until it is matched. Contrary to classical queueing models, both customers and servers may have to wait, so that their roles are interchangeable. While (the process underlying) this model was already known to have a product-form stationary distribution, this paper derives a new compact and manageable expression for the normalization constant of this distribution, as well as for the waiting probability and mean waiting time of customers and servers. We also provide a numerical example and make some important observations.
AB - We consider a stochastic bipartite matching model consisting of multi-class customers and multi-class servers. Compatibility constraints between the customer and server classes are described by a bipartite graph. Each time slot, exactly one customer and one server arrive. The incoming customer (resp. server) is matched with the earliest arrived server (resp. customer) with a class that is compatible with its own class, if there is any, in which case the matched customer-server couple immediately leaves the system; otherwise, the incoming customer (resp. server) waits in the system until it is matched. Contrary to classical queueing models, both customers and servers may have to wait, so that their roles are interchangeable. While (the process underlying) this model was already known to have a product-form stationary distribution, this paper derives a new compact and manageable expression for the normalization constant of this distribution, as well as for the waiting probability and mean waiting time of customers and servers. We also provide a numerical example and make some important observations.
KW - Bipartite matching models
KW - Order-independent queues
KW - Performance analysis
KW - Product-form stationary distribution
UR - https://www.scopus.com/pages/publications/85121917639
U2 - 10.1007/978-3-030-91825-5_26
DO - 10.1007/978-3-030-91825-5_26
M3 - Conference contribution
SN - 9783030918248
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 425
EP - 440
BT - Performance Engineering and Stochastic Modeling - 17th European Workshop, EPEW 2021, and 26th International Conference, ASMTA 2021, Proceedings
A2 - Ballarini, Paolo
A2 - Castel, Hind
A2 - Dimitriou, Ioannis
A2 - Iacono, Mauro
A2 - Phung-Duc, Tuan
A2 - Walraevens, Joris
ER -