Preemptible queues with advance reservations: Strategic behavior and revenue management

Consider an M/G/1 queuing system that supports advance reservations. In this system, strategic customers must decide whether to reserve a server in advance (thereby gaining higher priority) or forgo reservations. Reserving a server in advance bears a cost. The provider can further impact the customers' reservation decisions via implementation of one of several priority-based preemption policies: (i) one in which any customer is subject to service preemption by a higher priority customer (PR); (ii) one in which service preemption does not occur (NP); and (iii) a hybrid policy in which only customers without a priority reservation are subject to service preemption (HPR). In this work, we characterize the strategic behavior of customers, equilibrium outcomes, and provider's revenue maximization under each of these policies. In all the cases, we prove that (i) the only possible type of Nash equilibria is a threshold one based on the customers' priorities; and (ii) the system load impacts both the structure and number of Nash equilibria. We also prove that HPR is the only policy in which (i) an equilibrium where all customers make reservations may exist; and (ii) the second moment of service impacts the equilibria. Finally, we prove that for any system load and any service distribution, the HPR policy yields the highest maximum revenue, followed in turn by the PR policy and the NP policy. We further show that the relative difference in the performance of the HPR and PR policies is greatest at low system load and under low service variance. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

For an M/G/1 queuing system with advance reservations, customers can strategically decide whether to reserve a server in advance and choose from different priority-based preemption policies. Analysis shows that only the HPR policy can have an equilibrium where all customers make reservations, and the system load and service distribution affect the Nash equilibria.