Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-02-05T23:11:43.319Z 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: borgs@microsoft.com, jchayes@microsoft.com
Jennifer T. Chayes
Affiliation:
Microsoft Research, Cambridge, MA. E-mail: borgs@microsoft.com, jchayes@microsoft.com
Sherwin Doroudi
Affiliation:
Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA E-mail: sdoroudi@andrew.cmu.edu
Mor Harchol-Balter
Affiliation:
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA E-mail: harchol@cs.cmu.edu
Kuang Xu
Affiliation:
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA E-mail: kuangxu@mit.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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