Files
Abstract
This dissertation examines the performance analysis and design of multi-class multi-server bipartite queueing systems under a FCFS-ALIS service discipline. The class of queueing systems we look at have $m$ servers with exponentially distributed service times organised into $n$ service classes, where a service class is defined by the subset of servers that it is compatible with. We begin by analysing the performance of the system with fixed arrival rates into the different service classes under conventional heavy-traffic conditions, where the traffic intensity approaches one from below. Building upon the formulation and results of Afèche et al. (2021) we generalize the model by allowing the vector of arrival rates to approach the heavy-traffic limit from an arbitrary direction. We characterize the steady-state waiting times of the various service classes and demonstrate that a much wider range of waiting time outcomes is achievable when the direction of approach is generalised. Furthermore, we establish that the matching probabilities, i.e., the probabilities of different customers who join different service classes being served by different servers, do not depend on the direction along which the system approaches heavy traffic. We also investigate the design of compatibility between service classes and servers, finding that a service provider who has complete control over the matching can design a delay-minimizing menu by considering only the limiting arrival rates. When some constraints on the compatibility structure exist, the direction of convergence to heavy-traffic affects which menu minimizes delay. Additionally, we discover that the bipartite matching queueing system exhibits a form of Braess's paradox, where adding more connectivity to an existing system can lead to higher average waiting times, even when neither customers nor servers are acting strategically.
We then extend the model to allow for strategic behaviour. We assume that customers of different types have heterogeneous preferences over the many servers available. The goal of the service provider is to design a menu of service classes that balances two competing objectives: (1) maximize customers' average matching reward and (2) minimize customers' average waiting time. Customers act as rational self-interested utility maximizing agents when choosing which service class to join. In particular, they join the class that maximizes their expected ex-ante net utility, which is given by the difference between the server-dependent service reward they receive minus a disutility based on the mean steady-state waiting time of the service class they join. We study the menu design problem under conventional heavy traffic conditions. For the case of two servers, we provide a complete characterization of the possible menus and their delay-reward tradeoffs. For general number of servers, we prove that if the service provider only cares about minimizing average delay or maximizing total matching reward then very simple menus are optimal. Finally, we provide Mixed Integer Linear Programming (MILP) formulations for optimizing the delay-reward trade-off within fairly rich and practically relevant families of menus, which we term Partitioned and Tailored.