Approximating G(t)/GI/1 queues with deep learning

Many real-world queueing systems exhibit a time-dependent arrival process and can be modeled as a G(t)/GI/1 queue. Despite its wide applicability, little can be derived analytically about this system, particularly its transient behavior. Yet, many services operate on a schedule where the system is empty at the beginning and end of each day; thus, such systems are unlikely to enter a steady state. In this paper, we apply a supervised machine learning approach to solve a fundamental problem in queueing theory: estimating the transient distribution of the number in the system for a G(t)/GI/1. We develop a neural network mechanism that provides a fast and accurate predictor of these distributions for moderate horizon lengths and practical settings. It is based on using a Recurrent Neural Network (RNN) architecture based on the first several moments of the time-dependent inter-arrival and the stationary service time distributions; we call it the Moment-Based Recurrent Neural Network (RNN) method (MBRNN). Our empirical study suggests MBRNN requires only the first four inter-arrival and service time moments. We use simulation to generate a substantial training dataset and present a thorough performance evaluation to examine the accuracy of our method using two different test sets. We perform sensitivity analysis over different ranges of Squared Coefficient of Variation (SCV) of the inter-arrival and service time distribution and average utilization level. We show that even under the configuration with the worst performance errors, the mean number of customers over the entire timeline has an error of less than 3%. We further show that our method outperforms fluid and diffusion approximations. While simulation modeling can achieve high accuracy (in fact, we use it as the ground truth), the advantage of the MBRNN over simulation is runtime. While the runtime of an accurate simulation of a G(t)/GI/1 queue can be measured in hours, the MBRNN analyzes hundreds of systems within a fraction of a second. We demonstrate the benefit of this runtime speed when our model is used as a building block in optimizing the service capacity for a given time-dependent arrival process. This paper focuses on a G(t)/GI/1, however the MBRNN approach demonstrated here can be extended to other queueing systems, as the training data labeling is based on simulations (which can be applied to more complex systems) and the training is based on deep learning, which can capture very complex time sequence tasks. In summary, the MBRNN has the potential to revolutionize our ability for transient analysis of queueing systems.