Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-01-09T14:40:49.352Z Has data issue: false hasContentIssue false
  • English
  • Français

THE OPTIMAL ADMISSION THRESHOLD IN OBSERVABLE QUEUES WITH STATE DEPENDENT PRICING

Published online by Cambridge University Press:  13 December 2013

Christian Borgs ,
Jennifer T. Chayes ,
Sherwin Doroudi ,
Mor Harchol-Balter  and
Kuang Xu
Christian Borgs
Affiliation:
Microsoft Research, Cambridge, MA. E-mail: [email protected], [email protected]
Jennifer T. Chayes
Affiliation:
Microsoft Research, Cambridge, MA. E-mail: [email protected], [email protected]
Sherwin Doroudi
Affiliation:
Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA E-mail: [email protected]
Mor Harchol-Balter
Affiliation:
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA E-mail: [email protected]
Kuang Xu
Affiliation:
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the social welfare model of Naor [20] and revenue-maximization model of Chen and Frank [7], where a single class of delay-sensitive customers seek service from a server with an observable queue, under state dependent pricing. It is known that in this setting both revenue and social welfare can be maximized by a threshold policy, whereby customers are barred from entry once the queue length reaches a certain threshold. However, no explicit expression for this threshold has been found. This paper presents the first derivation of the optimal threshold in closed form, and a surprisingly simple formula for the (maximum) revenue under this optimal threshold. Utilizing properties of the Lambert W function, we also provide explicit scaling results of the optimal threshold as the customer valuation grows. Finally, we present a generalization of our results, allowing for settings with multiple servers.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 28 , Issue 1 , January 2014 , pp. 101 - 119
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

1.Afèche, P. (2010). Incentive-compatible revenue management in queueing systems: optimal strategic delay and capacity, Working paper, University of Toronto.Google Scholar
2.Alperstein, H. (1988). Optimal pricing policy for the service facility offering a set of priority prices. Management Science 34(5): 666–671.Google Scholar
3.Balachandran, K.R. (1972). Purchasing priorities in queues. Management Science 18(5): Part 1, 319–326.Google Scholar
4.Borgs, C., Chayes, J.T., Doroudi, S., Harchol-Balter, M. & Xu, K. (2012). The optimal admission threshold in observable queues with state dependent pricing. Technical report, CMU-CS-12-145. School of Computer Science, Carnegie Mellon University.Google Scholar
5.Borgs, C., Chayes, J.T., Doroudi, S., Harchol-Balter, M. & Xu, K. (2012). Pricing and queueing. ACM SIGMETRICS Performance Evaluation Review 40(3): 71–73.Google Scholar
6.Burnetas, A. & Economou, A. (2007). Equilibrium customer strategies in a single server Markovian queue with setup times. Queueing Systems 56(3): 213–228.Google Scholar
7.Chen, H. & Frank, M.Z. (2001). State dependent pricing with a queue. IIE Transactions 33(10): 847–860.Google Scholar
8.Corless, R.M., Gonnet, G.H., Hare, D.E.G., Jeffrey, D.J. & Knuth, D.E. (1996) On the Lambert W function. Advances in Computational Mathematics 5(1): 329–359.Google Scholar
9.Economou, A., Gómez-Corral, A. & Kanta, S. (2011). Optimal balking strategies in single-server queues with general service and vacation times. Performance Evaluation 68(10): 967–982.Google Scholar
10.Economou, A. & Kanta, S. (2008). Equilibrium balking strategies in the observable single-server queue with breakdowns and repairs. Operations Research Letters 36(6): 696–699.Google Scholar
11.Economou, A. & Kanta, S. (2008). Optimal balking strategies and pricing for the single server Markovian queue with compartmented waiting space. Queueing Systems 59(3): 237–269.Google Scholar
12.Ghanem, S.B. (1975). Computing center optimization by a pricing-priority policy. IBM Systems Journal 14(3): 272–291.CrossRefGoogle Scholar
13.Guo, P. (2007). Analysis and comparison of queues with different levels of delay information. Ph.D. thesis, Duke University.Google Scholar
14.Gupta, D. & Weerawat, W. (2006). Supplier-manufacturer coordination in capacitated two-stage supply chains. European Journal of Operational Research 175(1): 67–89.Google Scholar
15.Hassin, R. & Haviv, M. (2003) To queue or not to queue: Equilibrium behavior in queueing systems. Boston: Kluwer.Google Scholar
16.Kittsteiner, T. & Moldovanu, B. (2005). Priority auctions and queue disciplines that depend on processing time. Management Science 51(2): 236–248.Google Scholar
17.Knudsen, N.C. (1972). Individual and social optimization in a multiserver queue with a general cost-benefit structure Econometrica: Journal of the Econometric Society 40: 515–528.Google Scholar
18.Libman, L. & Orda, A. (2002). Optimal retrial and timeout strategies for accessing network resources. Networking, IEEE/ACM Transactions on 10(4): 551–564.CrossRefGoogle Scholar
19.Mendelson, H. & Whang, S. (1990). Optimal incentive-compatible priority pricing for the m/m/1 queue. Operations Research 38(5): 870–883.Google Scholar
20.Naor, P. (1969). The regulation of queue size by levying tolls. Econometrica: Journal of the Econometric Society 37(1): 15–24.Google Scholar
21.Plambeck, E.L. (2004). Optimal leadtime differentiation via diffusion approximations. Operations Research 52(2): 213–228.Google Scholar
22.Yildirim, U. & Hasenbein, J.J. (2010). Admission control and pricing in a queue with batch arrivals. Operations Research Letters 38(5): 427–431.CrossRefGoogle Scholar