Optimal pricing that coordinates queues with customer-chosen service requirements

This article considers the problem of coordinating the admission rates and service requirements of a multiclass queue when these decisions are made on a decentralized basis. The customer classes are characterized by different demand patterns, delay costs, and service costs. Customers make individual decisions on whether to join the queue and, if so, their service requirements. Their class identities and service requirements are private information not known to the system manager. We develop a two-stage decision framework to analyze the problem and characterize the optimal admission rates and service requirements under both centralized and decentralized assumptions. We distinguish admission and service externality costs that lead to suboptimal performance under decentralized control. For a given service discipline, we derive optimal class-specific pricing schemes that can coordinate the system when only service requirements but not class identities are unobservable. When customer class identities are also unobservable, we consider two common service disciplines that offer undifferentiated service: processor sharing and first-come-first-served. Based on the general framework, for the M/G/s processor sharing queue, we show that a single variable fee (payment per unit of time in the system) can induce the optimal admission rates and service requirements for all customer classes. For the M/G/1 first-come-first-served queue, we show that a single pricing scheme that is quadratic in time in service can induce the optimal admission rates and service requirements for all customer classes. Our result demonstrates that, under suitable conditions, simple and undifferentiated pricing can coordinate complex queueing systems with heterogeneous customer classes.