Journal
OIL AND GAS TECHNOLOGIES AND ENVIRONMENTAL SAFETY SERIES: MARINE ENGINEERING AND TECHNOLOGIES SERIES: FISHING INDUSTRY SERIES: MANAGEMENT, COMPUTER SCIENCE AND INFORMATICS SERIES: ECONOMICS

VESTNIK OF ASTRAKHAN STATE TECHNICAL UNIVERSITY (ARCHIVAL)
History Links News Contacts
Submit manuscript
Home / Journals / Vestnik of Astrakhan State Technical University. Series: Management, computer science and informatics / Issue 3 / OPTIMIZATION OF QUEUING SYSTEMS UNDER SIGNIFICANT LOADS
OPTIMIZATION OF QUEUING SYSTEMS UNDER SIGNIFICANT LOADS
Submit manuscript Download PDF
Text
To cite
Citations:

OPTIMIZATION OF QUEUING SYSTEMS UNDER SIGNIFICANT LOADS
UDK 65 Управление предприятиями. Организация производства, торговли и транспорта
Afonin Viktor Vasil'evich 1
Nikulin Vladimir Valer'evich 2
Authors:
1.  National Research Ogarev Mordovia State University (Candidate of Technical Sciences, Assistant Professor; Assistant Professor of the Department of Automated Information Processing Systems and Management)

Russian Federation
2.  National Research Ogarev Mordovia State University (Candidate of Technical Sciences, Assistant Professor; Head of the Department of Information and Communication Technologies and Communication Systems)

Russian Federation
Type:
Article
DOI:
https://doi.org/10.24143/2072-9502-2020-3-105-115
Pages:
from 105 to 115
Status:
Published
Received:
20.07.2020
Accepted:
21.07.2020
Published:
21.07.2020
Subject area:
UDK 65 Управление предприятиями. Организация производства, торговли и транспорта
Language:
Russian
Keywords:
queuing system, failure probability, relative throughput, optimization, service channels
Abstract and keywords
Abstract (English):
The article deals with analytical models of Markov Queuing systems with service failures, incoming requests and requirements. The systems are analyzed in the conflict situations, for example, under significant loads, when the input flow intensity is high relative to the service intensity, which is important for extreme situations, both in technical applications, Internet applications, and social ones. There occurs a problem of optimization – minimization of the number of channels, provided the Queuing system has a guaranteed throughput. There is considered the approach to solving the optimization problem, when the relative system throughput is maximized while minimizing the number of service channels. Given the fact that the analytical formulas of Markov Queuing systems contain factorials, the analytical analysis of systems encounters the computational limitations. In the conducted research, in order to resolve computational difficulties it was decided to apply the approximation of the probabilities of the system states using the Laplace probability integral. Its use is justified precisely at high system load rates and a large number of service channels. There are described the features of applying the Laplace integral in conjunction with the numerical optimization for a conditional extremum. There is given the method of determining the number of service channels, when the probability of denial of service is minimized, respectively, maximizing the relative throughput of the system. There is given a graphical interpretation of the proposed method for optimizing Queuing systems with failures at the significant load. It is shown that during the search for the optimum there is a transition process in which there take place the significant changes in the system parameters: the intensity of the input flow and the intensity of service.

