Inferring most likely queue length from transactional data

This paper presents an efficient algorithm for inferring a most likely length of an M/G/1 queue from its transactional data (service completion times) in a busy period. Practical application of queue-inferencing algorithms may be found in evaluating servers such as automatic teller machines (ATM) or public telephones. These systems keep track on transactional data while the exact number of people waiting in line is not available. This important performance measure can be only estimated using partial information contained in transactional data. The efficiency of a queue-inferencing procedure is important since transactional data (e.g. ATM in a downtown area) may contain hundreds of transactional records. The developed procedure recursively infers a most likely scenario of length r + 1 from the previously inferred most likely scenario of length r. This property, and the algorithm's efficiency (O(log r) per iteration), make the algorithm an attractive solution for real-time estimation when the process under investigation is in progress and the actual busy sequence is not known yet. The total computational complexity is O(n log n) for a busy period sequence with n customers. Due to different queue-inferencing objective (most likely vs. mean queue length) and efficient organization of data structures, the developed procedure is faster than other queue-inferencing algorithms known from the available literature. The algorithm may be modified to use additional information (if available) on upper limits of queue lengths in each service interval. In this case, the computation complexity is O(n²).