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

• 成果类型: Article
• 署名作者: Ding, Yichuan; McCormick, S. Thomas; Nagarajan, Mahesh
• 署名单位: McGill University; University of British Columbia
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.2015
• 发表日期: 2021
• 页码: 1256-1281
• 关键词: convex delay costs; scheduling flexible servers; multiserver pools; Service Systems; priority queue; allocation; time; ABANDONMENT; 1st-come

摘要

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.