A Fluid Model for One-Sided Bipartite Matching Queues with Match-Dependent Rewards

Yichuan Ding (), S. Thomas McCormick () and Mahesh Nagarajan ()
Additional contact information
Yichuan Ding: Desautels Faculty of Management, McGill University, Montreal, Quebec V3A 1G5, Canada
S. Thomas McCormick: Sauder School of Business, University of British Columbia, Vancouver, British Columbia V6T 1Z2, Canada
Mahesh Nagarajan: Sauder School of Business, University of British Columbia, Vancouver, British Columbia V6T 1Z2, Canada

Operations Research, 2021, vol. 69, issue 4, 1256-1281

Abstract: We consider a one-sided bipartite matching queueing system (OBMQ) with customers and resources of multiple types, where different customer-resource combinations can generate different rewards. Each resource is allocated on arrival to the customer with the highest score (or index), which is the sum of the customer’s waiting score and matching score, so we call it an M+W index. We assume that the waiting score is an increasing function of a customer’s waiting time and that the matching score is a function of both the customer’s and the resource’s types. Unmatched customers wait in the queue until being matched or will abandon the waitlist after a random duration. We study the fluid sample path in such a system, which provides an approximate to the system dynamics. We show that a fluid sample path can be computed over any finite horizon. We propose an efficient algorithm to check whether a steady state of the fluid sample path exists or not. When a steady state exists, the algorithm also computes one efficiently. We prove that there can be at most one steady state and that the fluid sample path will be attracted to the unique steady state under mild conditions. These results enable a policy designer to predict the behavior of an OBMQ when using an M+W index and to choose an indexing formula that optimizes a given set of performance metrics. We derive a closed-form index that optimizes the steady-state performance according to some well-known efficiency and fairness metrics.

Keywords: queues: priority; network: flow algorithms; network: matching; Stochastic Models; min cost max flow; nested cuts for parameterized network; fluid sample path; value-based routing; kidney allocation; parallel server system (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2015 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:4:p:1256-1281

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().