Designing Service Menus for Bipartite Queueing Systems

• 成果类型: Article
• 署名作者: Caldentey, Rene; Hillas, Lisa Aoki; Gupta, Varun
• 署名单位: University of Chicago; University of Auckland; Northwestern University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0179
• 发表日期: 2025
• 关键词: multiclass queueing system; first come; first served; bipartite matching; steady-state analysis

摘要

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 delayreward 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.