Transient Little’s Law for the First and Second Moments of G/M/1/N Queue Measures

ABSTRACT

A customer in a service system and an outside observer (manager or designer of the system) estimate the system performance differently. Unlike the outside observer, the customer can never find himself in an empty system. Therefore, the sets of scenarios, relevant for the two at a given time, differ. So differ the meanings and values of the performance measures of the queue: expected queue length and expected remaining waiting time (workload). The difference between the two viewpoints can be even more significant when steady-state values of the queue measures are reached slowly, or even are never reached. In this paper, we obtain the relations between the means and variances of the measures in transient time and in steady state for a capacitated FCFS queue with exponentially distributed service time. In particular, a formula similar to Little’s law is derived for the means of the queue measures. Several examples support the validity and significance of the results.

A customer in a service system and an outside observer (manager or designer of the system) estimate the system performance differently. Unlike the outside observer, the customer can never find himself in an empty system. Therefore, the sets of scenarios, relevant for the two at a given time, differ. So differ the meanings and values of the performance measures of the queue: expected queue length and expected remaining waiting time (workload). The difference between the two viewpoints can be even more significant when steady-state values of the queue measures are reached slowly, or even are never reached. In this paper, we obtain the relations between the means and variances of the measures in transient time and in steady state for a capacitated FCFS queue with exponentially distributed service time. In particular, a formula similar to Little’s law is derived for the means of the queue measures. Several examples support the validity and significance of the results.

Cite this paper

nullA. Herbon and E. Khmelnitsky, "Transient Little’s Law for the First and Second Moments of G/M/1/N Queue Measures,"*Journal of Service Science and Management*, Vol. 3 No. 4, 2010, pp. 512-519. doi: 10.4236/jssm.2010.34058.

nullA. Herbon and E. Khmelnitsky, "Transient Little’s Law for the First and Second Moments of G/M/1/N Queue Measures,"

References

[1] J. D. C. Little, “A Proof for The Queuing Formula,” Operations Research, Vol. 9, No. 3, 1961, pp. 383-387.

[2] S. Eilon, “A Simpler Proof of ,” Operations Research, Vol. 17, No. 5, 1969, pp. 915-917.

[3] W. Maxwell, “On the Generality of the Equation ”, Operations Research, Vol. 18, No. 1, 1970, pp. 172-174.

[4] S. J. Stidham, “A Last Word on ,” Operations Research, Vol. 22, No. 2, 1974, pp. 417-421.

[5] J. Keilson and L. D. Servi, “The Distributional Form of Little’s Law”, Operations Research Letters, Vol. 9, No. 4, 1990, pp. 239-247.

[6] S. L. Brumelle, “On the Relation between Customer and Time Averages in Queues,” Journal of Applied Pro- bability, Vol. 8, No. 3, 1971, pp. 508-520.

[7] S. L. Brumelle, “A Generalization of to Mom- ents of Queue Length and Waiting Times,” Operations Research, Vol. 20, No. 6, 1972, pp. 1127-1136.

[8] D. P. Heyman and S. Stidham, “The Relation between Customer and Time Averages in Queues,” Operations Research, Vol. 28, No. 4, 1980, pp. 983-994.

[9] R. Haji and G. F. Newell, “A Relation between Stationary Queue and Waiting-Time Distributions,” Journal of Applied Probability, Vol. 8, No. 3, 1971, pp. 617-620.

[10] T. Rolski and S. Stidham, “Continuous Versions of the Queuing Formulas and ,” Operations Research Letters, Vol. 2, No. 5, 1983, pp. 211-215.

[11] P. W. Glynn and W. Whitt, “Extensions of the Queuing Relations and ,” Operations Research, Vol. 37, No. 4, 1989, pp. 634-644.

[12] W. Whitt, “A Review of and Extensions,” Queueing Systems, Vol. 9, No. 3, 1991, pp. 235-268.

[13] D. Bertsimas and G. Mourtzinou, “Transient Laws of Non-Stationary Queueing Systems and Their Applicati- ons,” Queueing Systems, Vol. 25, No. 1-4, 1997, pp. 115-155.

[14] G. Ria?o, R. Serfozo and S. Hackman, “A Transient Little’s Law,” Technical report, 2003, COPA Centro de Optimización y Probabilidad Aplicada, Universidad de los Andes and Georgia Institute of Technology.

