An order-based method for robust queue inference with stochastic arrival and departure times

摘要

The internal structure and parameters of a queue are completely unobservable in some military and competitive commercial applications. Furthermore, arrival and departure times may be observable but subject to substantial uncertainty due to measurement error in an adversarial environment. This analysis estimates the number of servers in an internally unobservable, first-come, first-served GI/G/c queue using a novel, order-based approach. This new approach provides a lower bound and converges in probability to the correct value. Compared to the standard variance minimization method, the order-based approach has improved performance for small samples. The order-based method is robust to noise in arrival and departure time measurements, while the variance minimization approach exhibits poor performance with noisy data. An extension to last-come, first-served GI/G/c queues is also considered. The last-come, first-served order-based approach also provides a lower bound that converges in probability to the correct value. The empirical performance of the last-come, first-served order based approach is statistically similar to the performance of the last-come, first-served variance minimization approach with respect to the number of observations required for approximate convergence.