DOI: https://doi.org/10.15588/1607-3274-2020-4-4

THE STATES FINAL PROBABILITIES ANALYTICAL DESCRIPTION IN QUEUING SYSTEM WITH AN ENTRANCE FLOW OF REQUIREMENTS GROUPS, WITH WAITING AND LEAVING THE QUEUE

V. P. Gorodnov, V. A. Kyrylenko, Iu. E. Repilo

Abstract


Context. The problem of predicting the efficiency of real queuing systems in the event of a possible arrival of requirements groups and leaving of “impatient” requirements from the queue. The aim of the study was to model the operation of such systems to create opportunities to control their operation in real time. 

Objective. The aim of the research is to obtain an analytical description of the state’s final probabilities in a Markov queuing system with an input flow of requirements groups, with individual service of requirements, with a limited number of waiting places and with individual leaving of “impatient” requirements from the queue that is necessary to predict the values of the queuing system performance indicators.

Method. The probabilities of queuing systems states with an input flow of requirements groups with a random composition and with leaving of “impatient” requirements from the queue are described by the Kolmogorov differential equations. In a stationary state, these equations are transformed into a linearly dependent homogeneous system of algebraic equations. The structure of the equations depends on the numerical values of the input flow requirements group’s parameters and the controlled service system. Therefore, an attempt to predict the efficiency of a system is faced with the need to write down and numerically solve a countable set of algebraic equations systems that is quite difficult. The key idea of the proposed method for finding an analytical description of the final probabilities for the specified queuing system was the desire to localize the influence of requirements groups in the input flow on the operation of the queuing system in multiplicative non-ordinary functions. Such functions allow obtaining the required analytical description and assessing the degree of the final probabilities transformation, in comparison with known systems, as well as assessing the predicted values of the noted queuing system efficiency indicators when choosing the parameters for controlling its operation. 

Results. For the first time analytical expressions are obtained for the final probabilities of the queuing system states with an input flow of random composition requirements groups, with a limited number of waiting places, with individual service and leaving “impatient” requirements from the queue, which makes it possible to evaluate all known indicators of the system’s performance. 

Conclusions. The resulting description turned out to be a general case for well-known types of Markov queuing systems with non-ordinary and with the simplest input flow of requirements. 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.


Keywords


Markov models, queuing systems, requirements groups, leaving the queue.

Full Text:

PDF

References


Khinchin A. Ya. Pod red. B. V. Gnedenko Raboty po matematicheskoy teorii massovogo obsluzhivaniya. Moscow, Fizmatgiz, 1963, 236 p.

Venttsel’ Ye. S. Issledovaniye operatsiy. Moscow, Sovetskoye radio, 1972, 552 p.

Gorodnov V. P. The analytical description of final probabilities for states of queuing systems with input flow of groups of requirements, Radio Electronics, Computer Science, Control, 2019, No. 4 (51), pp. 25–37 DOI https://doi.org/10.15588/1607-3274-2019-4-3/.

Erlang A.K. The Theory of Probabilities and Telephone Conversations, Nyt Tidsskrift for Mathematic Ser. B 20, 1909.

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/.

Gaydamaka Yu. V., Zaripova E. R., Samuilov K. E. Modeli obsluzhivaniya vyzovov v seti sotovoy podvizhnoy svyazi. Moscow, RUDN, 2008, 72 p.

Lakatos L., Szeidl L., Telek M. Introduction to queueing systems with telecommunication applications, books.google.com, 2012.

Lozhkovsky A. G. Teoriya massovogo obsluzhivaniya v telekommunikatsiyakh: uchebnik. Odessa, ONAS im. A. S. Popova, 112 p.

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.

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/.

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

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/.

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, № 3.

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

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/.

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, № 10, pp. 148–152,

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, Radioelektronni i komp’yuterni systemy, 2012, № 1 (53), pp. 144–151.

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)000998/.

Kleinrok L. Vychislitel’nyye sistemy s ocheredyami. Moscow, Mir, 1979, 600 p.

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.

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/01912607(80)90017-5/.

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, № 4 (14), pp. 4–14. DOI: https://doi.org/10.20291/2079-0392-2016-4-4-14/.

Rachinskaya M. A., Fedotkin M. A. Postroyeniye i issledovaniye veroyatnostnoy modeli tsiklicheskogo upravleniya potokami maloy intensivnosti, Vestnik Nizhegorodskogo universiteta im. N. I. Lobachevskogo, 2014, № 4 (1), pp. 370–376.