[15] J. I. Zhang, “The Transient Solution of Time-Dependent M/M/1 Queues,” IEEE Transactions on Information Theory, Vol. 37, No. 6, 1991, pp. 1690-1696.

[16] D. Perry, W. Stadje and S. Zacks, “The M/G/1 Queue wi- th Finite Workload Capacity,” Queueing Systems, Vol. 39, No. 1, 2001, pp. 7-22.

[17] J. -M. Garcia, O. Brun and D. Gauchard, “Transient Analytical Solution of M/D/1/N Queues,” Journal of Applied Probability, Vol. 39, No. 4, 2002, pp. 853- 864.

[18] J. W. Cohen, “The Single Server Queue,” North-Holland, Amsterdam, 1982.

[19] S. Asmussen, “Applied Probability and Queues,” 2nd ed. Springer, Berlin, 2003.

[20] I. Adan, O. Boxma and D. Perry, “The Queue Revisited,” Mathematical Methods of Operations Resea- rch, Vol. 62, No. 3, 2005, pp. 437-452.

[1] J. D. C. Little, “A Proof for The Queuing Formula,” Operations Research, Vol. 9, No. 3, 1961, pp. 383-387.

[2] S. Eilon, “A Simpler Proof of ,” Operations Research, Vol. 17, No. 5, 1969, pp. 915-917.

[3] W. Maxwell, “On the Generality of the Equation ”, Operations Research, Vol. 18, No. 1, 1970, pp. 172-174.

[4] S. J. Stidham, “A Last Word on ,” Operations Research, Vol. 22, No. 2, 1974, pp. 417-421.

[5] J. Keilson and L. D. Servi, “The Distributional Form of Little’s Law”, Operations Research Letters, Vol. 9, No. 4, 1990, pp. 239-247.

[6] S. L. Brumelle, “On the Relation between Customer and Time Averages in Queues,” Journal of Applied Pro- bability, Vol. 8, No. 3, 1971, pp. 508-520.

[7] S. L. Brumelle, “A Generalization of to Mom- ents of Queue Length and Waiting Times,” Operations Research, Vol. 20, No. 6, 1972, pp. 1127-1136.

[8] D. P. Heyman and S. Stidham, “The Relation between Customer and Time Averages in Queues,” Operations Research, Vol. 28, No. 4, 1980, pp. 983-994.

[9] R. Haji and G. F. Newell, “A Relation between Stationary Queue and Waiting-Time Distributions,” Journal of Applied Probability, Vol. 8, No. 3, 1971, pp. 617-620.

[10] T. Rolski and S. Stidham, “Continuous Versions of the Queuing Formulas and ,” Operations Research Letters, Vol. 2, No. 5, 1983, pp. 211-215.

[11] P. W. Glynn and W. Whitt, “Extensions of the Queuing Relations and ,” Operations Research, Vol. 37, No. 4, 1989, pp. 634-644.

[12] W. Whitt, “A Review of and Extensions,” Queueing Systems, Vol. 9, No. 3, 1991, pp. 235-268.

[13] D. Bertsimas and G. Mourtzinou, “Transient Laws of Non-Stationary Queueing Systems and Their Applicati- ons,” Queueing Systems, Vol. 25, No. 1-4, 1997, pp. 115-155.

[14] G. Ria?o, R. Serfozo and S. Hackman, “A Transient Little’s Law,” Technical report, 2003, COPA Centro de Optimización y Probabilidad Aplicada, Universidad de los Andes and Georgia Institute of Technology.

[15] J. I. Zhang, “The Transient Solution of Time-Dependent M/M/1 Queues,” IEEE Transactions on Information Theory, Vol. 37, No. 6, 1991, pp. 1690-1696.

[16] D. Perry, W. Stadje and S. Zacks, “The M/G/1 Queue wi- th Finite Workload Capacity,” Queueing Systems, Vol. 39, No. 1, 2001, pp. 7-22.

[17] J. -M. Garcia, O. Brun and D. Gauchard, “Transient Analytical Solution of M/D/1/N Queues,” Journal of Applied Probability, Vol. 39, No. 4, 2002, pp. 853- 864.

[18] J. W. Cohen, “The Single Server Queue,” North-Holland, Amsterdam, 1982.

[19] S. Asmussen, “Applied Probability and Queues,” 2nd ed. Springer, Berlin, 2003.

[20] I. Adan, O. Boxma and D. Perry, “The Queue Revisited,” Mathematical Methods of Operations Resea- rch, Vol. 62, No. 3, 2005, pp. 437-452.