Designing Service Menus for Bipartite Queueing Systems

We consider a multiclass, multiserver queueing system, in which 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. A service class corresponds to a single queue served by a subset of servers under a first come, first served–assign longest idle server service discipline. 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 and a disutility based on the mean steady-state waiting time of the service class they join. We study the problem under (conventional) heavy-traffic conditions: that is, in the limit as the traffic intensity of the system approaches one from below. For the case of two servers, we provide a complete characterization of the possible menus and their delay-reward trade-offs. For a 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 formulations for optimizing the delay-reward trade-off within fairly rich and practically relevant families of menus, which we term partitioned and tailored .