Keywords:
queuing system, failure probability, relative throughput, optimization, service channels
Text
Text (PDF): Read Download
Введение Математические модели на основе систем массового обслуживания (СМО) используются во многих сферах. Многие положения анализа марковских СМО имеют аналитическое решение. Эти системы продолжают исследоваться [1–3]. Безусловно, следует отметить, что в настоящее время значительное внимание уделяется полумарковским и немарковским системам массового обслуживания [4–7]. В данной статье авторы расширяют известные положения марковских СМО. А именно, будет рассматриваться задача с предельно допустимыми нагрузками на системы обслуживания, когда требуется определить то минимальное число приборов (каналов) обслуживания, когда при высокой интенсивности входного потока требований обеспечивается практически безотказная работы СМО типа M/M/m с отказами. С наличием современных инструментальных и программ-ных средств и пакетов анализ СМО облегчается [8–13]. Для решения поставленной задачи при-нята система MATLAB. При решении задач оптимизации СМО рассматриваются различные целевые функции – функционалы оптимизации, решаются различные задачи оптимизации СМО [10–12, 14–20]. В предлагаемой работе в качестве целевой функции принимается функция двух аргументов для поиска минимума вероятности отказа в обслуживании. При этом в качестве параметра выступает количество каналов (приборов) обслуживания. Задача необходимого числа приборов, каналов обслуживания достаточно актуальна. В данной статье развивается подход оптимизации СМО, рассмотренный в [10–12]. В указанных работах существует ограничение на возможное число каналов обслуживания, вызванное тем, что в них применяются классические формулы Эрланга, содержащие вычисления факториалов числа [21–23]. Это ограничение можно обойти при использовании интеграла вероятностей или функции Лапласа для случая больших загрузок марковских СМО [24]. Приведенные в [24] положения в приложении к СМО послужили осно-вой для постановки и решения задачи оптимизации СМО с отказами в плане определения необ-ходимого числа каналов обслуживания с сохранением высокой загрузки системы. С применени-ем алгоритмов минимизации целевой функции нескольких переменных авторами в [24] показа-но, что существует некий переходный процесс до момента установления заданных параметров входного потока и обслуживания, которые по производственным и технологическим причинам не могут быть изменены. Постановка задачи оптимизации и ее решение Марковская система с отказами в соответствии с обозначениями Кендалла описывается тремя полями с дополнением: M/M/m с отказами. Для данной системы известны аналитические решения по определению вероятностей состояния, вероятности отказов, относительной про-пускной способности и т. д. [21–23]. Однако в случае числа каналов обслуживания, превышаю-щего 170, напрямую известными формулами пользоваться не удается в силу ограничений на вычисления факториала больших чисел. Учитывая это и предполагаемую большую загрузку системы, следует воспользоваться аппроксимацией классических формул Эрланга на основе интеграла вероятностей – функции Лапласа [24]. Приведем исходные формулы для описания в стационарном режиме систем массового обслуживания с отказами: (1) где pi – вероятность того, что в системе будет i требований; m – число каналов (приборов) об-служивания;  – приведенная плотность потока заявок; λ – интенсивность входного пуассонов-ского потока;  – интенсивность обслуживания по экспоненциальному закону; p0 – вероятность отсутствия требований (заявок, запросов) в системе. При больших значениях m (m > 20) вероятность отсутствия требований в системе при-ближенно можно заменить экспонентой в результате разложения ее в конечный ряд Тейлора: (2) Для введения интеграла вероятностей (функции Лапласа) принимаются следующие обозначения: (3) (4) (5) где Ф(х) – интеграл вероятностей, или функция Лапласа: Для Ф(–х) = –Ф(х) [24]. Вычитая из (3) выражение (4) и деля на (5), получим формулу для расчета вероятности со-стояний в СМО с отказами в виде (6) Соответственно, для вероятности отказов pm в обслуживании будем иметь (7) Если проследить выражения с (1) по (7), становится очевидным, что вероятность отказов зависит от трех величин: интенсивности входного потока , интенсивности обслуживания  и числа каналов обслуживания m. Но число каналов обслуживания – заранее не известная величина, в отличие от параметров входного потока и обслуживания. Поэтому предлагается рассматривать число каналов обслуживания в виде параметра, который заключен в интервале от одного до приемлемой большой величины, которая зависит от допустимых возможностей рассматриваемой СМО. Следовательно, можно сформулировать задачу минимизации вероятности отказов как функцию двух переменных , , и решать ее в виде итерационного процесса, который обусловлен изменением числа каналов обслуживания m как параметра: . (8) Переменные ,  как интенсивности входного потока и обслуживания должны быть больше нуля. Из анализа известных методов минимизации функций нескольких переменных с ограничениями следует, что, возможно, наиболее приемлемым является метод «active-set» (активный набор), который эффективен для задач средней размерности с негладкими ограничениями. Этот метод поддерживается функцией fmincon системы MATLAB [25]. Первым аргументом функции fmincon является указатель на функцию или имя анонимной функции, например f. При больших загрузках СМО приведем соотношение, связывающее интеграл вероятностей Ф(х) и функцию ошибок erf(х): (9) В свою очередь, функция ошибок erf(x) определяется по формуле (10) С учетом выражений (2)–(7) определяется выражение для правой части целевой функции (8), подлежащей минимизации. В терминах синтаксиса языка системы MATLAB вид анонимной целевой функции f будет следующим: f = @(x)(1 – (0,5 + 0,5 * erf((m – 1 + 0,5 – x (1) / x (2)) / sqrt (2))) / (0,5 + 0,5 * erf ((m + + 0,5 – x(1) / x (2)) / sqrt(2)))). Алгоритм оптимизации СМО с отказами приведен на рис. 1. Рис. 1. Схема предлагаемого алгоритма оптимизации СМО с отказами На рис. 1 не отражены процессы обработки контейнеров LMP, Xm, Fm, которые исполь-зуются для определения графических зависимостей и минимально необходимого числа каналов обслуживания, когда вероятность отказов будет минимальной при конечном числе каналов (устройств) обслуживания. Цикл прохода по числу каналов обслуживания позволяет накопить информацию о поведении параметров системы. В начальный вектор состояния X0 включены заданные параметры СМО. Алгоритм active-set, используемый в опциях функции fmincon, позволяет не прерывать процесс поиска оптимального решения, когда он не может быть найден. В этом случае возвращается NaN (не число), которое можно контролировать с помощью функции isfinite. Случай, когда допустимое число каналов обслуживания не пре-вышает 170, рассмотрен в [11]. Модельные эксперименты оптимизации СМО с отказами Для проверки предложенных алгоритмов по расчету минимального числа каналов обслу-живания СМО с отказами были использованы тестовые модели с параметрами, обеспечивающие высокую приведенную плотность потока заявок (требований). Параметры тестовых моделей СМО (Модель 1, Модель 2) с отказами и результаты поиска оптимального числа каналов обслуживания приведены в таблице. Результаты оптимизации тестовых моделей СМО* Параметры СМО Модель 1 Модель 2 Интенсивность входного потока  109,012 345 Интенсивность обслуживания  0,36 0,23 Приведенная плотность потока заявок  302,811 1 500 Вычислительная точность 1,192093e-07 2,220446e-16 1,192093e-07 2,220446e-16 Расчетная  109,011981 109,012002 345,000000 345,000000 Расчетная  0,365613 0,360468 0,230700 0,230126 Оптимальное число приборов обслуживания 308 310 1 506 1 507 Вероятность отказов при оптимальном числе приборов обслуживания 0,000000e+00 7,102097e-13 0,000000e+00 1,219025e-13 Зона недоступности оптимальных решений Загрузка СМО к оптимальному числу приборов – λ/(mμ) 0,968059 0,975542 0,992992 0,994809 * Размерность интенсивности потока и обслуживания предполагаются в условных единицах. Зона недоступности оптимальных решений определяется через значения контейнера Fm (см. рис. 1), в который заносилось число приборов обслуживания, при которых функция fmincon не определяла оптимального решения. Расчетные переменные  и  определялись при опти-мальном числе приборов обслуживания, которое находилось как минимальное значение, при котором переменные целевой функции принимали свои заданные значения, которые вклю-чались в начальный вектор поиска с помощью функции fmincon. Как видно из табл., вероятно-сти отказов при оптимальном числе приборов обслуживания предельно малы. Соответственно, относительная пропускная способность будет практически равна единице. Очевидно, что за-грузка СМО к общему числу приборов обслуживания m будет стремиться к нулю при m   при конечных значениях  и . Характер изменения контролируемых переменных показан на рис. 2–5 при вычислительной точности 1,192093e-07. Рис. 2. Изменения переменных целевой функции Модели 1 Рис. 3. Изменение загрузки системы Модели 1 Рис. 4. Изменение переменных целевой функции Модели 2 Рис. 5. Изменение загрузки системы Модели 2 Из приведенных диаграмм следует, что при большой загрузке системы характер изменения переменных в зависимости от числа каналов обслуживания наиболее ясно характеризуют за-висимости для тестовой Модели 2. Существует переходный период, при котором аргументы целевой функции значительно отклоняются от своих заданных практических значений, которые представляют собой параметры той или иной СМО. Заключение Рассмотрены возможности численной оптимизации систем массового обслуживания с отказами при большой загрузке. Получены приемлемые, на взгляд авторов, результаты для тестовых моделей СМО. Предложен эвристический алгоритм поиска минимально необходимого числа приборов обслуживания, при котором вероятность отказов предельна мала. Полученные результаты могут быть использованы при проектировании СМО с отказами и с большой приведенной загрузкой.
References

