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.