THE ANALYTICAL DESCRIPTION OF FINAL PROBABILITIES FOR STATES OF QUEUING SYSTEMS WITH INPUT FLOW OF GROUPS OF REQUIREMENTS
DOI:
https://doi.org/10.15588/1607-3274-2019-4-3Keywords:
Markov models, Queuing systems, Requirements groups.Abstract
Context. The management of many economic and other “service” systems of random flows of “requirements” is based on theprediction of their efficiency, based on an estimate of the system states probability distribution. In a number of important practical
cases, the input flow may have random composition groups of requirements, which determined the applicability of linear algebra
numerical methods for searching probabilities, and also made it difficult to build queuing systems that are effective in a range of
conditions and made it impossible to obtain probability estimates for systems with an infinite number of places to wait for service.
The objects of the study are Markov models of three types of queuing systems: with refusals, with a limited and with an unlimited
number of places to wait in the conditions of the input flow of a random composition groups of requirements.
Objective. The goal of the work is to obtain an analytical description of the final state probabilities which are necessary to
predict the values of efficiency indicators for three types of Markov multichannel queuing systems: with refusals, with a limited and
with an unlimited number of places to wait in the conditions of the input flow of random composition groups of requirements.
Method. In the general case, the probabilities of states in queuing systems with input flow random groups of requirements are
described by Kolmogorov differential equations. The Kolmogorov equations, in the stationary state of the queuing system, are
transformed into a linearly dependent homogeneous system of algebraic equations. The final probabilities of the states of a queuing system can be found by numerically solving a system of equations using methods well known in linear algebra: complete exclusion, the inverse matrix, and the matrix method of Ramaswami [3], [38], which takes into account the repeating block structure of the system of equations matrix. The infinite number of unpredictable combinations for the set of numerical values of the considered queuing systems parameters makes it difficult to control the operation of such systems and to build systems that are effective in a range of conditions.
In queuing systems with an unlimited number of places to wait, the number of equations becomes infinite, and numerical
methods become unsuitable for final probabilities searching and for solving problems of analysis, synthesis and control of queuing
systems. Analytical expressions for the final probabilities of queuing systems are obtained by equivalent transformations of
homogeneous systems of algebraic equations in the general case of each type of queuing system mentioned above.
Results. The obtained analytical expressions for the final probabilities of the queuing systems states for three noted system types
are not previously known and therefore required verification of their correctness. Such a check was performed by the way of
degenerate the flow of random groups of requirements in the input of the system to the simplest flow of requirements. As a result of verification, analytical expressions for the final probabilities of the considered systems states were automatically transformed into the corresponding well-known models of queuing systems with the simplest input flow of requirements. This effect allows us to consider the well-known models of queuing systems of the simplest input requirements flow – to be a particular case of the obtained models of queuing systems with an input flow of groups of requirements.
Conclusions. To further verify the correctness of the results and to assess the degree of influence of requirements random
number in groups of input flow onto the system efficiency, a numerical example is given for the critical conditions of a constant
intensity of requirements flow equal to the total performance of the system’s service channels. In this case, only the average number of requirements in groups changed. The results of the numerical experiment testify in favor of the correctness of the obtained analytical expressions for the final probabilities and in favor of the possibility of their practical application in real queuing systems when solving problems of forecasting efficiency, as well as analyzing and synthesizing the parameters of real queuing systems.
References
Afanas’yeva L. G., Bulinskaya E. V. Matematicheskiye modeli transportnykh sistem, osnovannyye na teorii ocheredey, Trudy MFTI, 2010, Vol. 2, Issue 4, pp. 6–10.
Albey E., Bilge U., Uzsoy R. Multi-dimensional clearing functions for aggregate capacity modeling in multi-stage production systems, International Journal of Production Research, 2017, Vol. 55, Issue 14, pp. 4164–4179. DOI:https://doi.org/10.1080/00207543.2016.1257169/.
Asmussen S. R. Random Walks, Applied Probability and Queues. Stochastic Modelling and Applied Probability,
, Vol. 51, pp. 220–243. DOI: https://doi:10.1007/0-387-21525-5_8. ISBN 978-0-387-00211-8/.
Assad A. A. Models for rail transportation, Transportation Research Part A: General, 1980, Vol. 14, Issue 3, pp. 205–220. Access mode: DOI: https://doi.org/10.1016/0191-2607(80)90017-5/.
Balsamo S., De Nitto V Personè, Inverardi P. A review on queueing network models with finite capacity queues for software architecture performance prediction, Performance Evaluation, 2003, Vol. 51, Issue. 2, pp. 269–288. Access mode: DOI: https://doi.org/10.1016/S0166-5316(02)00099-8/.
Bocharov P. P., Pechinkin A. V. Teoriya massovogo obsluzhivaniya. Moscow, Izd-vo RUDN, 1995, 520 p.
Bogoyavlenskaya O.Yu. Statsionarnoye raspredeleniye dliny ocheredi v sisteme s neordinarnym potokom i distsiplinoy razdeleniya protsessora, Trudy Petrozavodskogo gosudarstvennogo universiteta, seriya «Matematika», 1996, Vol. 3, pp. 3–10.
Brown L., Gans N., Mandelbaum A. et al. Statistical Analysis of a Telephone Call Center, Queueing-Science Perspective Journal of the American Statistical Association, 2005, Vol. 100, Issue 469, pp. 36–50. DOI:https://doi.org/10.1198/016214504000001808/.
D’Auria B. Stochastic decomposition of the M/G/∞ queue in a random environment, Operations Research Letters, 2007, Vol. 35, pp. 805–812.
Doorn E. A., Jagers A. A. Note on the GI/GI/∞ system with identical service and interarrival-time distributions, Journal of queueing systems, 2004, Vol. 47, pp. 45–52.
Ebadi M., Ahmadi-Javid A. Socio-economic design of control charts for monitoring service processes: a case study of a restaurant system, Journal Quality Technology & Quantitative Management, 2018, Published online. DOI:https://doi.org/10.1080/16843703.2018.1519880/.
Erlang A. K. The Theory of Probabilities and Telephone Conversations, Nyt Tidsskrift for Mathematic Ser. B 20., 1909.
Gaydamaka Yu. V., Zaripova E. R., Samuilov K. E.Modeli obsluzhivaniya vyzovov v seti sotovoy podvizhnoy svyazi. Moscow, RUDN, 2008, 72 p.
Grachev V. V., Moiseev A. N., Nazarov A. A. et al. Mnogofaznaya model’ massovogo obsluzhivaniya sistemy raspredelennoy obrabotki dannykh, Doklady TUSURa, 2012, No. 2 (26), Part 2, pp. 248–251.
Istomina A. A., Badenikov V. Y., Istomin A. L. Optimal’noye upravleniye tovarnymi zapasami na osnove teorii massovogo obsluzhivaniya, FGBOU VO «Angarskiy gosudarstvennyy tekhnicheskiy universitet», 2016, No. 10, pp. 148–152,
Jung-Shyr Wu, Jyh-Yeong Wang Refining the diffusion approximation for M/G/m queuing systems with group arrivals, International Journal of Systems Science, 1992, Vol. 23, Issue 1, pp. 127–133. DOI:https://doi.org/10.1080/00207729208949194/.
Kazakov A., Lempert A. A., Zharkov M. L. Modelirovaniye transportno-peresadochnykh uzlov na osnove sistem massovogo obsluzhivaniya – mnogofaznykh i c bmappotokom, Vestnik ural’skogo gosudarstvennogo universiteta putey soobshcheniya, 2016, No. 4 (14), pp. 4–14. DOI:
https://doi.org/10.20291/2079-0392-2016-4-4-14/.
Khinchin A. Ya. Raboty po matematicheskoy teorii massovogo obsluzhivaniya. Pod red. B. V. Gnedenko. Moscow, Fizmatgiz, 1963, 236 p.
Kleinrok L. Vychislitel’nyye sistemy s ocheredyami. Moscow, Mir, 1979, 600 p.
Klimov G. P. Teoriya massovogo obsluzhivaniya. Moscow, MGU, 2011, 307 p.
Korolkova L. I., Pereverzev P. P. Optimizatsiya protsessov predpriyatiya na osnove novoy metodiki rascheta kharakteristik mnogofaznoy sistemy massovogo obsluzhivaniya s nepreryvnoy zagruzkoy bez promezhutochnykh nakopiteley, Sovremennyye problemy nauki i obrazovaniya, 2012, No. 3.
Kutselay N. O., Safonov S. V. Obsluzhivaniye neordinarnogo potoka trebovaniy, Molodoy uchenyy, 2018. No. 23, pp. 1–2.
Lakatos L., Szeidl L., Telek M. Introduction to queueing systems with telecommunication applications. books.google.com, 2012.
Liu Zhongyia, Liu Jingchenb, Zhai Xinb et al. Police staffing and workload assignment in law enforcement using multi-server queueing models, European Journal of Operational Research, 2019, Vol. 276, Issue 2, pp. 614–625. DOI: https://doi.org/10.1016/j.ejor.2019.01.004
Lozhkovsky A. G. Teoriya massovogo obsluzhivaniya v telekommunikatsiyakh: uchebnik. Odessa, ONAS im. A. S. Popova, 112 p.
Mandelbaum A., Pats G. State-dependent queues:approximations and applications, Stochastic Networks, IMA Volumes in Mathematics, Springer, 1995, pp. 239–282.
Mandelbaum A., Zeltyn S. The impact of customers patience on delay and abandonment: some empirically driven experiments with the M/M/n + G queue, Operations Research, 2004, Vol. 26, pp. 377–411.
Matveev V. F., Ushakov V. G. Sistemy massovogo obsluzhivaniya. Moscow, Izd-vo MGU, 1984, 242 p.
Moiseev A. N., Nazarov A. A.. Beskonechnolineynyye sistemy i seti massovogo obsluzhivaniya. Tomsk, Izd-vo NTL, 2015, 240 p.
Moiseeva S. P. Razrabotka metodov issledovaniya matematicheskikh modeley nemarkovskikh sistem obsluzhivaniya s neogranichennym chislom priborov i nepuassonovskimi vkhodyashchimi potokami: dis. doktora fiz.-mat. nauk. Tomsk, NI TGU, 2014, 260 p.
Pankratova E. V. Issledovaniye matematicheskikh modeley neodnorodnykh beskonechnolineynykh SMO, TSU, 2016, pp. 1–19.
Papadopoulos H. T., Heavey C. Queueing theory in manufacturing systems analysis and design: A classification of models for production and transfer lines, European Journal of Operational Research, 1996, Vol. 92, Issue 1, pp. 1–27. DOI: https://doi.org/10.1016/0377-2217(95)00378-9
Pechinkin A. V. Inversionnyy poryadok obsluzhivaniya s veroyatnostnym prioritetom v sisteme obsluzhivaniya s neordinarnym potokom, Matematicheskiye issledovaniya. Ser. Veroyatnost’ i prilozheniya, 1989, Vol. 109, pp. 83–94.
Plotkin B. K., Delukin L. A. Ekonomiko-matematicheskiye metody i modeli v kommercheskoy deyatel’nosti i logistike:Uchebnik. SPb, Izd-vo, 2015, 345 p.
Popov A. V., Obrezanova E. R., Sinebryukhova E. Yu. Veroyatnostnoye modelirovaniye logisticheskoy sistemy gruzoperevozok, Radíoyelektronní í komp’yuterní sistemi, 2012, No. 1 (53), pp. 144–151.
Puhalskii A. A., Reed J. E. On many-server queues in heavy traffic, Annals of Applied Probability, 2008, Vol. 20, pp. 129–195.
Rachinskaya M. A., Fedotkin M. A. Postroyeniye i issledovaniye veroyatnostnoy modeli tsiklicheskogo upravleniya potokami maloy intensivnosti, Vestnik Nizhegorodskogo universiteta im. N. I. Lobachevskogo, 2014, No. 4 (1), pp. 370–376.
Ramaswami V. A. duality theorem for the matrix paradigms in queueing theory, Communications in Statistics. Stochastic Models, 1990, pp. 151–161. DOI:https://doi:10.1080/15326349908807141/.
Reed J. E. The G/GI/N queue in the Halfin-Whitt regime I:infinite-server queue system equations, The Stern School, NYU, 2007, pp. 1– 59. DOI: https://doi.org/10.1214/09-AAP609/.
Saaty T. L. Elements of queuing theory: with applications. New York, Dover Pubns, 1983, 423 p.
Shakhbazov A. A. Ob odnoy zadache obsluzhivaniya neordinarnogo potoka trebovaniy, Dokl. AN SSSR, 1962, Vol. 145:2, pp. 289–292.
Tarasov V. N., Bakhareva N. F., Akhmetshina E. G. Modeli teletrafika na osnove sovremennoy teorii massovogo obsluzhivaniya, Infokommunikatsionnyye tekhnologii, 2018, Vol. 16, № 1, pp. 68–74.
Tsitsiashvili G. Sh., Osipova M. A., Samuilov K. E. et al. Primeneniye mnogokanal’nykh sistem massovogo obsluzhivaniya s otkazami k konstruirovaniyu telekommunikatsionnykh setey, Dal’nevostochnyy matematicheskiy Zhurnal, 2018, Vol. 18:1, pp. 123–126.
Tsitsiashvili G. Sh. Invariantnyye svoystva sistem massovogo obsluzhivaniya s neskol’kimi potokami, Dal’nevostochnyy matematicheskiy zhurnal, 2018, Vol. 18:2, pp. 267–270.
Venttsel’ Ye. S. Issledovaniye operatsiy. Moscow, Sovetskoye radio, 1972, 552 p.
Zavanella L., Zanoni S., Ferretti I., et al. Energy demand in production systems: A Queuing Theory perspective, International Journal of Production Economics, 2015, Vol. 170, Part B, pp. 393–400. DOI:https://doi.org/10.1016/j.ijpe.2015.06.019/.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 V. P. Gorodnov
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
