Title: An Overloaded Bipartite Queueing System with Scoring-Based Priority Rules

Abstract:
We consider an overloaded bipartite queueing system (OBQS) with multitype customers and service providers. In such a system, a service provider assigns each customer a score based on customer type, duration of waiting time, and server type. Service is then provided first to the customer with the highest score. We approximate the behavior of such a system using a fluid limit process, which has two important features: (1) the routing flow rates at a transient state coincide with the maximal flow in a parameterized network and can be efficiently computed based on a nested-cut structure using a so-called GGT algorithm; (2) the routing flow rates at the steady state coincide with the minimal-cost maximal-flow in a capacitated network. Given these properties, we can efficiently characterize the unique fluid limit process. This result has three immediate applications: (1) it predicts the outcome of an OBQS equipped with a scoring-based routing policy; (2) it sheds insight into designing a score formula with a given set of objectives; and (3) by applying the result to the special case when the OBQS is FCFS, we make new progress in addressing the open question raised by Talreja and Whitt (2008).