Recurrence relations for a multi-channel closed queueing system with Erlangian service times of second order
Yuriy Zhernovyi
,Bohdan Kopytko
Journal of Applied Mathematics and Computational Mechanics |
![]() Download Full Text |
![]() View in HTML format |
![]() Export citation |
@article{Zhernovyi_2017, doi = {10.17512/jamcm.2017.3.12}, url = {https://doi.org/10.17512/jamcm.2017.3.12}, year = 2017, publisher = {The Publishing Office of Czestochowa University of Technology}, volume = {16}, number = {3}, pages = {123--128}, author = {Yuriy Zhernovyi and Bohdan Kopytko}, title = {Recurrence relations for a multi-channel closed queueing system with Erlangian service times of second order}, journal = {Journal of Applied Mathematics and Computational Mechanics} }
TY - JOUR DO - 10.17512/jamcm.2017.3.12 UR - https://doi.org/10.17512/jamcm.2017.3.12 TI - Recurrence relations for a multi-channel closed queueing system with Erlangian service times of second order T2 - Journal of Applied Mathematics and Computational Mechanics JA - J Appl Math Comput Mech AU - Zhernovyi, Yuriy AU - Kopytko, Bohdan PY - 2017 PB - The Publishing Office of Czestochowa University of Technology SP - 123 EP - 128 IS - 3 VL - 16 SN - 2299-9965 SN - 2353-0588 ER -
Zhernovyi, Y., & Kopytko, B. (2017). Recurrence relations for a multi-channel closed queueing system with Erlangian service times of second order. Journal of Applied Mathematics and Computational Mechanics, 16(3), 123-128. doi:10.17512/jamcm.2017.3.12
Zhernovyi, Y. & Kopytko, B., 2017. Recurrence relations for a multi-channel closed queueing system with Erlangian service times of second order. Journal of Applied Mathematics and Computational Mechanics, 16(3), pp.123-128. Available at: https://doi.org/10.17512/jamcm.2017.3.12
[1]Y. Zhernovyi and B. Kopytko, "Recurrence relations for a multi-channel closed queueing system with Erlangian service times of second order," Journal of Applied Mathematics and Computational Mechanics, vol. 16, no. 3, pp. 123-128, 2017.
Zhernovyi, Yuriy, and Bohdan Kopytko. "Recurrence relations for a multi-channel closed queueing system with Erlangian service times of second order." Journal of Applied Mathematics and Computational Mechanics 16.3 (2017): 123-128. CrossRef. Web.
1. Zhernovyi Y, Kopytko B. Recurrence relations for a multi-channel closed queueing system with Erlangian service times of second order. Journal of Applied Mathematics and Computational Mechanics. The Publishing Office of Czestochowa University of Technology; 2017;16(3):123-128. Available from: https://doi.org/10.17512/jamcm.2017.3.12
Zhernovyi, Yuriy, and Bohdan Kopytko. "Recurrence relations for a multi-channel closed queueing system with Erlangian service times of second order." Journal of Applied Mathematics and Computational Mechanics 16, no. 3 (2017): 123-128. doi:10.17512/jamcm.2017.3.12
RECURRENCE RELATIONS FOR A MULTI-CHANNEL CLOSED QUEUEING SYSTEM WITH ERLANGIAN SERVICE TIMES OF SECOND ORDER
Yuriy Zhernovyi1, Bohdan Kopytko2
1Ivan
Franko National University of Lviv, Lviv, Ukraine
2Institute of Mathematics, Czestochowa University of Technology
Częstochowa, Poland
yu.zhernovyi@lnu.edu.ua, bohdan.kopytko@im.pcz.pl
Received: 19 June 2017; Accepted: 21 August 2017
Abstract. We propose a method for determining the steady-state characteristics of a multi-channel closed queueing system with exponential distribution of the time generation of service requests and the second order Erlang distributions of the service times. Recurrence relations to compute the steady-state distribution of the number of customers are obtained. The developed algorithms are tested on examples using simulation models constructed with the assistance of the GPSS World tools.
MSC 2010: 60G10,60J28,60K25,93B40
Keywords: multi-channel closed queueing system, Erlangian service times of second order, fictitious phase method, recurrence relations
1. Introduction
Closed queueing systems are widely used as models to evaluate characteristics of information systems, data networks and queueing processes in production, transport, trade, logistics and service systems [1]. The closed system is also called the system with a finite number of sources or an Engset system.
Suppose that a queueing system with channels receives service requests from
identical sources. Each source is
alternately on and off. A source is off when it has a service request being
served, otherwise the source is on. A source in the
on-state generates a new service request after an exponentially distributed
time (the generation time) with mean
The sources act
independently of each other. The service time of a service request has the second order Erlang
distribution. A service request, that is generated when
channels
are occupied, waits in the queue.
To investigate the systems with Erlangian
service times, in particular the M/Es/1/∞ system
[2], the method of fictitious phases, developed by A.K. Erlang [3], was
applied. The Erlangian service times of the second order means that each customer
runs two service phases sequentially, the duration of which is distributed
exponentially with parameters and
respectively.
The objective of this work is the construction with the aid of a fictitious phase method that is a recursive algorithm for computing the steady-state distribution of the number of customers in the multi-channel closed queueing system. We consider the system with an exponential distribution of the time generation of service requests and Erlangian service times of the second order. A similar approach is used in [4, 5], where recursive algorithms are developed for the systems M/E2/2/m, M/E2/2/∞, M/E2/3/m and M/E2/3/∞ as well as for the systems of the same types with threshold and hysteretic strategies of the random dropping of customers.
2. Construction of a recursive algorithm
Suppose that the service time of each
customer is distributed under the generalized Erlang law of the second order,
that is, the service time is the sum of two independent random variables
exponentially distributed with parameters and
respectively.
Let denote the number of customers in the
system. Based on the phase method, we introduce the following designations for
system states:
signifies that
customers are absent in the system;
signifies that
there are
customers in the system
and that
customers
are at the first phase of service and
customers
are at the second phase
or
. We denote steady-state probabilities that
the system is in the states
and
by
and
, respectively. Then we obtain the
following system of equations for determining these probabilities:
![]() | (1) |
![]() | (2) |
![]() | (3) |
where
Introducing the notation
![]() |
and using equations (1), we find:
![]() | (4) |
![]() |
Recurrence relations (4) allow us to
calculate as
linear functions of the unknown parameters
in the
following sequence:
![]() |
To determine , any
equations from
formulas (2) can be used. The equations (2) have not
been involved in obtaining relations (4).
Using the normalization condition (3), we find steady-state probabilities by the formulas
![]() |
Here is the steady-state
probability that
We calculate the steady-state characteristics - the average number
of customers in the system
the average queue length
and the average
waiting time
- by the formulas
![]() |
Here is a
steady-state value of the arrival rate of customers,
defined by the equality
![]() |
The parameter is a
characteristic of the system capacity, because for the steady-state regime, we
have the equality of the intensities of flows of customers arriving and served.
3. Numerical examples
Consider twentieth-channel
closed queueing systems with an exponential
distribution of the time generation of service requests and Erlangian service
times of the second order for the following values of
the parameters:
The values of the steady-state probabilities
characteristics of the system, found using the recurrence relations obtained in
this paper, are presented in Table 1 and 2. In order to verify the
obtained values, the tables contain the computing results evaluated by the GPSS
World simulation system [6] for the time value
Table 1
Stationary distribution of the number of customers in the system
|
Values of the steady-state probabilities |
|||||
|
|
|
||||
Recurrence method |
GPSS World |
Recurrence method |
GPSS World |
Recurrence method |
GPSS World |
|
0 |
1.056∙10‒12 |
0.000000 |
1.496∙10‒17 |
0.000000 |
3.542∙10‒24 |
0.000000 |
1 |
4.760∙10‒11 |
0.000000 |
9.159∙10‒16 |
0.000000 |
2.811∙10‒22 |
0.000000 |
2 |
1.037∙10‒9 |
0.000000 |
2.736∙10‒14 |
0.000000 |
1.096∙10‒20 |
0.000000 |
3 |
1.454∙10‒8 |
0.000000 |
5.315∙10‒13 |
0.000000 |
2.799∙10‒19 |
0.000000 |
4 |
1.475∙10‒7 |
0.000000 |
7.548∙10‒12 |
0.000000 |
5.266∙10‒18 |
0.000000 |
5 |
1.153∙10‒6 |
0.000001 |
8.353∙10‒11 |
0.000000 |
7.784∙10‒17 |
0.000000 |
10 |
0.001868 |
0.001883 |
9.460∙10‒7 |
0.000004 |
4.320∙10‒12 |
0.000000 |
15 |
0.074600 |
0.074590 |
0.000425 |
0.000406 |
1.300∙10‒8 |
0.000000 |
20 |
0.116516 |
0.117011 |
0.016895 |
0.016916 |
5.467∙10‒6 |
0.000002 |
21 |
0.086435 |
0.085993 |
0.027838 |
0.027924 |
0.000015 |
0.000015 |
22 |
0.056151 |
0.055804 |
0.042782 |
0.043157 |
0.0000411 |
0.000035 |
23 |
0.031662 |
0.031370 |
0.061267 |
0.060925 |
0.000106 |
0.000105 |
24 |
0.015288 |
0.015470 |
0.081565 |
0.081926 |
0.000258 |
0.000283 |
25 |
0.006201 |
0.006080 |
0.100634 |
0.100669 |
0.000596 |
0.000616 |
26 |
0.002057 |
0.002009 |
0.114632 |
0.114369 |
0.001308 |
0.001281 |
27 |
0.000536 |
0.000510 |
0.120022 |
0.119740 |
0.002715 |
0.002826 |
28 |
0.000103 |
0.000100 |
0.114914 |
0.115003 |
0.005327 |
0.005292 |
29 |
0.000013 |
0.000009 |
0.100011 |
0.099971 |
0.009856 |
0.009873 |
30 |
7.985∙10‒7 |
0.000000 |
0.078564 |
0.078377 |
0.017158 |
0.017189 |
31 |
- |
- |
0.055242 |
0.054938 |
0.028042 |
0.027858 |
32 |
- |
- |
0.034419 |
0.034723 |
0.042909 |
0.043099 |
33 |
- |
- |
0.018766 |
0.018799 |
0.061298 |
0.061235 |
34 |
- |
- |
0.008813 |
0.008854 |
0.081490 |
0.081228 |
35 |
- |
- |
0.003492 |
0.003495 |
0.100453 |
0.100511 |
36 |
- |
- |
0.001135 |
0.001104 |
0.114361 |
0.114362 |
37 |
- |
- |
0.000290 |
0.000314 |
0.119694 |
0.119866 |
38 |
- |
- |
0.000055 |
0.000046 |
0.114571 |
0.114588 |
39 |
- |
- |
6.802∙10‒6 |
0.000006 |
0.099694 |
0.099532 |
40 |
- |
- |
4.149∙10‒7 |
0.000000 |
0.078304 |
0.078887 |
42 |
- |
- |
- |
- |
0.034299 |
0.034318 |
44 |
- |
- |
- |
- |
0.008781 |
0.008891 |
46 |
- |
- |
- |
- |
0.001131 |
0.001142 |
48 |
- |
- |
- |
- |
0.000055 |
0.000062 |
50 |
- |
- |
- |
- |
4.133∙10‒7 |
0.000000 |
Table 2
Stationary characteristics of the system
Method |
|
|
|
|
|
Recurrence |
30 |
18.161167 |
0.402916 |
0.034033 |
11.838833 |
GPSS World |
30 |
18.158 |
0.402 |
0.034 |
- |
Recurrence |
40 |
26.689706 |
6.724264 |
0.505193 |
13.310294 |
GPSS World |
40 |
26.687 |
6.725 |
0.505 |
- |
Recurrence |
50 |
36.666670 |
16.666673 |
1.250001 |
13.333331 |
GPSS World |
50 |
36.665 |
16.667 |
1.250 |
- |
4. Conclusions
The numerical algorithm for solving a
system of linear algebraic equations for the steady-state probabilities, proposed
in this paper, is constructed taking into
account the structural features of the system, in particular the presence of
three or four unknown features in most of its equations. The obtained
recurrence relations are used for the direct calculation of the solutions of
the system, that allows us to reduce the amount of calculations in comparison
with the case of application of one of the classical methods (direct or
iterative). Using the obtained recurrence relations makes it possible to reduce
the number of solved equations from to
References
[1] Nesterov Yu.G., Analysis of characteristics of a closed queuing system with relative priorities, Nauka i Obrazovanie. MGTU im. N. Baumana 2014, 3, 242-254 (in Russian).
[2] Bocharov P.P., Pechinkin A.V., Queueing Theory, RUDN, Moskow 1995 (in Russian).
[3] Brockmeyer E., Halstrøm H.L., Jensen A., The Life and Works of A.K. Erlang, Danish Academy of Technical Sciences, Copenhagen 1948.
[4] Zhernovyi K.Yu., Determining stationary characteristics of two-channel queueing systems with Erlangian distribution of service time, Cybernetics and Systems Analysis 2017, 53, 1, 92-104.
[5] Kopytko B., Zhernovyi K. Steady-state characteristics of three-channel queueing systems with Erlangian service times, Journal of Applied Mathematics and Computational Mechanics 2016, 15(3), 75-87.
[6] Zhernovyi Yu., Creating Models of Queueing Systems Using GPSS World, LAP Lambert Academic Publishing, Saarbrücken 2015.
![](2017_3/art_12.pdf.png)