RUDN scientist built a neural network to estimate the optimal threshold policy for heterogeneous devices in queueing theory

Queuing theory mathematically describes systems with the need for optimization of the flow of customers, or requests. For example, it is used to calculate the load on servers in computer systems or optimize customer queues in a supermarket (in this case, the “server” is a cashier). The approach by which the requests are distributed depends on each specific task. One of the popular approaches is based on the threshold values with the maximum allowed number of clients in the queue to the server. To find the optimal threshold value, the policy iteration method is used, but it cannot be applied, for example, if there are too many clients. RUDN University mathematicians have shown that in such cases, the classical method can be improved by artificial neural networks.

“Policy-iteration algorithm is a fairly versatile tool for solving various optimization problems. Unfortunately, as is usually the case in practice, this algorithm is not without some limitations, such as the difficulties associated with convergence when the traffic is close to loaded, limitation on the process dimension, and, consequently, on the number of states. Thus, we would like to compensate for some of the weaknesses of this algorithm with other methods for calculating the optimal control policy”, said Dmitry Efrosinin, Ph.D., associate professor of the Department of Probability Theory and Mathematical Statistics at RUDN University.

Mathematicians studied a model of several servers with different operating speeds. The flow of incoming client requests is a Poisson process—the number of requests in any time interval does not depend on how many requests were in another interval. The time it takes to close on each request is distributed exponentially. First, RUDN University mathematicians performed calculations using a classical algorithm and then used the obtained data to teach artificial neural networks. They were then used to calculate the efficiency of the neural network (or the accuracy of the solution).

As a result, it turned out that the neural network gives a fairly accurate result. The value completely coinciding with the theoretical value was obtained with a probability of 80-97%. An almost correct solution, that is, differing by ±1 compared to the theory, was obtained with a probability of 99%. Hence, the mathematicians concluded that, if necessary, the neural network can complement the classical algorithm.

“We strongly believe that the trained neural network can be successfully used to calculate the optimal thresholds for those system parameters for which alternative numerical methods are difficult or impossible to use, for example, in a heavy traffic case. With this study, we confirm that the analysis of controlled queueing systems and the solution of optimization problems using classical Markov decision theory can be successfully combined with machine learning techniques. These approaches do not contradict each other; on the contrary, combining them provides new results”, said Dmitry Efrosinin, Ph.D., associate professor of the Department of Probability Theory and Mathematical Statistics at RUDN University. 

The results are published in the journal Mathematics.