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

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.