# Expert-Classification Methods for Estimation of the Structure and Parameters of Controlled Queueing Systems

Alexander Mandel, Sergey Granin, Viktor Laptin

► To cite this version:

Alexander Mandel, Sergey Granin, Viktor Laptin. Expert-Classification Methods for Estimation of the Structure and Parameters of Controlled Queueing Systems. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.528-534, 10.1007/978-3-030-85874-2_56 . hal-04030351

HAL Id: hal-04030351

https://inria.hal.science/hal-04030351

Submitted on 15 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Expert-Classification Methods for Estimation of the Structure and Parameters of Controlled Queueing Systems

Alexander Mandel¹[0000-0001-8936-4596], Sergey Granin² and Viktor Laptin²-⁴⁴⁴⁴

¹ Trapeznikov Institute of Control Sciences RAS, Moscow, Russia

² Moscow Institute of Physics and Technology, Moscow, Russia

³ Lomonosov Moscow State University, Moscow, Russia
almandel@yandex.ru ssgranin@gmail.com straqker@bk.ru

**Abstract.** The problem consideration of estimating the structure and parameters of a queuing system, in which at the moments of control, which are separated from each other by a fixed time step, the optimal switching of the service channels is carried out. To solve the problem of assessing the structure and parameters of the model, procedures of expert-classification analysis and structural forecasting are proposed.

**Keywords:** Controlled Queueing Systems, Markov Input Stream, Structure and Parameter Estimation

## 1 Introduction

The problem of estimating the structure and parameters of the model of optimal control of the queuing system (QS), described in [1], is considered. The main assumption in [1] is the hypothesis of a jump-like Markov step-by-step change in the intensity of the simplest incoming flow. Classical methods of statistical estimation are not quite suitable for studying the structure (the number of elements in a set and the values of various intensities of the incoming flow), as well as the probabilities of transition from state to state. As an alternative, a set of procedures for expert-classification analysis and structural forecasting is proposed.

## 2 Queuing System Model

As stated in [1], in the studied QS the number of working service channels can be changed at the moments of control, which are separated from each other for a fixed time (the control step). In this case, it is considered that the QS receives the simplest incoming flow, the intensity of which $\lambda(t)$ is constant throughout the step, and at the moments of control it undergoes jump-like Markov changes, taking a finite number $k$ of values $\lambda_i$ from the discrete set $\Lambda = \{\lambda_i, i \in \overline{1, k}\}$. The task is to form a strategy for switching working channels (disconnecting a part of working channels or putting into
operation reserve channels), which minimizes the average costs of the QS for a given N-step planning period. In this case, as in [1], it is assumed that the matrix of transition probabilities of the corresponding homogeneous Markov chain $P = \|p_{ij}\|$ is given, where $p_{ij}$ is the transition probability (at the time of control) from the intensity $\lambda_i, i \in \overline{1, k}$, at the previous step to the intensity $\lambda_j, j \in \overline{1, k}$, at the next step.

In [1] was shown that solving the problem of choosing the optimal channel switching strategy is reduced to the following system of dynamic programming equations:

$$C_1^*(\lambda_i, m) = \min_{u \ge u_i} C^{(1)}(\lambda_i, m, u), \qquad (1)$$

$$C_n^*(\lambda_i, m) = \min_{u \ge u_i} \{ C^{(1)}(\lambda_i, m, u) + \alpha \sum_{j=1}^{l} p_{ij} C_{n-1}^*(\lambda_j, u) \}, \quad n \in \overline{2, N}, \qquad (2)$$

where $C_n^*(\lambda_i, m)$ is the minimum possible value of the total average costs at the last n steps of the control process, when the mathematical expectation is taken along the trajectory of the incoming flow intensity, which makes Markov jumps. The variable u in equations (1)–(2) is the current (n steps before the end of the planning period) value of the control decision on the number of switched working channels. It has been proved that the optimal channel switching strategy, as in the equivalent inventory control problem with returns [2], is a four-level strategy.

# 3 The Problem Setting

In the process of practical use of model (1)–(2), it is necessary to estimate the points of the different incoming flow intensities of the $\Lambda = \{\lambda_i\}, i \in \overline{1, k}$ (system structure) and the values of the transition probabilities (system parameters) of the corresponding homogeneous Markov chain $P = \|p_{ij}\|$, where $p_{ij}$ is the probability of transition (at the time of control) from the intensity $\lambda_i, i \in \overline{1, k}$, at the previous step to the intensity $\lambda_j, j \in \overline{1, k}$, in the next step.

To solve the problem of assessing the structure of the system and its parameters, the concept of structural forecasting [3–5] with the involvement of methods of expert-classification analysis [6–7] was chosen.

The idea of structural forecasting is that there is a structured (into clusters) set of dynamically changing objects characterized by a variety of features. This set of objects is subjected to an automatic classification procedure [6] with the assistance of experts, i.e. expert-classification analysis [7].

## 3.1 Observation Data for Controlled QS