1. Sushil Ghimire, Gyan Bahadur Thapa, Ram Prasad Ghimire, Silvestrov S. A Survey on Queueing Systems with Mathematical Models and Applications. American Journal of Operational Research, 2017, vol. 7, no. 1, pp. 1-14.

2. Budylina E. A., Gar'kina I. A., Sukhov Ia. I. Sistemy massovogo obsluzhivaniia: markovskie protsessy s diskretnymi sostoianiiami [Queuing systems: Markov processes with discrete states]. Molodoi uchenyi, 2014, no. 6, pp. 145-148.

3. Tonui B., Lang'at R., Gichengo J. On Markovian Queuing Models. International Journal of Science and Research (IJSR), 2014, vol. 3, pp. 93-96.

4. Nazarov A. A., Izmailova Ia. E. Issledovanie RQ-sistemy M|E2|1 s vytesneniem zaiavok i sokhraneniem fazovoi realizatsii obsluzhivaniia [Study of RQ-system M | E2 | 1 with crowding out applications and maintaining phase realization of services]. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naia tekhnika i informatika, 2018, no. 42, pp. 72-78.

5. Peschanskii A. I. Polumarkovskaia model' odnolineinoi sistemy obsluzhivaniia s poteriami i nenadezhnym vosstanavlivaemym kanalom [Semi-Markov model of single-line service system with losses and unreliable reconstructed channel]. Dinamicheskie sistemy, 2017, vol. 7 (35), no. 1, pp. 53-61.

