Data-Driven Fitting of the G/G/1 Queue

Abstract

The Maximum Likelihood Estimation (MLE) method is an established statistical method to estimate unknown parameters of a distribution. A disadvantage of the MLE method is that it requires an analytically tractable density, which is not available in many cases. This is the case, for example, with applications in service systems, since waiting models from queueing theory typically have no closed-form solution for the underlying density. This problem is addressed in this paper. MLE is used in combination with Stochastic Approximation (SA) to calibrate the arrival parameter θ of a G/G/1 queue via waiting time data. Three different numerical examples illustrate the application of the proposed estimator. Data sets of an M/G/1 queue, G/M/1 queue and model mismatch are considered. In a model mismatch, a mismatch is present between the used data and the postulated queuing model. The results indicate that the estimator is versatile and can be applied in many different scenarios.

Keywords

G/G/1 queue / maximum likelihood estimation / stochastic approximation / data-driven fitting

References

[1] Armero C. Bayesian inference in Markovian queues. Queueing Systems, 1994, 15: 419-426.

[2] Asmussen S. Applied Probability and Queues(2ed), 2003, New York: Springer.

[3] Basawa I V, Narayan Bhat U, Lund R. Maximum likelihood estimation for single server queues from waiting time data. Queueing Systems, 1996, 24: 155-167.

[4] Bingham N H, Pitts S M. Nonparametric inference from M/G/1 busy periods. Stochastic Models, 1999, 15(2): 247-272.

[5] Clarke A. Maximum likelihood estimates in a simple queue. The Annals of Mathematical Statistics, 1957, 28(4): 1036-1040.

[6] Hall R W. Queuing Methods: For Services and Manufacturing, 1991, Englewood Cliffs: Prentice Hall.

[7] Kannan K S J A. Parameter estimation of single server queue with working vacations. Research & Reviews: Journal of Statistics, 2014, 2: 94-98.

[8] Millar R. Maximum Likelihood Estimation and Inference, 2011, Chichester: Wiley.

[9] Mukherjee S P, Chowdhury S. Maximum likelihood and Bayes estimation in M/M/1 queue. Stochastic Modeling and Applications, 2005, 8: 47-55.

[10] Peng Y, Fu M, Heidergott B, Lam H (2019). Maximum likelihood estimation by Monte Carlo simulation: Towards data-driven stochastic modeling. Operations Research, submitted in revision.

[11] Peng Y, Fu M, Hu JQ, Heidergott B. A new unbiased stochastic derivative estimator for discontinuous sample performances with structural parameters. Operations Research, 2018, 66: 487-499.

[12] Pflug G. Optimization of Stochastic Models: The Interface between Simulation and Optimization, 1996, Boston: Kluwer.

[13] Rubinstein R, Melamed B. Modern Simulation and Modelling, 1998, New York: Wiley.

[14] Rubinstein R, Shapiro A. Discrete Event Systems: Sensitivity Analysis and Optimization by the Score Function Method, 1993, Chichester: Wiley.

[15] Seghal V K, Agrawal P K. Bayesian predictions in M/G/1 queuing system. International Journal of Applied Engineering Research, 2014, 9(11): 1325-1330.

[16] Simar L. Maximum likelihood estimation of a compound Poisson process. The Annals of Statistics, 1976, 4(6): 1200-1209.

[17] Wang T, Ke J, Wang K, Ho S. Maximum likelihood estimates and confidence intervals of an M/M/R queue with heterogeneous servers. Mathematical Methods of Operations Research, 2006, 63: 371-384.

[18] Wang W, Casale G, Kattepur A, Nambiar M (2016). Maximum likelihood estimation of closed queueing network demands from queue length data. Proceedings of the 7th ACM/SPEC International Conference on Performance Engineering. Delft, The Netherlands, March 12–18, 2016.