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.