Directed FCFS infinite bipartite matching
- PDF / 716,344 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 56 Downloads / 251 Views
Directed FCFS infinite bipartite matching Gideon Weiss1 Received: 1 December 2019 / Revised: 9 November 2020 / Accepted: 11 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We consider an infinite sequence consisting of agents of several types and goods of several types, with a bipartite compatibility graph between agent and good types. Goods are matched with agents that appear earlier in the sequence using FCFS matching, if such are available, and are lost otherwise. This model may be used for two-sided queueing applications such as ride sharing, Web purchases, organ transplants, and for parallel redundant service queues. For this model, we calculate matching rates and delays. These can be used to obtain waiting times and help with design questions for related service systems. We explore some relations of this model to other FCFS stochastic matching models. Keywords Dynamic online matching · FCFS matching · Matching rates · Matching delays · Two-sided queues · Parallel service systems Mathematics Subject Classification 60K25 · 68M20 · 90B22
1 Introduction Classical queueing models have random streams of customer arrivals and fixed sets of servers. Recently, however, more and more applications are better modeled by two-sided queues, where the fixed sets of servers are replaced by streams of arriving servers. The simplest example of such a system is the taxi stand, where cabs and passengers arrive at random times and depart at the moment that they meet [10]. More general systems where two-sided models seem appropriate include ride sharing systems, organ transplants, Web postings and searches, job markets, trading and auctions. These models share a more symmetric role of the so-called customers and servers, and
Research supported in part by Israel Science Foundation Grant 286/13. Part of this work was done while the author was visiting the Simons Institute for the Theory of Computing.
B 1
Gideon Weiss [email protected] Department of Statistics, The University of Haifa, Haifa, Israel
123
Queueing Systems
in particular, in these models service durations are replaced by inter-arrival times. In the simplest taxi stand model, the symmetric version where both cabs and passengers can wait is always either transient or null-recurrent, and to be useful the model needs to include finite waiting rooms or abandonments. In particular, one may assume that cabs always wait, while passengers abandon and are lost if they do not find a cab at the stand. This seems also to be the model appropriate for ride sharing systems like Uber and Lyft [9,15,18], for transplants of perishable organs or blood transfusions [25], perishable inventory systems [14,21], trading systems [6,13,17], and models of the sharing economy [22]. Our results in this paper are relevant for the following twosided parallel service model: Agents of several types arrive to the system and wait for goods, and goods of several types arrive and match and depart with a compatible agent, or, if no match is immediately
Data Loading...
