Group for Research in Decision Analysis

A fluid model for one-sided bipartite matching queues with match-dependent rewards

Yichuan Daniel Ding McGill University, Canada

Yichuan Daniel Ding

We consider a queueing system with multitype customers and resources, where different customer-resource combinations can generate different rewards. Each resource is allocated upon arrival to the customer with the highest sum of the customer's waiting index and matching index. We assume that the waiting index is an increasing function of a customer's waiting time and the matching index depends on both the customer's and the server's types. Unmatched customers will wait in the queue till being matched, or abandon the queue after a random duration. We show that the fluid sample path can be computed over any finite horizon. We develop 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 converges to the 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 M+W index that optimizes the steady-state performance according to some well-known efficiency and fairness metrics. The paper is currently under minor revision of Operations Research.

Click here to view the presentation.


Free entrance.
Welcome to everyone!