Grachev V. V. Moiseev A. N., Nazarov A. A. et al. Mnogofaznaya model’ massovogo obsluzhivaniya sistemy raspredelennoy obrabotki dannykh, Doklady TUSURa, 2012, № 2 (26), Part 2, pp. 248–251.

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.

Pankratova E. V. Issledovaniye matematicheskikh modeley neodnorodnykh beskonechnolineynykh SMO, TSU, 2016, pp. 1–19.

Puhalskii A. A., Reed J. E. On many-server queues in heavy traffic, Annals of Applied Probability, 2008, Vol. 20, pp. 129–195.

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/09AAP609/.

D’Auria B. Stochastic decomposition of the M/G/∞ queue in a random environment, Operations Research Letters, 2007, Vol. 35, pp. 805–812.

Saaty T. L. Elements of queuing theory: with applications. New York, Dover Pubns, 1983, 423 p.

Klimov G. P. Teoriya massovogo obsluzhivaniya. Moscow, MGU, 2011, 307 p.

Tsitsiashvili G. Sh. Invariantnyye svoystva sistem massovogo obsluzhivaniya s neskol’kimi potokami, Dal’nevostochnyy matematicheskiy zhurnal, 2018, Vol. 18:2, pp. 267–270.

Bocharov P. P., Pechinkin A. V. Teoriya massovogo obsluzhivaniya. Moscow, Izd-vo RUDN, 1995, 520 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.

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.

Matveev V. F., Ushakov V. G. Sistemy massovogo obsluzhivaniya. Moscow, Izd-vo MGU, 1984, 242 p.

Shakhbazov A. A. Ob odnoy zadache obsluzhivaniya neordinarnogo potoka trebovaniy, Dokl. AN SSSR, 1962, Vol. 145:2, pp. 289–292.

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/.

Kutselay N. O., Safonov S. V. Obsluzhivaniye neordinarnogo potoka trebovaniy, Molodoy uchenyy, 2018, № 23, pp. 1–2.

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.

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.

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/.


GOST Style Citations


1. Хинчин А. Я. Работы по математической теории массового обслуживания. Под ред. Б. В. Гнеденко / А. Я. Хинчин. – M. : Физматгиз, 1963. – 236 с.

2. Вентцель Е. С. Исследование операций / Е. С. Вентцель. – M. : Советское радио, 1972. – 552 c.

3. Gorodnov V. P. The analytical description of final probabilities for states of queuing systems with input flow of groups of requirements/ V. Gorodnov // Radio Electronics, Computer Science, Control. – 2019. – № 4 (51). – P. 25–37. DOI https://doi.org/10.15588/1607-3274-2019-4-3/.

4. Erlang A.K. The Theory of Probabilities and Telephone Conversations / A. K. Erlang // Nyt Tidsskrift for Mathematic Ser. B 20. – 1909.

5. Brown L. Statistical Analysis of a Telephone Call Center / [L. Brown, N. Gans, A. Mandelbaum et al.] //Queueing-Science Perspective Journal of the American Statistical Association.– 2005.– Vol. 100, Issue 469. – P. 36–50. DOI: https://doi.org/10.1198/016214504000001808/.

6. Гайдамака Ю.В. Модели обслуживания вызовов в сети сотовой подвижной связи: учебно-методическое пособие. / Ю. В. Гайдамака, Э. Р. Зарипова, К. Е. Самуйлов. – M. : РУДН, 2008. – 72 p.

7. Lakatos L. Introduction to queueing systems with telecommunication applications. / L. Lakatos, L. Szeidl, M. Telek // books.google.com. – 2012.

8. Ложковский A. Г. Теория массового обслуживания в телекоммуникациях : учебник / A. Г. Ложковский. – Одесса : ОНАС им. A. С. Попова – 112 с.

9. Tarasov V. N. Модели телетрафика на основе современной теории массового обслуживания. / В. Н. Тарасов, Н. Ф. Бахарева, Э. Г. Ахметшина // Инфокоммуникационные технологии. – 2018. – Т. 16, № 1. – С. 68–74.

10. Цициашвили Г. Ш. Применение многоканальных систем массового обслуживания с отказами к конструированию телекоммуникационных сетей / Г. Ш. Цициашвили, М. А. Осипова, К. Е. Самуйлов и др. // Дальневост. матем. журн. – 2018. – Т. 18, № 1. – С. 123–126.

