Can machines solve general queueing systems?
Eliran Sherzer post doctoral fellow at Rotman School of Management, Unviersity of Toronto, 3 March 2022, 12:00 PM via zoom
Abstract:
Computing performance measures in general queueing systems is a challenging task: most complex systems are intractable, while simpler systems often require involved mathematical analysis to derive exact solutions. For more complex systems only approximation formulas are available, which may lead to large errors. While a common practical alternative is simulation modeling, a simulation model can only be designed for a specific, not a general system. Moreover, such simulation modelsmay take a long time to converge to an equilibrium solution.
In this paper, we analyze how well a machine can solve a general problem in queueing theory. Toanswer this question, we use a deep learning model to predict the stationary queue-length distribution of an M/G/1 queue (Poisson arrivals, general service times, one server). To the best of our knowledge, this is the first time a machine learning model is applied to a general queueing theory problem. We chose M/G/1 queue for this paper because it lies “on the cusp” of the analytical frontier:
on the one hand exact solution for this model is available, which is both computationally and mathematically complex. On the other hand, the problem (specifically the service time distribution) is general. This allows us to compare the accuracy and efficiency of the deep learning approach to the analytical solutions.
Our results show that our model is indeed able to predict the stationary behavior of the M/G/1 queue extremely accurately. Moreover, our machine learning model is very efficient, computing very accurate stationary distributions in a fraction of a second (an approach based on simulation modeling would take much longer to converge). We also present a case-study that mimics a real-life setting and shows that our approach is more robust and provides more accurate solutions compared to the existing methods. This shows the promise of extending our approach beyond the analytically solvable systems (e.g., G/G/1 or G/G/c).
Joint work: A.Snederovich, O.Baron and D.Krass.
Bio:
Eliran Sherzer is a post doctoral fellow at Rotman School of Management, Unviersity of Toronto. He holds a B.Sc, M.Sc and Ph.D. in Industrial Engineering, all from Ben-Gurion University. He was also a Postdoctoral fellow in the Computer Science department at Tel-Aviv University followed by two years working in the Industry as a Data Scientist at Johnson Controls, developing Computer Vision AI applications. His areas of expertise include Queueing Theory, Stochastic Optimization and Machine-Learning (ML). Recently, he has developed novel ML tools for analyzing queueing systems.
