Diffusion approximation of the network with limited number of same type customers and time dependent service parameters
Mikhail Matalytski
,Dmitry Kopats
Journal of Applied Mathematics and Computational Mechanics |
Download Full Text |
DIFFUSION APPROXIMATION OF THE NETWORK WITH LIMITED NUMBER OF SAME TYPE CUSTOMERS AND TIME DEPENDENT SERVICE PARAMETERS
Mikhail Matalytski1, Dmitry Kopats2
1Institute
of Mathematics, Czestochowa University of Technology
Częstochowa, Poland
2Faculty of
Mathematics and Computer Science, Grodno State University
Grodno, Belarus
m.matalytski@gmail.com, dk80395@mail.ru
Abstract. The article presents research of an open queueing network (QN) with the same types of customers, in which the total number of customers is limited. Service parameters are dependent on time, and the route of customers is determined by an arbitrary stochastic transition probability matrix, which is also dependent on time. Service times of customers in each line of the system is exponentially distributed. Customers are selected on the service according to FIFO discipline. It is assumed that the number of customers in one of the systems is determined by the process of birth and death. It generates and destroys customers with certain service times of rates. The network state is described by the random vector, which is a Markov random process. The purpose of the research is an asymptotic analysis of its process with a big number of customers, obtaining a system of differential equations (DE) to find the mean relative number of customers in the network systems at any time. A specific model example was calculated using the computer. The results can be used for modelling processes of customer service in the insurance companies, banks, logistics companies and other organizations.
Keywords: queueing network, birth and death process, asymptotic analysis
1. Introduction
Exact results for finding state probabilities of Markov chains in the non-stationary regime (transitional regime) was obtained only in certain special cases [1, 2] because of the large dimension of systems of difference-differential equations, which they satisfy. The diffusion approximation method for finding them with a large number of customers has been investigated in [3-5]. Its essence is to approximate a discrete stochastic process that describes the number of customers in network systems, a continuous diffusion process. In this paper, this method is used to analyze an open Markov network with a number of features that were not previously considered in other works.
Queueing networks (QN) are used in the mathematical modelling of various economic and technical systems related to the servicing of client requests, the number of which is actually limited. Often, however, the total number of customers in studied systems changes over time. It predetermines to use at their simulation an open QN with a limited number of customers serviced in them.
Consider an open QN, consists of n + 1 queueing systems (QS) S0, S1, ..., Sn. Supposing that serviced parameters of its network depend on time t, let the number of service lines in the system Si in time t describe a function of time mi(t), that takes integer values, . Service probability of customer in each service line of the system Si on the time interval [t + Δt] equal to μi(t)Δt + o(Δt), . Customers are selected on the service according to FIFO discipline. Customer and service of which the QS Si was completed, with probability pij(t) move in the queue of QS Sj,. Transition matrix, P(t)=||pij(t)|| is the matrix of transition probabilities of an irreducible Markov chain and depends on time 0 ≤ pij(t) ≤ 1. In addition, we assume that the number of customers in the system , except for functions μ0(t), pi0(t), m0(t) determined by the birth and death process, which generates new customers with the intensity and destroys the existing with intensity . Hence, the object under study is an open QN, the total number of customers which is limited and varies in accordance with the process of birth and death, occurring in the system . The network state is determined by the vector
, (1)
where - count of customers in the system in time , . Vector (1) in view of the above, is a Markov random process with continuous time and a finite number of states. Obviously, the total number of customers serviced in the network at time equals . We carry out the asymptotic analysis of Markov process (1) with a big number of customers using the technique proposed in [6, 7]. Note that the analytical results, when the parameters of service customers and transition probabilities of customers not dependent on the time, have been obtained in [8]. Supposing that QN operate under a high load regime of customers, i.e. value . It is sufficiently big, but not limited:.
This article derives a partial differential equation of the second order, and is the equation of the Kolmogorov-Fokker-Planck equation for the probability density of the investigated process. A system of non-homogeneous ordinary differential equations of the first order for the average values of the components of the vector of the network state was obtained. The solution of this system allows us to find the average relative number of customers in each QS in interested time.
2. The derivation of system of differential equations for the average relative number of customers in the network system
We introduce – -vector, all components are equal to zero except -th, which equals 1, . Consider all possible transitions to the state of process during time Δt: from the state can get into with probability , ; from the state we can get into with probability ; from the state we can get into with probability ; from the state – with probability ; from other states – with probability .
From the formula of total probability, we obtain a system of difference equations for the state probabilities :
Therefore, the system of difference-differential Kolmogorov equations for these probabilities is:
. (2)
The solution of system (2) in an analytic form is a difficult task. We shall therefore consider the asymptotic case of a big number of customers on the network, that is, we assume that . To find the probability distribution of the random vector , we move on to the relative variables and consider the vector . Possible values of this vector at a fixed belong to a bounded closed set
, (3)
in which they are located in nodes - dimensional lattice at a distance from each other. By increasing “filling density” of set possible vector components increases, and it becomes possible to consider that it has a continuous distribution with probability density function , which satisfies the asymptotic relation . We use the following approximation function : , .
Rewriting the system of equations (2) for the density , we obtain
where , . If twice continuously differentiable in , then valid the following expansion
,
, .
By using them, and that , we obtain the following representation:
We introduce notations:
, (4)
, , (5)
, (6)
, , (7)
, , (8)
, (9)
Considering them, it turns out that in the case of asymptotic for a sufficiently big K distribution density p(x,t) of vector relative variables satisfies up to a , where the Kolmogorov-Fokker-Planck equation:
, (10)
at points of existence of derivatives.
Then, according to [9], expectations , , accurate to terms order of magnitude determined from the system of DE
, . (11)
From (3), (4) it is obvious that the right-hand side of (11) are continuous piecewise linear functions. Such systems are appropriately addressed by dividing the phase space and find solutions in the areas of the linearity of the right parts. Let – the components of the index set . We divide into two disjoint sets and : , . For fixed the number of partitions of the type equals . Each partition will be defined in the set of disjoint regions such that, , .
You can write the system of equations (11) explicitly for each of the areas of phase space subdivision. Consider the field , which according to no queues in systems in average and the presence of queues in the system . The system of differential equations (11) in this field is of the form:
(12)
The system (12) is a system of ordinary inhomogeneous DE. Its solution of a system for a big n is analytically difficult, so in the event of a network of a big dimension, it is appropriate to use numerical methods.
3. Example
In the computer system Mathematica, a mathematical programming procedure has been developed that implements calculation examples. It shows one example of the calculation of the average relative number of customers in the system network, which is a mathematical model of the processing of customer requests for an insurance company.
Consider the QN, consisting of 6 QS S0, S1, S2, S3, S4, S5, wherein K = 100000. Define the following transition probabilities between QS: p05(t) = 0.2cos2(3t); p04(t) = 0.2sin2(3t); p03(t) = 0.4cos2t; p02(t) = 0.4sin2t; p01(t) = 0.2sin2(2t); p00(t) = = 0.2cos2(2t); p10(t) = 1; pij = 0 in other cases. . ; ; ; ; ; .
Let's pretend that ni(0) = 0,, and consider period where there are no queues in systems S1, S2, S3, S4, S5 in average. Then (12) takes the form
Let μ0(t) = t‒21.3‒t; μ1(t) = t‒11.2t; μ2(t) = t‒32.5t; μ3(t) = 0.1t + 2‒t; μ4(t) = = 0.5t + 1.5‒t; μ5(t) = t + 3‒t , , l0(t)=, where [.] - integer part, in parentheses. Solving the system (13) in the package Mathematica, we obtain
N0(t) = (1.3‒t + 1.2‒t)(t2 ‒ 5t) + 17000; N1(t) = (2.5‒t + 1.2-t)(‒t2 + 5t) + 13000;
N2(t) = (2.5‒t + 0.5‒t)(‒t3 +7t2+8t) + 25000; N3(t) = (0.7‒t + 1.3‒t)(t2 ‒ 0.7t) + 23000;
N4(t) = (0.9‒t + 3‒t)(t2 ‒ 0.7t) + 12000; N5(t) = (0.9‒t + 3‒t + 0.5‒t)(t2 – 1.1t) + 10000.
4. Conclusions
In this paper, Markov QN with a limited number of the same type customers was investigated. The number of customers of systems varies in accordance with the process of birth and death. For obtaining a system of DE for an average number of customers in its systems, the method of diffusion approximation was applied, allowing one to find them with high accuracy for a big number of customers. The results may be useful in modelling and optimization of customer service in the insurance companies, banks, logistics companies and other organizations [10-12].
References
[1] Kelly F.P., Williams R.J., Stochastic Networks. The IMA Volumes in Mathematics and its Applications, Springer-Verlag, New York 1995.
[2] Nykowska M., Model tandemowego systemu obsługi, Przegląd Statystyczny 1984, 29(3), 531-‑540.
[3] Kobayashi H., Application of the diffusion approximation to queueing networks, Journal of ACM 1974, 21(2-3), 316-328, 456-469.
[4] Gelenbe E., Probabilistic models of computer systems. Diffusion approximation waiting times and batch arrivals, Acta Informatica 1979, 12, 285-303.
[5] Lebedev E.A., Chechelnitsky A.A., Diffusion approximation of queueing net with a semi-Markov input rate, Cybernetics 1991, 2, 100-103.
[6] Medvedev G.A., On the optimization of the closed queuing system. Proceedings of the Academy of Sciences of the USSR, Technical Cybernetics 1975, 6, 65-73.
[7] Medvedev G.A., Closed queuing systems and their optimization. Proceedings of the Academy of Sciences of the USSR, Technical Cybernetics 1978, 6, 199-203.
[8] Rusilko T.V., The asymptotic analysis of closed queuing networks with time-dependent parameters and priority application, Vestnik of GrSU. Series 2, Mathematics. Physics. Computer Science, Computer Facilities and Management 2015, 2, 117-123.
[9] Paraev Y.I., Introduction to Statistical Process Control Dynamics and Filtering, Soviet Radio, 1976.
[10] Matalytski M.A., Rusilko T.V., Mathematical Analysis of Stochastic Models of Claims Processing in Insurance Companies, GRSU, Grodno 2007.
[11] Rusilko T.V., Matalytski M.A. Queuing Network Models of Claims Processing in Insurance Companies, LAP LAMBERT Academic Publishing, Saarbrucken 2012.
[12] Matalytski M.A., Kiturko O.M., Mathematical Analysis of HM-networks and its Application in Transport Logistics, GrSU, Grodno 2015.