Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-03T04:06:53.418Z Has data issue: false hasContentIssue false
  • English
  • Français

Queues with advanced reservations: an infinite-server proxy for the bookings diary

Part of: Computer system organization Special processes Operations research and management science

Published online by Cambridge University Press:  24 March 2016

R. J. Maillardet  and
P. G. Taylor
R. J. Maillardet*
Affiliation:
University of Melbourne
P. G. Taylor*
Affiliation:
University of Melbourne
*
* Postal address: Department of Mathematics and Statistics, University of Melbourne, Melbourne, VIC 3010, Australia.
* Postal address: Department of Mathematics and Statistics, University of Melbourne, Melbourne, VIC 3010, Australia.
Get access Rights & Permissions [Opens in a new window]

Abstract

Queues with advanced reservations are endemic in the real world. In such a queue, the 'arrival' process is an incoming stream of customer 'booking requests', rather than actual customers requiring immediate service. We consider a model with a Poisson booking request process with rate λ. Associated with each request is a pair of independent random variables (Ri, Si) constituting a request for service over a period Si, starting at a time Ri into the future. Our interest is in the probability that a customer will be rejected due to capacity constraints. We present a simulation of a finite-capacity queue in which we record the proportion of rejected customers, and then move to an analysis of a queue with infinitely-many servers. Obviously no customers are rejected in the latter case. However, the event that the arrival of the extra customer will cause the number of customers in the queue to exceed C at some point during its service can be used as a proxy for the event that the customer would have been rejected in a system with finite capacity C. We start by calculating the transient and stationary distributions for some performance measures for the infinite-server queue. By observing that the stationary measure for the bookings diary (that is, the list of customers currently on hand, together with their start times and service times) is the same as the law for the entire sample path of an infinite server queue with a specified nonhomogenous Poisson input process, which we call the bookings queue, we are able to write down expressions for the abovementioned probability that, at some time during a requested service, the number of customers exceeds C. This measure serves as a bound for the probability that an incoming arrival would be refused admission in a system with C servers and, for a well-dimensioned system, it is to be hoped that it is a good approximation. We test the quality of this approximation by comparing our analytical results for the infinite-server case against simulation results for the finite-server case.

Keywords

Advanced reservationsinfinite-server queueblocking probability

MSC classification

Primary: 60K25: Queueing theory
Secondary: 68M20: Performance evaluation; queueing; scheduling 90B22: Queues and service
Type
Research Article
Information
Advances in Applied Probability , Volume 48 , Issue 1 , March 2016 , pp. 13 - 31
Copyright
Copyright © Applied Probability Trust 2016 

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

[1]Abate, J. and Whitt, W. (1995). Numerical inversion of Laplace transforms of probability distributions. ORSA J. Comput. 7, 36–43. Google Scholar
[2]Abate, J. and Whitt, W. (1998). Calculating transient characteristics of the Erlang loss model by numerical transform inversion. Commun. Statist. Stoch. Models 14, 663–680. Google Scholar
[3]Barakat, N. and Sargent, E. H. (2004). An accurate model for evaluating blocking probabilities in multi-class OBS systems. IEEE Commun. Lett. 8, 119–121. Google Scholar
[4]Barakat, N. and Sargent, E. H. (2005). Analytical modelling of offset-induced priority in multiclass OBS networks. IEEE Trans. Commun. 53, 1343–1352. Google Scholar
[5]Borovkov, K. (2003). Elements of Stochastic Modelling. World Scientific, River Edge, NJ. Google Scholar
[6]Chihara, T. S. (1978). An Introduction to Orthogonal Polynomials. Gordon and Breach, New York. Google Scholar
[7]Coffman, E. G. Jr., Flatto, L. and Jelenković, P. (2000). Interval packing: the vacant interval distribution. Ann. Appl. Prob. 10, 240–257. CrossRefGoogle Scholar
[8]Coffman, E. G. Jr., Jelenković, P. and Poonen, B. (1999). Reservation probabilities. Adv. Performance Anal. 2, 129–158. Google Scholar
[9]Coffman, E. G. Jr., Flatto, L., Jelenković, P. and Poonen, B. (1998). Packing random intervals on-line. Algorithmica 22, 448–476. CrossRefGoogle Scholar
[10]Daley, D. J. and Vere-Jones, D. (2003). An Introduction to the Theory of Point Processes, Vol. 1, Elementary Theory and Methods. Springer, New York. Google Scholar
[11]Dolzer, K. and Gauger, C. (2001). On burst assembly in optical burst switching networks—a performance evaluation of just-enough-time. In Proceedings of the 17th International Teletraffic Congress, pp. 149–160. Google Scholar
[12]Foley, R. D. (1982). The nonhomogeneous M/G/∞ queue. Opsearch 19, 40–48. Google Scholar
[13]Greenberg, A. G., Srikant, R. and Whitt, W. (1999). Resource sharing for book-ahead and instantaneous-request calls. IEEE/ACM Trans. Networking 7, 10–22. CrossRefGoogle Scholar
[14]Kaheel, A., Alnuweiri, H. and Gebali, F. (2004). Analytical evaluation of blocking probability in optical burst switching networks. In Proc. IEEE Internat. Conf. Commun., Vol. 3, pp. 1548–1553. Google Scholar
[15]Kaheel, A. M., Alnuweiri, H. and Gebali, F. (2006). A new analytical model for computing blocking probability in optical burst switching networks. IEEE J. Selected Areas Commun. 24, 120–128. CrossRefGoogle Scholar
[16]Levi, R. and Shi, C. (2014). Revenue management of reusable resources with advanced reservations. Submitted. Google Scholar
[17]Liang, Y., Liao, K., Roberts, J. W. and Simonian, A. (1988). Queueing models for reserved set up telecommunications services. In Proc. Teletraffic Science for New Cost-Effective Systems, Networks and Services, Session 4.4B, 1.1–1.7. Google Scholar
[18]Ramakrishnan, M., Sier, D. and Taylor, P. G. (2005). A two-time-scale model for hospital patient flow. IMA J. Manag. Math. 16, 197–215. Google Scholar
[19]Riordan, J. (1962). Stochastic Service Systems. John Wiley, New York. Google Scholar
[20]Takács, L. (1962). Introduction to the Theory of Queues. Oxford University Press. Google Scholar
[21]Van de Vrugt, M., Litvak, N. and Boucherie, R. J. (2014). Blocking probabilities in Erlang loss queues with advance reservation. Stoch. Models 30, 187–196. CrossRefGoogle Scholar
[22]Virtamo, J. T. (1992). A model of reservation systems. IEEE Trans. Commun. 40, 109–118. Google Scholar
[23]Vu, H. L. and Zukerman, M. (2002). Blocking probability for priority classes in optical burst switching networks. IEEE Commun. Lett. 6, 214–216. Google Scholar
[24]Wolff, R. W. (1989). Stochastic Modeling and the Theory of Queues. Prentice-Hall, Englewood Cliffs, NJ. Google Scholar