6. Ryzhikov Iu. I., Ulanov A. V. Primenenie gipereksponentsial'noi approksimatsii v zadachakh rascheta nemarkovskikh sistem massovogo obsluzhivaniia [Using hyperexponential approximation in problems of calculating non-Markov queuing systems]. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naia tekhnika i informatika, 2016, no. 3 (36), pp. 60-65.

7. Nazarov A. A., Semenova I. A. Asimptoticheskii analiz sistem massovogo obsluzhivaniia s neogranichennym chislom priborov i polumarkovskim vkhodiashchim potokom [Asymptotic analysis of queuing systems with unlimited number of devices and semi-Markov input]. Izvestiia Tomskogo politekhnicheskogo universiteta. Seriia: Upravlenie, vychislitel'naia tekhnika i informatika, 2012, vol. 320, no. 5, pp. 12-17.

8. Antonova V. M., Grechishkina N. A., Kuznetsov N. A., Sukhorukova N. A. Modelirovanie trafika sistem massovogo obsluzhivaniia v srede ANYLOGIC na primere passazhiropotoka stantsii metro [Modeling traffic of queuing systems in ANYLOGIC environment: a study of passenger flow in metro station]. Zhurnal radioelektroniki, 2018, no. 3. Available at: http://jre.cplire.ru/jre/mar18/8/text.pdf (accessed: 12.02.2020)

9. Shchukina N. A., Goremykina G. I., Tarasova I. A. Diskretno-sobytiinoe modelirovanie deiatel'nosti otdeleniia banka v srede MATLAB + SIMULINK [Discrete event modeling of branch bank activity in MATLAB + SIMULINK environment]. Fundamental'nye issledovaniia, 2016, no. 10, pp. 452-456.

10. Afonin V. V., Davydkin V. V. Optimizatsiia sistemy massovogo obsluzhivaniia s ogranichennoi dlinoi ocheredi [Queuing system optimization with limited queue length]. XLVI Ogarevskie chteniia: materialy nauchnoi konferentsii (Saransk, 06-13 dekabria 2017 g.): v 3-kh ch. Saransk, Izd-vo Natsional'nogo issledovatel'skogo Mordovskogo gosudarstvennogo universiteta im. N. P. Ogareva, 2018. Part 1. Pp. 227-232.

11. Afonin V. V., Nikulin V. V. Optimizatsiia Markovskikh sistem massovogo obsluzhivaniia s otkazami v sisteme MATLAB [Optimization of Markov queuing systems with denials in MATLAB system]. Vestnik Astrakhanskogo gosudarstvennogo tekhnicheskogo universiteta. Seriia: Upravlenie, vychislitel'naia tekhnika i informatika, 2018, no. 1, pp. 112-120.

12. Afonin V. V., Nikulin V. V. Optimizatsiia Markovskikh sistem massovogo obsluzhivaniia s ozhidaniem v sisteme MATLAB [Optimization of Markov queuing systems with waiting service in MATLAB]. Vestnik Astrakhanskogo gosudarstvennogo tekhnicheskogo universiteta. Seriia: Upravlenie, vychislitel'naia tekhnika i informatika, 2017, no. 2, pp. 39-47.