11. Ebadi M. Socio-economic design of control charts for monitoring service processes: a case study of a restaurant system / M. Ebadi, A. Ahmadi-Javid // Journal Quality Technology & Quantitative Management. – 2018. DOI: https://doi.org/10.1080/16843703.2018.1519880/.

12. Liu Zhongyia. Police staffing and workload assignment in law enforcement using multi-server queueing models / Zhongyia Liu, Jingchenb Liu, Xinb Zhai et al. // European Journal of Operational Research. – 2019. – Vol. 276, Issue 2. – P. 614– 625. DOI: https://doi.org/10.1016/j.ejor.2019.01.004

13. Albey E. Multi-dimensional clearing functions for aggregate capacity modeling in multi-stage production systems / E. Albey, U. Bilge, R. Uzsoy // International Journal of Production Research. – 2017. – Vol. 55, Issue 14. – P. 4164–4179. DOI: https://doi.org/10.1080/00207543.2016.1257169/.

14. Королькова Л. И. Оптимизация процессов предприятия на основе новой методики расчета характеристик многофазной системы массового обслуживания с непрерывной загрузкой без промежуточных накопителей [ Текст] / Л. И. Королькова, П. П. Переверзев // Современные проблемы науки и образования. – 2012. – № 3. 

15. Papadopoulos H. T. Queueing theory in manufacturing systems analysis and design: A classification of models for production and transfer lines / H. T. Papadopoulos, C. Heavey // European Journal of Operational Research. – 1996. – Vol. 92, Issue 1. – P. 1–27. DOI: https://doi.org/10.1016/0377-2217(95)00378-9 

16. Zavanella L. Energy demand in production systems: A Queuing Theory perspective. / L. Zavanella, S. Zanoni, I. Ferretti, et al. // International Journal of Production Economics. – 2015. – Vol. 170, Part B – P. 393–400. DOI: https://doi.org/10.1016/j.ijpe.2015.06.019/.

17. Истомина A. A. Оптимальное управление товарными запасами на основе теории массового обслуживания / A. A. Истомина, В. Я. Бадеников, А. Л. Истомин // Вестник ангарского государственного технического университета. – 2016. – № 10. – С. 148–152.

18. Плоткин Б. К. Экономико-математические методы и модели в коммерческой деятельности и логистике : учебник / Б. К. Плоткин, К. Л. А. Делюкин. – СПб. : Изд-во, 2015. – 345 с. 

19. Попов А. В. Вероятностное моделирования логистической системы грузоперевозок / А. В. Попов, Е. Р. Обрезанова, Е. Ю. Синебрюхова // Радіоелектронні і комп’ютерні системи. – 2012. – № 1 (53). – С. 144–151. 

20. Balsamo S. A review on queueing network models with finite capacity queues for software architecture performance prediction. / S. Balsamo, De Nitto V Personè, P. Inverardi // Performance Evaluation. – 2003. – Vol. 51, Issue. 2. – P. 269– 288. DOI: https://doi.org/10.1016/S0166-5316(02)00099-8/.

21. Клейнрок Л. Вычислительные системы с очередями / Л. Клейнрок. – M. : Мир, 1979. – 600 с.

22. Афанасьева Л. Г. Математические модели транспортных систем основанные на теории очередей / Л. Г. Афанасьева, Е. В. Булинская // Труды МФТИ. – 2010. – Т. 2, № 4. – С. 6– 10.

23. Assad A. A. Models for rail transportation / A. A. Assad // Transportation Research Part A: General. – 1980. – Vol. 14, Issue 3. – P. 205–220. DOI: https://doi.org/10.1016/01912607(80)90017-5/.

24. Казаков Л. A. Моделирование транспортно-пересадочных узлов на основе систем массового обслуживания – многофазных и c BMAP-потоком / А. Л. Казаков, А. А. Лемперт, М. Л. Жарков // Вестник Уральского государственного университета путей сообщения. – 2016. – № 4 (14). – С. 4–14. DOI: https://doi.org/10.20291/2079-03922016-4-4-14/.

25. Рачинская М. А. Построение и исследование вероятностной модели циклического управления потоками малой интенсивности. / M. A. Рачинская, M. A. Федоткин // Вестник Нижегородского университета им. Н. И. Лобачевского. – 2014. – № 4 (1). – С. 370–376.

26. Многофазная модель массового обслуживания системы распределенной обработки данных. / В. В. Грачев, А. Н. Моисеев, А. А. Назаров и др. // Журнал «Доклады ТУСУР». – 2012. – № 2, Часть 2 (26). – С. 248– 251. 

