On the Optimal Design of a Bipartite Matching Queueing System

We consider a multiclass multiserver queueing system and study the problem of designing an optimal matching topology (or service compatibility structure) between customer classes and servers under a first come first served—assign longest idle server (FCFS-ALIS) service discipline. Specifically, we are interested in finding matching topologies that optimize—in a Pareto efficiency sense—the trade-off between two competing objectives: (i) minimizing customers’ waiting time delays and (ii) maximizing matching rewards generated by pairing customers and servers. Our analysis of the problem is divided into three main parts.First, under heavy-traffic conditions, we show that any bipartite matching system can be partitioned into a collection of complete resource pooling (CRP) subsystems, which are interconnected by means of a direct acyclic graph (DAG). We show that this, together with the aggregate service capacity on each CRP, fully determines the vector of steady-state waiting times. In particular, we show that the average (scaled) steady-state delay across all customer classes is asymptotically equal to the number of CRP components divided by the total system capacity.Second, since computing matching rewards under a FCFS-ALIS service discipline is computationally infeasible as the number of customer classes and servers grow large, we propose a quadratic programming (QP) formulation to approximate matching rewards. We show that the QP formulation is exact for a number of instances of the problem and provides a very good approximation in general. Extensive numerical experiments show that in over 98% of problem instances the relative error between the exact rewards and the QP approximate rewards is less than 2%.Lastly, combining our characterization of average delays in terms of the number of CRP components and the QP formulation to compute matching rewards, we propose a mixed-integer linear program that can be used to find the set of matching topologies that define the Pareto frontier of reward-delay pairs.