When does Partial Priority Improve Revenue?

Zhouzi Li, Mor Harchol-Balter, Alan Scheller-Wolf

Abstract: Priority queues have long been used to increase revenue by exploiting the fact that time-sensitive customers are willing to pay for shorter waiting times. This fact begs the question: Can one make even more revenue by relaxing the strictness of the priority policy? This paper answers this question under the unobservable queue setting, where customers are heterogeneous in their time-sensitivity; specifically the time-sensitivity of customers is allowed to follow an arbitrary distribution.

In this paper we prove necessary and sufficient conditions under which partial priority can increase the revenue. Specifically, we find a surprising result: Although partial priority offers much more flexibility than strict priority, partial priority only increases revenue if there are two additional constraints on the service provider, one setting a maximum price and the other setting a maximum waiting time. In the absence of either of these constraints, we prove that strict priority maximizes revenue. Finally, in situations where partial priority increases the revenue, we analytically characterize the amount of improvement.