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

Authors: Yichuan Ding, S.T. McCormick and M. Nagarajan

Publication: Operations Research, Forthcoming

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.

Desautels 22

In recognition of research excellence as it relates to publications in top-tier management journals, our Faculty has compiled a list of high quality, peer-reviewed management journals, which is referred to as the Desautels 22.