7. Mandelbaum A. State-dependent queues: approximations and applications / A. Mandelbaum, G. Pats // Stochastic Networks, IMA Volumes in Mathematics, Springer. – 1995. – P. 239–282. 

28. Mandelbaum A. The impact of customers patience on delay and abandonment: some empirically driven experiments with the M/M/n + G queue / A. Mandelbaum, S. Zeltyn // Operations Research. – 2004. – Vol. 26. –P. 377–411.

29. Панкратова Е. В. Исследование математических моделей неоднородных бесконечнолинейных СМО / E. В. Панкратова // ТГУ. – 2016. – С. 1–19. 

30. Puhalskii A. A. On many-server queues in heavy traffic / A. A. Puhalskii, J. E. Reed // Annals of Applied Probability. – 2008. – Vol. 20. – P. 129–195. 

31. Reed J. E. The G/GI/N queue in the Halfin-Whitt regime I: infinite-server queue system equations / J. E. Reed // The Stern School, NYU. – 2007. – P. 1–59. DOI: https://doi.org/10.1214/09-AAP609/.

32. D’Auria B. Stochastic decomposition of the M/G/∞ queue in a random environment. / B. D’Auria // Operations Research Letters. – 2007. – Vol. 35. – P. 805–812.

33. Saaty T. L. Elements of queuing theory: with applications / T. L. Saaty. – New York : Dover Pubns, 1983. – 423 p.

34. Климов Г. П. Теория массового обслуживания / Г. П. Климов. – M. : МГУ, 2011. – 307 p. 

35. Цициашвили Г. Ш. Инвариантные свойства систем массового обслуживания с несколькими потоками / Г. Ш. Цициашвили // Дальневосточный математический журнал. – 2018. – Т. 18:2. – С. 267–270. 

36. Бочаров П. П. Теория массового обслуживания. / П. П. Бочаров, А. В. Печинкин – M. : Изд-во РУДН, 1995. – 520 с. 

37. Моисеев A. Н. Бecкoнeчнo линeйные c иcтeмы и ceти мaccoвoгo обcлуживaния / A. Н. Моисеев, A. A. Назаров. – Томск : Изд-во НТЛ, 2015. – 240 с. 

38. Моисеева С. П. Разработка методов исследования математических моделей немарковских систем обслуживания с неограниченным числом приборов и непуассоновскими входящими потоками: дис. доктора физ.мат. наук / С. П. Моисеева. – Томск : ТГИ, 2014. – 260 с. 

39. Doorn E. A. Note on the GI/GI/∞ system with identical service and interarrival-time distributions. / E. A. Doorn, A. A. Jagers // Journal of queueing systems. – 2004. – Vol. 47. – P. 45–52.

40. Матвеев В. Ф. Системы массового обслуживания. / В. Ф. Матвеев, В. Г. Ушаков – M : Изд-во МГУ, 1984. – 242 с.

41. Шахбазов A. A. Об одной задаче обслуживания неординарного потока требований. / A. A. Шахбазов // Докл. АН СССР. – 1962. – Т. 145:2. – С. 289–292. 

42. Jung-Shyr Wu, Jyh-Yeong Wang Refining the diffusion approximation for M/G/m queuing systems with group arrivals. / Wu Jung-Shyr, Wang Jyh-Yeong // International Journal of Systems Science. – Vol. 23. – 1992. – Issue 1. – P. 127–133. DOI: https://doi.org/10.1080/00207729208949194/.

43. Куцелай Н. O. Обслуживание неординарного потока требований. / Н. O. Куцелай, С. В. Сафонов // Молодой ученый. – 2018. – № 23. – С. 1–2. 

44. Богоявленская O. Ю. Стационарное распределение длины очереди в системе с неординарным потоком и дисциплиной разделения процессора / O. Ю. Богоявленская // Труды Петрозаводского государственного университета, серия «Математика». – 1996. – Вып. 3. – С. 3–10.

45. Печинкин А. В. Инверсионный порядок обслуживания с вероятностным приоритетом в системе обслуживания с неординарным потоком / A. В. Печинкин // Математические исследования. Сер. Вероятность и приложения. – 1989. – Т. 109. – С. 83–94. 

46. Ramaswami V. A duality theorem for the matrix paradigms in queueing theory / V. Ramaswami // Communications in Statistics. Stochastic Models, 1990. – P. 151–161. DOI: https://doi :10.1080/15326349908807141/







Copyright (c) 2020 V. P. Gorodnov, V. A. Kyrylenko, Iu. E. Repilo

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.