Naturally, the results of observations are strongly related to the subject area to which the corresponding QSs belong. In any case, they represent data on the average intensities of incoming flows at each step and various information about specific QS. In this case, separate time intervals with the results of observations of the same QS can act as different objects.
The choosing a set of observations problem solution generates a set of p objects is formed, each of which is characterized by a set of m parameters and is represented by a segment of its trajectory in the state space. Let the discrete duration of this time interval be natural number L. This set of trajectory segments will be called a training sample. The behavior of this set of objects (trajectory segments) at discrete moments of time is studied. The m-dimensional parameter space X is introduced into consideration, in which the jth object at time n is represented by the point x_j(n) = {x_j^{(1)}(n), x_j^{(2)}(n), ..., x_j^{(m)}(n)}. An ordered set of points x_j(n) is a known part of the trajectory that characterizes the dynamics of the jth object.

## 3.2 Formation of the Initial Cluster Structure

To identify the cluster structure of the considered set of objects, a complex automatic classification algorithm is used [8]. The complex algorithm includes m-local optimization algorithms of a given criterion, selection of informative parameters, selection of an initial partition, selection of the number of clusters and filling in missing observations [9].

In modeling and in applications, as a criterion, we used the functional J of the average proximity of points in clusters, defined through the potential function [10]:

$$K(x, y) = 1/(1 + \alpha R^{(m)}(x, y)), \quad (3)$$

where R<sup>(m)</sup>(x, y) is the chosen metric in space X and α and m are tunable parameters of the algorithm. The average proximity of points in a cluster is defined as:

$$K(A_i, A_j) = \frac{2}{p_i(1-p_i)} \sum_{i=1}^{p_i} \sum_{j>i} K(x_i, x_j), \quad (4)$$

where K(x_i, x_j) is determined by formula (3), p_i is the number of points in the cluster A_i. Then criterion J is defined as:

$$K(A_i, A_j) = \frac{2}{p_i(1-p_i)} \sum_{i=1}^{p_i} \sum_{j>i} K(x_i, x_j), \quad (5)$$

# 4 Stages of the Problem Solving

## 4.1 Procedure for Identifying the Initial Structure and Evaluating the Initial Approximation to the Transition Probabilities of Objects

Let the distances for points x_j(1) to the current standards a_i(1) of all selected clusters R<sub>ji</sub><sup>(1)</sup> = R(x_j(1), a_i(1)), i = 1,2, ..., k, j = 1,2, ..., p. This allows us to solve the problem of identifying the initial structure of clusters and evaluating cluster standards, that is, the structure of the set A = {λ<sub>i</sub>}, i ∈ 1, k, and the corresponding values λ<sub>i</sub>.

Then the elements of the transition probability matrix of object j to cluster i, the values p<sub>ji</sub><sup>(1)</sup> = p<sub>ji</sub>(1) are calculated as follows:
$$p_{ji}^{(1)} = \frac{\alpha_j^{(1)}}{R_{ji}^{(1)}}, \qquad (6)$$

where $\alpha_j^{(1)}$ is a normalizing factor.

## 4.2 The Procedure for Evaluating Subsequent Approximations to the Transition Probabilities of Objects

After identifying the initial structure and evaluating the initial approximation to the transition probabilities of objects at the next steps, the elements of the transition probabilities matrix of object j to cluster i are modified using the following procedure. Let us introduce the notation $R_{ji}^{(n)} = R_{ji}^{(n)} - R_{ji}^{(n-1)}$. If the jth point at the moment n coincides with the standard of the i0th cluster, i.e. $R_{ji0}^{(n)} = 0$, then

$$p_{ji}^{(n)} = \begin{cases} 1, & \text{if } i = i_0, \\ 0, & \text{if } i = 1, \dots, k, i \neq i_0 \end{cases}$$

In other words, if a point coincides with the standard of a certain cluster, then the probability for this point to stay in this cluster is 1, and the probability of moving to another cluster is 0.

For the case when $R_{ji0}^{(n)} \neq 0$ transition probabilities are modified according to the following scheme:

$$p_{ji}^{(n)} = \gamma \left\{ p_{ji}^{(n-1)} + \left[ \frac{1+\mathrm{sign}(\Delta R_{ji}^{(n)})}{2} - p_{ji}^{(n-1)} \mathrm{sign}(\Delta R_{ji}^{(n)}) \right] \Delta R_{ji}^{(n)} \right\}, \qquad (7)$$

where $\mathrm{sign} z = \begin{cases} 1, & \text{if } z \ge 0, \\ 0, & \text{if } z < 0, \end{cases}$ and $\gamma$ is the normalizing factor determined by the normalization condition for the transition probabilities: $\sum_{i=1}^{k} p_{ji}^{(n)} = 1$:

## 4.3 Methods for Estimating the Required Intensities $\lambda_j$ and Transition Probabilities $p_{ij}$ from Formula (2)

Since formula (2) uses the probabilities of transition $p_{ij}$ of the considered QS from cluster i to cluster j, and the two previous paragraphs provide predictive estimates of the probabilities of transition of a specific object to a specific cluster, depending on the nature of the training sample, one can act in the following two ways.

