On the Optimal Design of a Bipartite Matching Queueing System

Philipp Afèche (), René Caldentey () and Varun Gupta ()
Additional contact information
Philipp Afèche: Rotman School of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada
René Caldentey: Booth School of Business, The University of Chicago, Chicago, Illinois 60637
Varun Gupta: Booth School of Business, The University of Chicago, Chicago, Illinois 60637

Operations Research, 2022, vol. 70, issue 1, 363-401

Abstract: 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.

Keywords: Stochastic Models; multi-class queueing system; first-come-first-served; bipartite matching; steady-state analysis; flexibility design (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2027 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:1:p:363-401

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().