Finding the probabilistically-temporal characteristics of Markov G-network with batch removal of positive customers
Journal of Applied Mathematics and Computational Mechanics
FINDING THE PROBABILISTICALLY-TEMPORAL CHARACTERISTICS OF MARKOV G-NETWORK WITH BATCH REMOVAL OF POSITIVE CUSTOMERS
Mikhail Matalytski 1, Victor Naumenko 2, Dmitry Kopats 2
1 Institute of Mathematics, Czestochowa
University of Technology
2 Faculty of Mathematics and Computer Science, Grodno State University
Received: 04 May 2016; accepted: 11 July 2016
Abstract. The investigation of a Markov queueing network with positive and negative customers and positive customers batch removal has been carried out in the article. The purpose of the research is analysis of such a network at the non-stationary regime, finding the time-dependent state probabilities and mean number of customers. In the first part of this article, a description of the G-network operation is provided with one-line queueing systems. When a negative customer arrives to the system, the count of positive customers is reduced by a random value, which is set by some probability distribution. Then for the non-stationary state probabilities a Kolmogorov system was derived of difference-differential equations. A technique for finding the state probabilities and the mean number of customers of the investigated network, based on the use of an apparatus of multi- dimensional generating functions has been proposed. The theorem about the expression for the generating function has been given. A model example has been calculated.
Keywords: G-network, positive and negative customers, customers batch removal, non-stationary regime, generation function, state probabilities
G-networks or queueing networks with positive and negative customers was introduced by Gelenbe . Such networks with batch removal of positive customers are used in the development of computer systems and networks models, in which defective problems (negative customers) destroy tasks or user jobs (positive customers). Task handlers are the processes running on servers; customers - user jobs for processing .
Let’s consider an open G-queueing network with single-line queueing systems (QS). To the system external environment (QS ) a simple flow of customers arrives with the rate and a simple flow of negative customers with the rate , . All customer flows that arrive to the network are independent. The service durations of positive customers in i-th QS distributed exponentially with the rate , .
In the articles [3-5], a G-network at a transient (non-stationary) regime has been investigated. At that negative customer, arrivining to the system, where there were positive customers, immediately destroy one of them, and then immediately left the network, not having received service in the QS. In the article  was conducted analysis at non-stationary regime of G-network with signals, and in the article  - G-network with signals with random delay.
In this paper, we describe in more detail the other behaviors of negative customers, which arrive to the network systems. Let at time t in the system there are positive customers, where - integer random value. Negative customer arriving to the some system of the network instantly destroys (removes from the network) destroyed immediately of positive customers. If , the system completely is devastated (all positive customers, which are in this QS at a given time are immediately destroyed). Thus, random value , which effectively deter- mines the maximum size of the destruction batch of customers in QS , is subject to an arbitrary discrete distribution law:
Gelenbe studied such behavior of negative customers considering signals in the paper , but only at stationary regime.
As previously explained, in each network system only positive customers are serviced. A positive customer serviced in the QS , with probability sent to the QS as a positive customer, with a probability - as a negative customer, and with probability leaving from the network to the external environment (QS ), .
The state of the network at time meaning the vector
which forms a Markov random process with a countable number of states, where state means that at time in QS there are of positive customers, .
2. The system of the difference-differential Kolmogorov equations for the network state probabilities
We introduce some notations. Let’s - probability of the network state at time ; - Heaviside function, ; - a vector of dimension , consisting of zeros, except for the component with number of , which is equal to 1, . Let’s allows
|, , , , , , .||(3)|
There are following transitions of a random process to the state during time :
1) from the state , in this case, during time a positive customer arriving to the QS with probability ;
2) from the state , wherein the positive customer leaves the network or in an external environment passes into QS as a negative customer, if it had no customers; the probability of such an event equals ;
3) from the states , in this case a negative customer arrives to the QS and destroys a random batch of positive customers; the probability of such event is equal to ;
4) from the state , in this case, after the servicing of a positive customer in the QS it goes to the QS ; the probability of such an event is equal to ;
5) from the states in this case, after the servicing of a positive customer in the QS it goes to the QS as a negative customer, which destroys in it random batch of positive customers; the probability of such an event is equal to ;
6) from the state , while in each QS , , there are no positive customers nor any negative customers arriving, and which during was not to serviced by any customer; the probability of such event is equal to , ;
7) of the remaining states with a probability .
Then, using the formula of total probability, we shall have
Dividing both sides of this relation by and passing to the limit we obtain that the non-stationary states probabilities of the considered network satisfy the following system of difference-differential equations
Suppose that all systems of the network operating in a heavy traffic regime, i.e. , , . Taking this assumption into account, the system (5) takes the form
3. Finding network state probabilities using the generating function
Denote by , where , , n-dimensional generating function:
Multiplied (6) on and adding together all possible values from 0 to , , obtain:
Consider some sums, contained on the right side of (8). Let’s allows
then we can show that
For the sum of we have:
For the sum of we will have:
For the sum of we obtain:
And finally, for the last sum
we shall have:
Therefore, the generating function is a fairly ordinary inhomogeneous linear ordinary differential equation
Since all of the whole QS network operate under high load conditions, the last two expressions in the form of the sums in equation (9) will be zero, and it becomes homogeneous:
Its general solution has the form
We assume that at the initial moment of time, the network is in state , , , , , . Then the initial condition for the last equation (10) will be . Using it, we obtain . Thus, the expression for the generating function has the form
To find the probability of the network states, we transform (11) to a convenient form by expanding its member exhibitors in a Maclaurin series. We can show that the statement is true.
Theorem. The expression for the generating function can be represented in the form
where , .
The probability can be found as the coefficient of in the expansion of function in multiple series (12), and the mean number of customers in the system in the form .
4. Model example
In this example the count of QS lets arriving probabilities of customers to i-th QS be respectively equal , , , , and , .
Consider the time interval . As a time unit we take 1 hour, then h. Let the arriving rates of positive and negative customers be respectively equal and . Let’s arriving rates of positive and negative customers to each QS and , taking into account that , , , respectively will be equal: , , , , , , , , , . Suppose, that service rates of customers in QS are equal: , , , ,.
Let us also transition probabilities of positive and negative customers between QS be equal , , , , , , ; , , , , , , , , , .
Calculations have shown that .
Let’s a random value has a Poisson distribution with parameter and let , then (1) takes form , , . Let also .
We need to find, for example, state probability . It is the coefficient of in the expansion of in multiple series (12), so that the degree of must satisfy the relation , , where , , , , . Hence, it follows that
|, , , , ,|
Then from (12) we find that
Figure 1 shows a chart of the state probability for different on the condition that at the initial time, the network is in a state of , .
Fig. 1. The chart of the state probability
Calculating the partial derivative of the generating function (12) by variable zi in dot z = (1,1,…,1), and carrying out a series of mathematical transformations, we find that the mean number of customers in the queue system Si is calculated by the formula
Figure 2 shows a plot of changes of the mean number of customers in QS .
Fig. 2. The chat for changes of the mean number of positive customers N2(t) in QS S2
In the article an investigation of Markov G-network was conducted in the case when a negative customer can destroy a random batch of positive customers. For such a network operating under a heavy traffic regime, finding a technique for non-stationary state probabilities and a mean number of customers in network systems was proposed using an apparatus based on the use of multivariate generating functions.
 Gelenbe E., Product form queueing networks with negative and positive customers, Journal of Applied Probability 1991, 28, 656-663.
 Naumenko V., Pankov A., Kopats D., Investigation of Markov G-network with positive customers batch removal in transient regime. [In Russian: Issledovaniye markovskoy G-seti s gruppovym udaleniyem polozhitel'nykh zayavok v perekhodnom rezhime]. Vestnik of GrSU. Ser 2, 2016, 3.
 Matalytski M., Naumenko V., Stochastic networks with non-standard customers movement. [In Russian: Stokhasticheskiye seti s nestandartnymi peremeshcheniyami zayavok], Monograph, GrSU, Grodno 2016.
 Naumenko V., Matalytski M., Network analysis with positive and negative requests in transitional mode. [In Russian: Analiz seti s polozhitel'nymi i otritsatel'nymi zaiavkami v perekhodnom rezhime], Vestnik of GrSU, Ser 2. 2016, 3(159), 135-142.
 Matalytski M., Naumenko V., Non-stationary analysis of queueing network with positive and negative messages, Journal of Applied Mathematics and Computational Mechanics 2013, 12(2), 61-71.
 Matalytski M., Naumenko V., Investigation of G-network with signals at transient behavior, Journal of Applied Mathematics and Computational Mechanics 2014, 13(1), 75-86.
 Matalytski M., Naumenko V., Investigation of G-network with random delay of signals at non-stationary behavior, Journal of Applied Mathematics and Computational Mechanics 2014, 13(3), 155-166.
 Gelenbe E., G-networks with signals and batch removal, Probability in the Engineering and Informational Sciences 1993, 7, 335-342.