*Method 1.* Let the QS under consideration be only one of the objects of the training sample with number s. Then, to estimate the probabilities $p_{ij}$ it is reasonable to use the relation

$$p_{ij} = p_{sj}^{(L)}, \quad \text{object with number s belongs to cluster } A_i, \qquad (8)$$

where L is the length of the time series segment in the training sample, $A_i$ is the cluster of objects with the number i, and the estimates $p_{sj}^{(L)}$ are calculated by formulas (6)–(7).
Method 2. If the considered QS is the only object of the training sample. In other words, the training set is based on the prehistory of the evolution of this QS in its various segments. Then, to estimate the probabilities $p_{ij}$ one can use the relation

$$p_{ij} = \frac{1}{p_i} \sum_{s \in A_i} p_{sj}^{(L)}, \qquad (10)$$

where L is the length of the time series segment in the training sample, $A_i$ is the cluster of objects with the number i, the estimates $p_{sj}^{(L)}$ are calculated by formulas (6)–(7) and $p_i$ is the number of objects in the cluster $A_i$.

## 5 Computer modelling

In this section, we present several graphs of the dependence of the average costs per one step, obtained as a result of modeling the process of functioning of a queuing system (QS) with switchable service channels, which, as noted in the Section 1, is equivalent to the inventory control model with returns using the same four-level strategies. The graphs show the values of the costs $C^*(m)$ (blue color), as well as the values of the functions $B_{on}(m)$ (red color) and $B_{off}(m)$ (green color), where the footnote “on” means turn on the channels in QS and the footnote “off” means turn off the channels in QS. The specificity of the QS is that, in any case, the number of included working service channels must satisfy the condition $u \ge m_{lim}(\lambda_i) = [\lambda_i/\mu] + 1$ for the existence of a stationary mode in the QS [11], where $\mu$ is the service rate on one channel.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Function graphs: average costs per step.</figcaption></figure>
# 6 Summary

To solve the problem of assessing the structure and parameters of the model for choosing the optimal channel switching strategy in a controlled queuing system (QS), procedures for expert-classification analysis and structural forecasting are proposed. An example is given.

# References

1. Mandel, A., Laptin V. Channel Switching Threshold Strategies for Multichannel Controllable Queuing Systems. In: Communications in Computer and Information Science. Vol. 1337, pp. 259–270. link.springer.com/chapter – DOI: 10.1007/978-3-030-66242-4_21 (2020).

2. Mandel, A., Granin, S. Investigation of Analogies between the Problems of Inventory Control and the Problems of the Controlled Queuing Systems. In: Proceedings of the 11th International Conference “Management of Large-Scale System Development” (MLSD). M.: IEEE, 2018, pp. 1–4. Moscow. IEEE. DOI: 10.1109/MLSD.2018.855185 (2018).

3. Dorofeyuk, Yu.A. Adaptive Structural Forecasting Methods. In: Information Technology and Computing Systems. 2010. No.3, pp. 53–58 (in Russian, 2010).

4. Bordukov, D.A., Dorofeyuk, Yu.A. Algorithms for Structural Forecasting. // Materials of the 11th International Conference “Management of Large-Scale Systems Development” (MLSD’2018, Moscow). Vol. 2, pp. 337–340. Moscow. ICS RAS (in Russian, 2018).

5. Dorofeyuk, Yu.A., Chernyavsky, A.L. Intelligent Methods of Dynamic Structural Data Analysis. / Sensors and Systems. 2019. No. 10, pp. 3–8 (in Russian, 2019).

6. Bauman, E.V., Dorofeyuk, A.A. Classification Data Analysis. // Proceedings of the International Conference on Management Problems. Volume 1. pp. 62–77. Mosco. SINTEG (in Russian, 1999).

7. Mandel, A.S., Dorofeyuk, Yu.A. Expert-Classification and Expert-Statistical Information Processing and Decision-Making. In: Proceedings of the International Conference on the Intellectualization of Information Processing. pp. 165–168. Moscow. Max Press. (in Russian, 2010).

8. Dorofeyuk, Yu.A. Formation of Arrays for Modeling Algorithms for Intelligent Information Processing, Modeling a Complex Algorithm for Automatic Classification. In: Large Systems Management. 2010, Issue 31, pp. 353–362 (in Russian, 2010).

9. Dorofeyuk, Yu.A., Pokrovskaya, I.V., Kiseleva, N.E. Complex of Algorithms for Mining Complex Data in the Study of Weakly Formalized Control Systems. In: Machine Learning and Data Analysis. 2014. Vol. 1, No. 10, pp. 1423–1438 (in Russian, 2014).

10. Aizerman, M.A., Braverman, E.M., Rozonoer, L.I. Potential Functions Method in Machine Learning Theory. Moscow. Science. (in Russian, 1970).

11. Saaty, T. Elements of Queueing theory. Mc. Graw Hill. NY.-Toronto-London (1961).