In this paper the sequential algorithm for generating a matrix of coefficients for a system of homogeneous differential equations describing a model of a nonstationary queueing system is proposed. Its comparison with the recursive algorithm is given. The optimal storage structure of the list of states for a sequential algorithm is given. A decrease of the performing time for the algorithm compared with the recursive one was noted due to no need to sort the list of states and matrix of coefficients.
Automated monitoring systems play an important role in the life of modern society. Monitoring is a continuous process of observing and recording the parameters of an object in comparison with the specified criteria. In some industries data is collected and accumulated very intensively. The mathematical basis for simulation of monitoring systems is queuing theory. Most authors use models of theory on the assumption that the task queue is infinite, there is a stationary mode, and the load factor does not exceed unity [Zeg12, Oso13, Upa16].1 Great practical and theoretical interest are nonstationary queueing system (nSQS). There are few works devoted to this topic in comparison with works devoted to the stationary regime. Examples of such works are [Bub11, Bub10, Bub99]. The various models are discussed in detail in [Bub99]. The disadvantage of the work [Bub11, Bub10] is that they consider only the classical numerical method for solving systems of ordinary differential equations (ODE) - the Runge-Kutta method.
Later in [7–9] a numerical-analytical method is presented, the speed and accuracy of which, when solving an ODE system describing nSQS, are superior to the most common Runge-Kutta method for solving this kind of problems. One of the advantages of this method is the recursive algorithm for generating the matrix of coefficients of an ODE system without deriving the general equation of the ODE system. But this algorithm also has significant disadvantages: (1) the output of the algorithm provides an unordered list of states, the states in it are in the order of their recursive generation; (2) the output of the algorithm provides an array of the desired dimension instead of the lower triangular matrix; (3) based on the first two points, it follows the necessity of sorting the list of states and the matrix of coefficients to bring them into a ready for further use. When replacing the values in the list of states, it is necessary to swap rows and columns for the same state numbers in the matrix, and for large matrix sizes, this is a resourceintensive operation. To eliminate these disadvantages, a sequential algorithm for generating a matrix of coefficients is proposed, this algorithm is using a completely different approach.
Russia, 8–9 November, 2018, published at http://ceur-ws.org 2 Essence of a sequential algorithm The essence of the sequential algorithm is to divide the list of states into subgroups with the same properties and further use these properties. For example, consider the simplest single-channel queueing system (QS) characterized by the number of tasks i (i=¯(0,N)) in it and the number of tasks j (j=¯(0,N-i)), that have already been completed, where N is the total number of tasks that can enter into the system. The input is sequentially received N tasks with intensities {λ1, λ2, … , λN}, which depends on the task number, and they are served with intensities{µ1, µ2, … , µN}, which also depends on the task number.
We divide states into groups, in a way that in each group with constant j, the value of i will grow to N-j. Note some important facts: (1) the number of groups will always be N+1; (2) the length of each next group will always be 1 less than the current; (3) within one group, states can transit into each other sequentially and only with intensity λ; (4) the transition with intensity µ can occur only from state i of group j to the state of the next group j + 1, while the number of the new state inside the group will always be i-1, the intensity of such a transition will always be µj.
The next step is generating a list of states with length Ns = (N+1)*(N+2)/2. The list is generated by simply iterating j in the outer loop, i in the inner loop, until i+j <= N. When this threshold is reached, j increases by one. At the output, the algorithm provides an ordered list of states and does it in a single loop pass.
An important component is the data structure for storing this list. The main list of states contains several groups, each of them is a separate list. Inside the group there are states, each of them is stored as a list containing a state number and a list with its description. This storage structure simplifies further filling of the matrix of coefficients and makes it possible not to go through the list of states when searching for the desired state, but to immediately go to the right place in the list. For example: Main list of states [
Group [
]
State number, [tasks in the system, completed tasks] the matrix of coefficients as A, the number of the current state as Num, µ and λ – the intensities of arriving and maintenance of the task with the number Num.
ANum,Num = ANum,Num - µ ;
ANum,Num-1 = ANum,Num-1 + l ; 2. If this is not the last state within group:
ANum,Num = ANum,Num - l ;
ANum,Pr ev _ Num = ANum,Pr ev _ Num + µ , where Prev_Num is the state number from which you can transit to the state with the Num state number after completed the task, in the state list it is always in group j-1 and has a number in its group i + 1.
After processing all states, such algorithm at the output provides a ready-made lower triangular matrix of coefficients that eliminates the need to sort it.
The flowchart of the entire algorithm is shown in Figure 1. 3 Comparative analysis of recursive and sequential algorithms Both algorithms for generating a matrix of coefficients of an ODE system without deriving the general system equation were implemented in Python3. All measurements were performed when the algorithms are running on the same device, it allows us to consider the obtained values as valid for comparison. The performing time of the algorithms may differ up or down depending on the power of the platform on which the algorithms are running, but the general trends will remain correct. The results of the comparative analysis are presented in the table 1.The flowchart of the entire algorithm is shown in Figure 1.
As we can see from Table 1, the number of possible states of the system, and consequently, the number of equations in the system of ODE grows exponentially from the number of tasks that can enter the nSQS. A graph of dependence between number of tasks and number of states is presented in Figure 2. algorithm, 100 values are used with the number of incoming applications from 1 to 100. As we can see from Figure 6, the performing time of this algorithm has an ordinary linear dependence on the number of tasks coming into the system and the number of states of this system.
The proposed sequential algorithm has undeniable advantages compared with the recursive algorithm: the performing time of it is significantly less and has a linear dependence on the number of tasks coming into the system, in contrast to the exponential dependence in the recursive algorithm. A sequential output algorithm provides a sorted list of states and a lower triangular matrix of coefficients, which eliminates the need for sorting used in the recursive algorithm.
As the system parameters increase, the number of states may increase, in some individual cases, the number of rules and conditions for transitions, but the overall complexity remains at the same level. It is recommended to use a sequential algorithm for implementations of the numerical-analytical method, instead of a recursive algorithm. [Bub10]
Khomonenko Model of reliability of the software with coxian distribution of length of intervals between the moments of detection of errors // International Computer Software and Applications Conference. 34th Annual IEEE International Computer Software and Applications Conference, COMPSAC 2010. Seoul, 2010. Pp. 238-243. [Bub99] V.P. Bubnov, V.I. Safonov Razrabotka dinamicheskih modelej nestacionarnyh system obsluzhivaniya. [Developing dynamic modeling of non-stationary systems.] / V.P. Bubnov, V.I. Safonov. – Saint-Petersburg, 1999, 65 p. [Bub15] V.P. Bubnov, A.S. Eremin, S.A. Sergeev Osobennosti programmnoj realizacii chislenno analiticheskogo metoda raschyota modelej nes-tacionranyh sistem obsluzhivaniya: Trudy SPIIRAN. [Features of the software implementation of numerical-analytical method of calculation models non-stationary service systems: SPIIRAS Proceedings.] / V.P. Bubnov, A.S. Eremin, S.A. Sergeev. 2015. №1. Pp. 218-232. [Bub15] V.P. Bubnov, A.D. Khomonenko, S.A.
Sergeev Recursive method for generating the coefficient matrix of the system of homogeneous differential equations describing nonstationary system maintenance: Proceedings of International Conference on Soft Computing and Measurements, SCM 2015 18. 2015. Pp. 75-77. [Ser15] S.A. Sergeev Method for compilation of the system of homogeneous differential equations for calculation probability-time characteristics which describing non stationary systems. // Intellectual Technologies on Transport.. 2015. №2. Pp. 32-42.