13. Zhernovyi Iu. V., Zhernovyi K. Iu. Metod potentsialov dlia zamknutoi sistemy s vremenem obslu-zhivaniia, zavisiashchim ot dliny ocheredi [Potential method for closed system with service time that depends on queue length]. Informatsionnye protsessy, 2015, vol. 15, no. 1, pp. 40-50.

14. Romanenko V. A. Vektornaia optimizatsiia sistemy massovogo obsluzhivaniia s chastichnoi vzai-mopomoshch'iu mezhdu kanalami [Vector optimization of queuing system with partial mutual assistance between channels]. Vestnik Samarskogo gosudarstvennogo aerokosmicheskogo universiteta, 2017, no. 6 (30), pp. 264-272.

15. Nazarov A. A., Fedorova E. A. Issledovanie RQ3 sistemy MMPP|GI|1 metodom asimptoticheskogo analiza vtorogo poriadka v uslovii bol'shoi zagruzki [Investigation of RQ3 system MMPP | GI | 1 by method of asymptotic analysis of second order under large load]. Izvestiia Tomskogo politekhnicheskogo universiteta. Informatsionnye tekhnologii, 2014, vol. 325, no. 5, pp. 6-15.

16. Boiarshinova I. N., Ismagilov T. R., Potapova I. A. Modelirovanie i optimizatsiia raboty sistemy massovogo obsluzhivaniia [Modeling and optimization of queuing system]. Fundamental'nye issledovaniia, 2015, no. 9 (1), pp. 9-13.

17. Baliasnikov V. V., Bogdanov A. A., Maslakov V. P., Staroselets V. G. Mnogokriterial'naia optimizatsiia transportnykh sistem massovogo obsluzhivaniia [Multicriteria optimization of queuing transport systems]. Transport Rossiiskoi Federatsii, 2012, no. 6 (43), pp. 73-76.

18. Miller B. M. Optimization of queuing system via stochastic control. Automatica, 2009, vol. 45, pp. 1423-1430.

19. Chekmenev V. A., Antropov M. S. Analiz sistemy massovogo obsluzhivaniia s dinamicheskimi po chislu trebovanii prioritetami pri bol'shoi zagruzke [Analysis of queuing system with dynamic requirements in terms of number of requirements at high load]. Vestnik Kuzbasskogo gosudarstvennogo tekhnicheskogo universiteta, 2003, no. 4, pp. 6-8.

20. Nazarov A. A., Chekmenev V. A. Analiz i optimizatsiia sistemy massovogo obsluzhivaniia s dinamicheskimi po chislu trebovanii prioritetami pri bol'shoi zagruzke [Analysis and optimization of queuing system with dynamic priorities in terms of number of requirements at high load]. Avtomatika i telemekhanika, 1984, no. 10, pp. 78-87.

21. Shelukhin O. I. Modelirovanie informatsionnykh sistem [Modeling information systems]. Moscow, Goriachaia liniia - Telekom Publ., 2016. 516 p.

22. Tarantsev A. A. Inzhenernye metody teorii massovogo obsluzhivaniia [Engineering methods of queuing theory]. Saint-Petersburg, Nauka Publ., 2007. 175 p.

23. Afonin V. V., Fedosin S. A. Modelirovanie sistem: uchebno-prakticheskoe posobie [Modeling systems: training manual]. Moscow, IntUIT: BINOM, Laboratoriia znanii Publ., 2016. 231 p.

24. Volkov I. K., Zuev S. M., Tsvetkova G. M. Sluchainye protsessy: uchebnik dlia vuzov [Random processes: textbook for high schools]. Pod redaktsiei V. S. Zarubina, A. P. Krishchenko. Moscow, Izd-vo MGTU im. N. E. Baumana, 2006. 448 p.

25. Gol'dshteit A. L. Optimizatsiia v srede MATLAB: uchebnoe posobie [Optimization in MATLAB environment: tutorial]. Perm', Izd-vo Perm. nats. issled. politekhn. un-ta, 2015. 192 p.

This work is licensed under Creative Commons Attribution 3.0 Unported

© "Редакция научных журналов"
Support Powered by Editorum,  Instructions
Login or Create
* Forgot password?