Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-04T20:16:44.455Z Has data issue: false hasContentIssue false
  • English
  • Français

ON THE TIME-DEPENDENT OCCUPANCY DISTRIBUTION OF THE G/G/1 QUEUING SYSTEM

Published online by Cambridge University Press:  16 February 2009

Jorge Limón–Robles  and
Martin A. Wortman
Jorge Limón–Robles
Affiliation:
Industrial and Systems Engineering, Instituto Tecnológico y de Estudios Superiores de Monterrey, C.P. 64849, Monterrey, N.L., México E-mail: [email protected]
Martin A. Wortman
Affiliation:
Department of Industrial and Systems Engineering, Texas A&M University, College Station, TX 77843–3131 E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This article offers an approach for studying the time-dependent occupancy distribution for a modest generalization of the GI/G/1 queuing system in which interarrival times and service times, although mutually independent, are not necessarily identically distributed. We develop and explore an analytical model leading to a computational approach that gives tight bounds on the occupancy distribution. Although there is no general closed-form characterization of probability law dynamics for occupancy in the GI/G/1 queue, our results offer what might be termed “near-closed-form” in that accurate plots of the transient occupancy distribution can be constructed with an insignificant computational burden. We believe that our results are unique; we are unaware of any alternative analytical approach leading to a numerical characterization of the time-dependent occupancy distribution for the G/G/1 queuing systems considered here.

Our analyses employ a marked point process that converges to the occupancy process at any fixed time t; it is shown that this process forms a Markov chain from which the transient occupancy law is available. We verify our analytical approach via comparison with the well-known closed-form expressions for time-dependent occupancy distribution of the M/M/1 queue. Additionally, we suggest the viability of our approach, as a computational means of obtaining the time-dependent occupancy distribution, through straightforward application to a Gamma[x]/Weibull/1 queuing system having batch arrivals and batch job services.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 23 , Issue 2 , April 2009 , pp. 261 - 280
Copyright
Copyright © Cambridge University Press 2009

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.Agrawala, A.K. & Tripathi, S.K. (1980). Transient solution of the virtual waiting time of a single-server queue and its applications. Information Sciences 21: 141–158.CrossRefGoogle Scholar
2.Borovkov, A. (1976). Stochastic processes in queueing theory. Berlin: Springer-Verlag.CrossRefGoogle Scholar
3.Burden, R.L. & Faires, J.D. (1993). Numerical analysis, 5th ed.Boston: PWS Publishing.Google Scholar
4.Chaudhry, M., Agarwal, M., & Templeton, J. (1992). Exact and approximate numerical solutions of steady-state distributions arising in the queue GI/G/1. Queueing Systems 10: 105–152.CrossRefGoogle Scholar
5.Choudhury, G.L., Lucantoni, D.M., & Whitt, W. (1997). Numerical solution of the piecewise-stationary M t/G t/1 queues. Operations Research 45(3): 451–463.CrossRefGoogle Scholar
6.Cohen, J. (1982). The single server queue, 2nd ed.New York: Elsevier Science Publishing.Google Scholar
7.Gross, D. & Harris, C.M. (1985). Fundamentals of queueing theory, 2nd ed.New York: Wiley.Google Scholar
8.Keilson, J. & Nunn, W. (1979). Laguerre transformation as a tool for the numerical solution of integral equations of convolution type. Applied Mathematics and Computation 5: 313–359.Google Scholar
9.Kingman, J. (1961). The single server queue in heavy traffic. Proceedings of the Cambridge Philospohical Society 57: 902–904.Google Scholar
10.Kingman, J. (1962). Some inequalities for the queue GI/G/1. Biometrika 49 (3/4): 315–324.CrossRefGoogle Scholar
11.Limón-Robles, J. (1998). On the time dependent occupancy distribution of the G/G/1 queueing system. Ph.D. dissertation, Monterrey, Mexico: Instituto Tecnológico y de Estudios Superiores de Monterrey.Google Scholar
12.Litko, J.R. (1989). GI/G/1 interdeparture time and queue-length distributions via the Laguerre transform. Queueing Systems 4: 367–382.CrossRefGoogle Scholar
13.Marchal, W.G. (1978). Some simpler bounds on the mean queueing time. Operations Research 26(6): 1083–1088.CrossRefGoogle Scholar
14.Taylor, H. & Karlin, S. (1998). Introduction to stochastic modeling, 3rd ed.San Diego, CA: Academic Press.Google Scholar
15.Whitt, W. (1993). Approximations for the GI/G/m queue. Production and Operations Management 2(2): 114–161.CrossRefGoogle Scholar
16.Yang, T. & Chaudhry, M. (1996). On steady-state queue size distributions of the discrete-time GI/G/1 queue. Advances in Applied Probability 28: 1177–1200.CrossRefGoogle Scholar